Краткий обзор Хэш-таблиц

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

Концептуально, ассоциативные структуры данных хранят данные в парах ключ/значение. Это означает, что для каждого сохраненного значения, есть соответствующий ключ, используемый, чтобы получить доступ к значению. Примером реального мира ассоциативной структуры данных является словарь. В словаре данные хранятся в парах ключ/значение. Ключи являются словами, и значения являются определениями. Чтобы получить доступ к определению, нужно использовать соответствующий ключ.

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