В чем разница между массивом и хеш-таблицей в языке программирования?


Ответ 1:

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

Вы можете использовать массивы для ведер. Допустим, вы хотели, чтобы вы подсчитали, сколько каждой буквы в тексте, скажем, для разработки чего-то вроде азбуки Морзе. Вы создаете массив с 26 записями (для простого безударного латинского алфавита). Всякий раз, когда вы видите букву, вы рассчитываете индекс и переходите к этой записи в массиве.

Хеш-таблицы расширяют это для произвольно длинных ключей. Вы вычисляете хеш ключа и переходите к этому индексу. Проблема в том, что несколько ключей имеют одинаковый хэш. Существуют различные способы решения этой проблемы, некоторые из которых побеждают назначение хэша (но их легко реализовать). Некоторые из них не имеют и поддерживают свойство постоянного времени, по крайней мере, в среднем.

Лучшее, что я видел, - это перефразирование надстроек, которое, если бы память работала десятилетия назад, оказалось, что Гоннет и Манро имели в среднем чуть более 4 обращений с коэффициентом загрузки 50%, независимо от размера хеш-таблица. Это, однако, требует использования простых чисел, и это усложняет реализацию. Вы должны найти простые числа как-то. К счастью, хеш-таблицы не становятся такими большими, что это становится смешным.