0

我正在尝试使用双散列将字符串键散列到散列表中。我做了类似的事情：

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;
}

主要部分是 . 之后的第 1 3 行do。我可以说如果我使用Double Hashing，它应该消除碰撞的可能性吗？size是我的哈希表的唯一键的总可能值

4

1 回答 1

2

所以我看到这里发生了两件事

  1. 使用两个不同的散列并将它们组合起来以尝试获得更分散的散列
  2. 如果哈希失败，请尝试更远的新位置

乍一看，这两种方法似乎都是减少哈希冲突的好方法。然而，仔细观察，这两者都陷入了真正的算法问题。

结合两个散列
散列算法被设计成在整数谱中分布得相当好。就像将两个随机数加在一起不会给您带来更多随机性一样，将两个散列加在一起不会让您获得更多分布。事实上，将两个相同分布加在一起总是会给你一些不均匀分布的东西。因此，任何一种使用相同底层算法的双散列策略都比单散列策略差。

尝试一个新点
如果第一个哈希值发生冲突，尝试一个新的哈希算法是很有诱惑力的。但是，这会导致算法的检索部分出现问题。当您将某些东西放入哈希中时，它会撞到另一个位置。然后，当您去检索该值时，它不存在。更糟糕的是，您是否找到它取决于第一个元素是否仍然存在。如果它已被删除，则无法判断您要查找的项目是否在更远的位置，或者它是否不存在。最终，一个 .contains 测试必须经过所有 200 次迭代才能确定它正在寻找的散列不存在。

最好的解决方案是使用 Java 提供的开箱即用的哈希。如果您遇到很多冲突，最好在哈希中使用较低的负载因子。这增加了桶的数量，并导致碰撞的可能性较小。

于 2011-11-12T02:33:35.600 回答