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

2075 / 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 + розмір списку)

1. Сортує при виводі

import java.util.HashMap;
HashMap<Integer, String> numbersAndNames = new HashMap<>();
numbersAndNames.put(1, "Neo");
numbersAndNames.put(3, "Taras");
numbersAndNames.put(2, "Bohdan");
System.out.println(numbersAndNames);

2. Сортує при виводі

import java.util.Hashtable;
Hashtable<Integer, String> hm = new Hashtable<Integer, String>();

hm.put(102, "Roshen");
hm.put(100, "AVK");
hm.put(101, "Konty");
hm.put(103, "Mars");

for (Map.Entry m : hm.entrySet()){
  System.out.println(m.getKey() + " " + m.getValue());
}