单词字典的双重哈希效率

Question

简单地说，我有一个单词字典，我正在将它们添加到散列中 table。

我正在使用双哈希（不是传统方法），下面的方法产生了最好的结果。

    public static int getHashKey(String word) {

        int index = 0;

        for(int i = 0; i<word.length(); i++){

            index += Math.pow(4,  i)*((int)word.charAt(i));
            index = index % size;
        }
        return index;
    }

    public static int getDoubleHashKey(String word) {

        int jump = 1;

        for(int i = 0; i<word.length(); i++){

            jump = jump * word.charAt(i);
            jump = jump % size;
        }
        return jump;

    }

这给了我 127,000 次碰撞。我还有一个 2 倍素数哈希 table 大小，它无法更改。

Double Hashing算法有什么改进的地方吗？（以上2种方法之一）。

我知道这取决于我们在散列中存储的内容 table 等。但是是否有任何直观的方法或一些更普遍适用的技巧可以避免更多的冲突。

Answer 1

我运行一个关于大约 336 531 个条目的字典的小 Scala 程序。版本 2 (118 142) 的冲突明显少于版本 1 (305 431)。请注意，版本 2 接近最佳碰撞次数，因为 118 142 + 216 555 = 334 697，因此 334 697/336 531 = 0-216555 运行ge 中使用的值的 99,46%。在循环 之外使用模数确实改进了您的散列方法。

import scala.io.Source object Hash extends App { val size = 216555 def doubleHashKey1(word: String) = { var jump = 1; for (ch <- word) { jump = jump * ch; jump = jump % size; } jump } def doubleHashKey2(word: String) = { var jump = 1; for (ch <- word) jump = jump * ch; jump % size; } def countCollisions(words: Set[String], hashFun: String => Int) = words.size - words.map(hashFun).size def readDictionary(path: String) = Source.fromFile(path).getLines.toSet val dict = readDictionary("words.txt") println(countCollisions(dict,doubleHashKey1)) println(countCollisions(dict,doubleHashKey2)) }

为了处理整数溢出，您必须使用不同的（但实现起来很简单）方法来计算模数，以便 return 正值。要做的另一项测试是查看碰撞是否静态分布良好。

单词字典的双重哈希效率

Double Hashing efficiency with word dictionary

java

dictionary

hash

double-hashing