Что такое точно хеш-таблицы?

Википедия , кажется, дает довольно хороший ответ на то, что они из себя представляют.

Вы должны использовать их, когда хотите найти значения по некоторому индексу.

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

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

Примером хорошей хэш-функции является SHA1 или SHA256.

Допустим, у вас есть таблица пользователей базы данных. Столбцы: id , last_name , first_name , phone_number и address .

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

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

Мы могли бы найти запись пользователя в нашей базе данных следующим образом:

SELECT * FROM users
WHERE last_name = 'Adams'
AND first_name = 'Marcus'
AND address = '1234 Main St'
AND telephone_number = '555-1212';

Чтобы найти мою запись, нам нужно выполнить поиск в 4 разных столбцах, используя 4 разных индекса.

Однако вы можете создать новый столбец «хэш» и сохранить хеш-значение всех четырех столбцов вместе.

String myHash = myHashFunction("Marcus" + "Adams" + "1234 Main St" + "555-1212");

Вы можете получить хеш-значение вроде AE32ABC31234CAD984EA8 .

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

SELECT * FROM users
WHERE hash_value = 'AE32ABC31234CAD984EA8';

Когда у нас есть идентификатор запрошенного пользователя, мы можем использовать это значение для поиска связанных данных в других таблицах.

Идея состоит в том, что хеш-функция разгружает работу с сервера базы данных.

Столкновения маловероятны. Если у двух пользователей один и тот же хэш, скорее всего, у них одинаковые данные.

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

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