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

Question

• Кто они и как работают?
• Где они используются?
• Когда я должен (не) использовать их?

Я слышал это слово снова и снова, но я не знаю его точного значения.

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

(Обратите внимание: это не моя домашняя работа; я тоже хожу в школу, но нас учат только БЕЙСИКУ по информатике)

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

Допустим, у вас есть таблица базы данных пользователей. Столбцы id, last_name, first_name, telephone_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';

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

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

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