java - 压缩方法在哈希表中会做什么？

Question

对于作业，我必须为通用哈希表编写代码。在示例 Put 方法中，有两行：

int hash = key.hashCode(); // get the hashcode of the key
int index = compress(hash); // compress it to an index

我的理解是 hashCode 方法使用键来返回索引，并且您可以将键/值对放在该索引处的数组中。但是这里我们“压缩”哈希码来获取索引。这个方法有什么作用？它如何“压缩”哈希码？是否有必要和/或首选？

Answer 1

哈希码可以是介于 -2 ³¹和 2 ³¹ -1 之间的任何整数。那是大约 40 亿种不同的可能哈希码。例如，如果您有 40 个哈希表存储桶，则需要将这 40 亿个整数“压缩”到 0-39 范围内。

一种常见的方法是使用模运算符%。a % b返回除以 后的余a数b。例如，7 % 3 == 1。

int compress(int hash) {
    return hash % numBuckets;
}

注意：并非所有语言都如此，但在 Java中，结果的符号等于被除数的符号，这意味着我们上面的计算结果将始终为非负数。在 C 和 C++ 中，情况并非如此（符号由实现定义），因此需要特别注意正确处理负哈希值。

有关每种编程语言如何处理模数符号的详细信息，请参阅Wikipedia 上各种编程语言中的整数模运算符。

Answer 2

你也可以有负哈希码，而你想要的是一个大于或等于零的有效索引。compress 在应用模数运算符之前也会对哈希码进行 abs() 。