Чим відрізняється масив від хеш-таблиці в мові програмування?


Відповідь 1:

У хеш-таблицях використовуються масиви. Масиви мають важливу властивість хешування: ви можете отримати доступ до будь-якого елемента за постійний час, якщо знаєте його індекс.

Можна використовувати масиви для відра. Скажімо, ви хотіли, щоб ви порахували кількість кожної літери в тексті, скажімо, для створення чогось подібного до коду Морзе. Ви створюєте масив з 26 записами (для простого нецензованого римського алфавіту). Щоразу, коли ви бачите букву, ви обчислюєте індекс і переходите до цього запису в масиві.

Таблиці хешу розширюють це для довільно довгих клавіш. Ви обчислюєте хеш ключа і переходите до цього індексу. Проблема полягає в тому, що кілька клавіш мають один і той же хеш. Існують різні способи боротьби з цим, деякі з яких перемагають мету хешу (але їх легко здійснити). Деякі з них не підтримують постійну властивість часу, принаймні в середньому.

Найкраще, що я бачив, це те, що хеш-переспівування, яке, якщо пам'ять слугує десятиліттями тому, Гоннет і Манро показали, мають в середньому трохи більше 4-х доступу з коефіцієнтом навантаження 50%, незалежно від розміру хеш-таблиця. Однак це вимагає використання простих чисел, і це ускладнює їх реалізацію. Вам доведеться якось знайти прості числа. На щастя, хеш-таблиці не настільки великі, що це стає смішним.