Java геш-таблиця

Геш-таблиця (hash table, hash map) — структура даних, що дозволяє зберігати пари (ключ, значення) і здійснювати три операції за ключем:

  • додавання нової пари
  • пошук
  • видалення

Геш-таблиця працює швидше за список де O(n), і представляє собою масив з геш-функцією 

У масива на 1 000 000 000 ключів – будуть використовуватися не всі комірки, і ми маємо стиснути цей діапазон функцією

Ключ (string) -> hesh code map (int) -> comprasion map (int в малому діапазоні)       hash function

dog = god – сума кодів цифр в ANSI однакова – виходить колізія

Колізію усувають методами:

  1. Відкрита адресація – дублюючі ключі додаємо вкінці таблиці, в найгіршому варіанті перебравши усі елементи отримуємо O(n)
  2. Метод ланцюжків – додаються в однозв’язний список кожного елементу за постійну одиницю часу O(1 + розмір списку)