Ну, подумай об этом так.
Если вы используете массив, простую структуру данных, основанную на индексах, и заполняете ее случайными данными, поиск конкретной записи становится все более и более дорогой операцией, поскольку вы заполняете ее данными, поскольку в основном вам приходится начните поиск с одного конца на другой, пока не найдете нужный.
Если вы хотите получить более быстрый доступ к данным, вы обычно прибегаете к сортировке массива и использованию бинарного поиска. Это, однако, увеличивает скорость поиска существующего значения и замедляет вставку новых значений, поскольку вам нужно перемещать существующие элементы, когда вам нужно вставить элемент посередине.
С другой стороны, хеш-таблица имеет связанную функцию, которая принимает запись и уменьшает ее до числа, хеш-ключа. Этот номер затем используется как индекс в массиве, и здесь вы сохраняете запись.
Хеш-таблица вращается вокруг массива, который изначально начинается пустым. Пустой не означает нулевую длину, массив начинается с размера, но все элементы в массиве ничего не содержат.
Каждый элемент имеет два свойства, данные и ключ, который идентифицирует данные. Например, список почтовых индексов США будет представлять собой почтовый индекс -> имя типа ассоциации. Функция уменьшает клавишу, но не учитывает данные.
Таким образом, когда вы вставляете что-то в хеш-таблицу, функция уменьшает ключ до числа, которое используется в качестве индекса в этом (пустом) массиве, и именно здесь вы храните данные, как ключ, так и связанный с ним данные.
Затем, позже, вы захотите найти конкретную запись, для которой вы знаете ключ, поэтому вы запускаете ключ через ту же функцию, получаете его хеш-ключ и переходите в это конкретное место в хеш-таблице и извлекаете данные. есть.
Теория гласит, что функция, которая превращает ваш ключ в хеш-ключ, это число, вычислительно намного дешевле, чем линейный поиск.
Типичная хеш-таблица не имеет бесконечного числа элементов, доступных для хранения, поэтому это число обычно уменьшается до индекса, который соответствует размеру массива. Один из способов сделать это - просто взять модуль индекса по сравнению с размером массива. Для массива размером 10 индекс 0-9 будет отображаться непосредственно в индекс, а индекс 10-19 снова будет отображаться в 0-9 и т. Д.
Некоторые ключи будут сокращены до того же индекса, что и существующая запись в хеш-таблице. В этот момент фактические ключи сравниваются напрямую со всеми правилами, связанными со сравнением типов данных ключа (например, обычное сравнение строк). Если есть полное совпадение, вы либо игнорируете новые данные (они уже существуют), либо перезаписываете (заменяете старые данные для этого ключа), либо добавляете их (многозначная хеш-таблица). Если совпадения нет, это означает, что, хотя ключи хеша были идентичны, фактические ключи не были, вы обычно находите новое место для хранения этого ключа + данных.
Разрешение коллизий имеет много реализаций, и самый простой - просто перейти к следующему пустому элементу в массиве. Это простое решение имеет и другие проблемы, поэтому поиск правильного алгоритма разрешения также является хорошим примером для хеш-таблиц.
Хеш-таблицы также могут увеличиваться, если они заполнены полностью (или близки к ним), и это обычно делается путем создания нового массива нового размера, вычисления всех индексов еще раз и помещения элементов в новый массив в их новых местах.
Функция, которая уменьшает ключ до числа, не выдает линейное значение, т.е. «AAA» становится 1, затем «AAB» становится 2, поэтому хэш-таблица не сортируется по типичным значениям.
На эту тему также есть хорошая статья в Википедии, здесь .