字符串的16位均匀哈希函数

Question

我有大约5万个单词需要映射到16位数字，并寻找适用于j2me的哈希函数。更具体地说，我正在寻找符合以下标准的哈希函数：

1. 少量（或没有）冲突
2. CPU负载轻
3. 我现在拥有所有的单词
4. 雪崩效应并不重要，因为这不涉及安全性，只是一个查找表。

我测试了Java String.hashCode()、MurmurHash、Jenkins one at a time和一些简单的手工算法，但它们都至少有30%的冲突。

对于小型移动设备来说，最小完美哈希似乎负载过重。 有谁能帮助我吗？

注意：正如您所知，Murmur算法需要种子，不同的种子具有不同的均匀性。 我该如何找到最小冲突的种子？

谢谢您的帮助！

- mohsenof

---

其他数据结构是否适合您？例如 Trie？ - Omri Barel

这可能会对您感兴趣：已知键集的最快字符串键查找和有向无环字图。 - Jiri Kriz

@Omri Barel：感谢您的评论。我想要尽量减少内存访问。我猜如果我能找到一个好的哈希函数，它会更快，并且访问内存更少。 - mohsenof

Answer 1

这是我在 C# 中用来将文件名映射为 16 位数字的函数。在我的测试中，它比 Pearson 哈希表现更好。

    public static unsafe int Get16BitHash(string str)
    {
        int hash = 0;
        int len = str.Length;

        fixed (char* ch = str)
        {
            for (int i = 0; i < len; i++)
            {
                hash = hash + ((hash) << 5) + *(ch + i) + ((*(ch + i)) << 7);
            }
        }

        return ((hash) ^ (hash >> 16)) & 0xffff;
    }

- ialiashkevich

---

如果您返回的数据类型是int，那么仍然会返回32位数字，而不是16位？ - Jake Drew

出于性能原因，最好使用32位整数进行计算。返回的32位整数仅具有低16位，其余高16位均为零。 - ialiashkevich

Answer 2

这个答案可能有点晚了，但是作为参考，MurmurHash 3足够快以满足您的速度要求。然而，由于您所施加的限制，碰撞会相当普遍，因为16位可以表示65536个值的范围，您的50000个单词会产生一些碰撞。

解决方案：

• 使用20位以上的键（使用32位，在几百万个样本中有一个碰撞）
• 编写一个测试程序来查找适合16位的种子，以下是一些有用的工具：http://code.google.com/p/smhasher/

- Andrei

Answer 3

你可以考虑一下老式的CRC。它们非常快速且碰撞较少。只是可能没有16位那么精确，就像这个实验所示。但无论如何，你可以尝试一下，也许对你的目的已经足够好了。

- emboss