Хеширование строки для использования в хеш-таблице (Double Hashing) - PullRequest
Новая
       33

Хеширование строки для использования в хеш-таблице (Double Hashing)

0 голосов
/ 09 ноября 2011

Я пытаюсь использовать двойное хеширование для хеширования ключа String в хеш-таблицу.Я сделал что-то вроде: 

protected int getIndex(String key) {
  int itr = 0,
      size = this.values.length,
      index1,
      index2,
      index = 0;

  do {
    // do double hashing to get index for curr [itr] (iteration)
    index1 = Math.abs(key.hashCode()) % size;
    index2 = size - ((key + key + "#!@").hashCode() % size); # trying very hard to eliminate clash, but still fails ... TA and AT gets index 2 when size = 5
    index = (index1 + (itr * index2)) % size;

    // if itr > set threshold, exit
    itr++;
    if (itr > 200) {
      index = -1;
      break;
    }

    // once index found, exit loop
  } while (index > 0 && this.keys[index] != null && !this.keys[index].equals(key));

  return index;
}

Основная часть - это первые 3 строки после do.Могу ли я сказать, что если я использую Double Hashing, это должно исключить вероятность столкновения?size - это общее количество возможных значений уникальных ключей для моей хеш-таблицы

1 Ответ

2 голосов
/ 12 ноября 2011

Итак, я вижу здесь две вещи

  1. Использование двух разных хешей и объединение их в попытке получить более распределенный хеш
  2. Если хеш не удался, попробуйте новое место немного дальше

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

Объединение двух хешей
Алгоритмы хеширования разработаны так, чтобы быть достаточно хорошо распределенными по целочисленному спектру. Точно так же, как то, что сложение двух случайных чисел не дает ничего более случайного, добавление двух хешей вместе не дает вам более распределенного распределения. Фактически, добавление двух идентичных распределений ВСЕГДА даст вам что-то менее равномерное распределение. Таким образом, любая стратегия двойного хеширования, использующая тот же базовый алгоритм, хуже, чем одна стратегия хеширования.

Пробуем новое место
Соблазнительно попробовать алгоритм, который пробует новый хеш, если первый сталкивается. Однако это вызывает проблемы с поисковой частью алгоритма. Когда вы помещаете что-то в хеш, и оно попадает в другое место. Затем, когда вы идете, чтобы получить значение, его там нет. Еще хуже то, найдёте ли вы это или нет, зависит от того, есть ли первый элемент или нет. Если он был удален, то невозможно определить, находится ли искомый предмет дальше, или его просто нет. В конечном итоге тест .contains должен пройти все 200 итераций, прежде чем он сможет убедиться, что искомого хэша нет.

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

...