Відображений хеш-масив
(HAMT) є реалізація асоціативного масиву, який поєднує характеристики хеш-таблиці та масиву, відображеного trie. Це вдосконалена версія більш загального поняття хеш-дерева.
Ідея хешування така щоб рівномірно розподілити записи (пари ключ/значення) по масиву. Кожному елементу призначається ключ (перетворений ключ). Використовуючи цей ключ, ви можете отримати доступ до елемента за час O(1). Використовуючи ключ, алгоритм (хеш-функція) обчислює індекс, який передбачає, де можна знайти або вставити запис.
Хеш-карти є загальною структурою даних для зберігання пар ключ-значення для ефективного пошуку. Значення, що зберігається в хеш-карті, отримується за допомогою ключа, під яким воно зберігалося. # `states` — це хеш-карта з ключами абревіатур штатів і значеннями назв штатів.
Хеш-таблиця — це тип структури даних, у якій інформація зберігається в легкодоступний та ефективний спосіб. У методі ключ-значення ключам призначаються випадкові індекси, а їхні значення зберігаються в масиві. Індекс — це інформація про те, де саме в масиві зберігається значення.
Хешування є процес перетворення будь-якого ключа або рядка символів в інше значення. Зазвичай це представлено коротшим значенням фіксованої довжини або ключем, який представляє та полегшує пошук або використання оригінального рядка. Найпопулярнішим використанням хешування є налаштування хеш-таблиць.
Хеш-таблиці, як правило, працюють швидше, коли справа доходить до пошуку елементів. У масивах вам потрібно пройти по всіх елементах, перш ніж знайти те, що ви шукаєте, тоді як у хеш-таблиці ви переходите безпосередньо до розташування елемента.Вставлення елемента також швидше в хеш-таблицях, оскільки ви просто хешуєте ключ і вставляєте його.