Двойное хэширование в C#. Разрешение коллизий

Рейтинг: 0Ответов: 1Опубликовано: 31.05.2011

Помогите написать нормальную хеш функцию. Все что я находил, мало похоже на двойное хеширование. И примеров нету.Вот единственное, что нашел:

  1. Установить i = h1(K)
  2. Если TABLE[i] пуст, то перейти к шагу 6, иначе, если по этому адресу искомый, алгоритм завершается.
  3. Установить c = h2(K)
  4. Установить i = i – c, если i < 0, то i = i + M.
  5. Если TABLE[i] пуст, то переход на шаг 6. Если искомое расположено по этому адресу, то алгоритм завершается, иначе возвращается на шаг 4.
  6. Вставка. Если N = M – 1, то алгоритм завершается по переполнению. Иначе увеличить N, пометить ячейку TABLE[i] как занятую и установить в нее значение ключа K.

Непонятно, какую брать функцию H1(k) и H2(k)

c# алгоритм хеширование
Источник: Stack Overflow на русском

Ответы

▲ 2

Видимо в задаче предполагается, что K это число (целое). Если это не так, то по K (например строка) надо вычислить целое число (допустим сумму всех байт строки, НО для практики это очень плохой алгоритм вычисления хэш-кода). Далее в задаче предполагается, что M это размер таблицы, а N количество уже помещенных в нее ключей.

Тогда хороший метод - это сделать размер таблицы простым числом. В этом случае (да, собственно, в любом) надо в качестве H1 взять остаток от деления K на M. i будет в интервале 0 - M-1 (т.е. внутри таблицы, что нам и надо).

Далее c - это шаг по таблице, он должен быть в интервале 1 - M-1, собственно выбор H2. 1 и M-1 тривиально (но плохо, будет высокое скучивание синонимов). Видимо для c можно попробовать остаток от деления K на Mm (ближайшее меньшее, чем M простое число), его можно вычислить один раз (при первом вызове) и запомнить.