Как Perl разрешает возможные коллизии хешей в хешах?

Question

Как мы знаем, perl реализует свой тип 'hash' в виде таблицы с вычисляемыми индексами, где эти индексы являются усеченными хэшами.

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

Тогда : Как интерпретатор Perl обрабатывает, когда обнаруживает, что ключ сгенерировал тот же хэш, что и другой ключ?Он вообще это обрабатывает?

Примечание : Речь идет не об алгоритме хеширования, а о разрешении коллизий в реализации хеш-таблицы.

Answer 1

Perl-хеш - это массив связанных списков.

+--------+       +--------+
|       -------->|        |
+--------+       +--------+
|        |       | key1   |
+--------+       +--------+
|      ------+   | val1   |
+--------+   |   +--------+
|        |   |
+--------+   |   +--------+     +--------+
             +-->|       ------>|        |
                 +--------+     +--------+
                 | key2   |     | key3   |
                 +--------+     +--------+
                 | val2   |     | val3   |
                 +--------+     +--------+

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

Это означает, что худший случай для поиска - O (N).Так почему люди говорят, что это O (1)?Вы могли бы заявить, что если бы удерживали список от превышения некоторой постоянной длины, и это то, что делает Perl.Для этого используются два механизма:

• Увеличение количества сегментов.
• Возмущающий алгоритм хеширования.

Удвоение количества сегментов должно делитьколичество записей в данной половине в среднем.Например,

305419896 % 4 = 0 and 943086900 % 4 = 0
305419896 % 8 = 0 and 943086900 % 8 = 4

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

Answer 2

Наборы пар ключ-значение, в которых ключи выдают одно и то же значение хеш-функции, хранятся вместе в связанном списке.Подробная информация доступна в hv.c.