java - 词频哈希表

Question

好的，我有一个项目需要我有一个动态哈希表来计算文件中单词的频率。我必须使用 java，但是，除了标准数组之外，我们根本不允许使用任何内置数据类型或内置类。此外，我不允许在互联网上使用任何已知速度很快的散列函数。我必须制作自己的哈希函数。最后，我的讲师还希望我的表从大小“1”开始，每次添加新键时大小加倍。

我的第一个想法是对组成单词的字母的 ASCII 值求和，然后用它来制作哈希函数，但具有相同字母的不同单词将等于相同的值。

我该如何开始？ ASCII 的想法是否走在正确的轨道上？

Answer 1

哈希表通常值和哈希之间的一对一映射。哈希表预计会发生冲突。也就是说，散列函数的域应该大于范围(即散列值)。然而，一般的想法是你想出一个哈希函数，其中碰撞的概率非常小。如果您的散列函数是统一的，即，如果您将其设计为每个可能的散列值具有相同的生成概率，那么您可以通过这种方式最大程度地减少冲突。

发生碰撞并不是世界末日。这只是意味着您必须搜索该散列的值列表。如果你的哈希函数很好，你的整体查找性能应该仍然是 O(1)。

生成哈希函数是一个独立的主题，没有唯一的答案。但是，您可以从处理字符串中字符的按位表示，并依次对它们执行某种卷积运算(旋转、移位、异或)开始，这是一个不错的起点。您可以根据一些初始种子值以某种方式执行这些操作，然后使用散列第一步的输出作为下一步的种子。通过这种方式，您最终可以放大卷积的效果。

例如，假设您得到字符 A，十六进制为 41，二进制为 0100 0001。您可以指定每个位来表示某种操作(可能位 0 为 0 时为 ROR，为 1 时为 ROL；位 1 为 0 时为 OR，为 1 时为 XOR，等等) .您甚至可以根据值本身决定要进行多少卷积。例如，您可以说低半字节指定您将向右旋转多少，而高半字节指定您将向左旋转多少。然后，一旦您获得了最终值，您将使用它作为下一个字符的种子。这些只是一些想法。发挥你的想象力，看看你会得到什么!