Зіставте хеш-таблицю і mар зі стандартної бібліотеки шаблонів (STL). Як організована хеш-таблиця? Яка структура даних буде оптимальною для невеликих обсягів даних?
У хеш-таблицю значення потрапляє при виклику хеш-функції з ключем. Самі значення зберігаються в невідсортованому порядку. Так як хеш-таблиця використовує ключ для індексації елементів, вставка або пошук даних займає O (1) часу (з урахуванням мінімальної кількості колізій в хеш-таблицях). У хеш-таблиці також потрібно обробляти потенційні колізії. Для цього використовується ланцюжок - зв'язний список всіх значень, ключі яких відображаються в конкретний індекс.
map (STL) вставляє пари ключ / значення в дерево двійкового пошуку, засноване на ключах. При цьому не потрібно обробляти колізії, а так як дерево збалансовано, час вставки і пошуку становить O (log N).
Як реалізована хеш-таблиця?
Хеш-таблиця реалізується як масив зв'язкових списків. Коли ми хочемо вставити пару ключ / значення, то, використовуючи хеш-функцію, відображаємо ключ в індекс масиву. При цьому значення потрапляє в зазначену позицію зв'язного списку.
Не можна сказати, що елементи зв'язного списку з певним індексом масиву мають один і той же ключ. Швидше, функція hashFunction (key) для цих значень збігається. Тому, щоб отримати значення, відповідне ключу, ми повинні зберігати в кожному вузлі і ключ і значення.
Підіб'ємо підсумок: хеш-таблиця реалізується як масив зв'язкових списків, де кожен вузол списку містить два компоненти: значення і вихідний ключ. Давайте перерахуємо особливості реалізації хеш-таблиць:
- Потрібно використовувати гарну хеш-функцію, щоб гарантувати, що ключі були правильно розподілені. Якщо ключі будуть погано розподілені, то виникне безліч колізій і швидкість знаходження елемента знизиться.
- Незалежно від того, наскільки хороша наша хеш-функція, колізії будуть виникати, і ми будемо мати потребу в їх обробці. Це має на увазі використання ланцюжків зв'язкових списків (або інший метод вирішення проблеми).
- Можна реалізувати методи динамічного збільшення або зменшення розміру хеш-таблиці. Наприклад, коли відношення кількості елементів до розміру таблиці перевищує певне значення, слід збільшити розмір хеш-таблиці. Це означає, що нам потрібно створити нову хеш-таблицю і передати в неї записи зі старої. Оскільки це дуже трудомісткий процес, потрібно зробити все можливе, щоб розмір таблиці не змінювався надто часто.
Що може замінити хеш-таблицю при роботі з невеликими обсягами даних?
Можна використовувати mар (з STL) або бінарне дерево. Хоча це зажадає O (log (n)) часу, обсяг даних не великий, тому тимчасові витрати будуть незначними.
У чому перевага map?
У дерева є принаймні одна помітна перевага в порівнянні з хеш-таблицею. У map можна пройтися ітератором за зростанням або спаданням ключів і зробити це швидко. Хеш-таблиця в цьому плані програє.