Классификация хеш-функции

9

В интернете я сталкивался с таким вопросом:

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

с ответами вроде

  • Прямой метод
  • Метод вычитания
  • Метод деления по модулю
  • Цифровой метод извлечения
  • Метод средней площади
  • Складной метод
  • Псевдослучайный метод

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

maaartinus
источник

Ответы:

4

Это методы превращения хеш-кода в индекс массива, который содержит значения. Допустим, у вас есть хеш-код 0x12345678. Очень большое число, и у вас вряд ли будет массив такого размера. Если вы делаете, вы можете просто сделать

Value = array[0x12345678];

И будет сделано (прямой метод).

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

Value = array[hashcode & 0xffff];

Или мод хеш-код против размера массива

Value = array[hashcode % array.size()]; // modulo division

И т. Д.

Изменить: эта ссылка может помочь

Джеймс
источник
Спасибо, вот и все - ссылка, кажется, является источником этого ***. Это по-прежнему не имеет смысла, поскольку они смешивают много вещей: 1. вычисление хэш-кода по ключу (например, свертывание и сложение), 2. улучшение (= размазывание) хэша (например, середина квадрата), 3. отображение хэш индекса (например, модуль, "&").
Maaartinus