C++ Геш-таблиця

2075 / C++ / Додатково / Геш-таблиця (Hash table)

 

Синоніми з різних мов: асоціативний масив, мапа, відображення чи словник

Структура даних що включає в себе ключ і значення

Дозволяє швидко отримати інформацію по ключу, в незалежності в кількості даних

Працює швидше за лінійний пошук

Пошук працює так само швидко, і на10 записах, і на 10 000 000

Функціонал: додавання пари, пошук та видалення за ключем

 

Геш-значення
від ключа		 Ключ Значення
1 A 0671234567
2 BB 0987654321
3 CCC 0932223344
5 DDDDD 0631112233
  • Геш-функція – перетворює ключ на номер в таблиці
  • Колізія – коли два ключі мають однакове геш-значення

 

 

1. Варіант розв'язку колізії – метод відкритої адресації

 

#define CAPACITY 1000 

int hash_function(string str)
{
    int i = 0;

    for (int j = 0; str[j]; j++)
        i += str[j];

    return i % CAPACITY;
}

 

Беремо суму букв ключа і знаходимо залишок від ділення на розмір таблиці

A – 65%5 = 0

BB – (66*2) = 132%5 = 2

CCC – (67*3) = 201%5 = 1

DDDDD – (68*5) = 340%5 = 0 // колізія з A

При колізії ми можемо:

  1. зберегти цей запис в наступну вільну комірку *
  2. ще раз запустити геш-функцію і знайти наступний індекс і тд.
  3. якщо ж таблиця замала – копіюємо все в більшу таблицю

 

Плюс:

  1. Швидкість
  2. Менше їсть пам'яті

Мінуси:

  1. Може бути довгий шлях пошуку елементу після колізії
  2. Потребує ретельного підбору розміру внутрішнього масиву

 

 

2. Варіант розв'язку колізії – метод ланцюжків

При колізії ми додаємо 2, 3, 4… елемент в список

Плюс:

  1. Простота реалізації

Мінуси:

  1. Додаткову пам'ять з'їдають вказівники
  2. Стрибати на окремі об'єкти – це трохи повільніше від роботи з масивом

 

educative.io
geeksforgeeks.org – замінити на <bits/stdc++.h> на <list>

 

 

Геш-функція має відповідати умовам:

  1. Для одного ключа має завжди давати один і той індекс
  2. Данні мають розподілятися рівномірно по всій таблиці (менше колізій)
  3. Індекси мають швидко обчислюватися
  4. Індекси які мають бути в межах таблиці