hash()%n 和 n%hash() 有什么区别

Question

在许多书籍、教学大纲、教程中，我看到找到一个项目的合适单元格的一个好选择是计算单元格的数量： item.hash()%(n-1) = # of the  bucket.

但是为什么要提到这个特定的表达呢？

倒数(n-1)%item.hash() = # of the  bucket与它有何不同？

PS我知道Java HashMap使用(n - 1) & hash，我只想抓住这两种方法之间稀疏键的区别。

Answer 1

将运算符模数%视为通过在较小范围内减少一组数字来均匀分布一组数字的方法。这组数字当然是输入键的哈希码。小范围是表的容量。当您想在小表中分配索引以存储大数字时，这是一种有用的技术。逆运算听起来很奇怪（而且没用）：考虑到哈希码是大数且 n 很小，n % hash将返回 always n，因此它根本没有兴趣。Javahash & (length-1)确实通过 选择索引，这在算术上并不等同于hash % length，但它是一种替代 - 并且比模数 - 减少和分发的公式便宜（归功于@Zabuza）。

Answer 2

桶的倒数 (n-1)%item.hash() = # 与它有何不同？基本上是行不通的。该表达式需要将哈希码缩减为 0 .. n - 1 范围内的值，以便将其用作大小为 n 的数组的下标。但是“逆”函数不会这样做。因此，如果您尝试使用它，（所谓的）桶下标会给出异常，因为对于 Javaint类型范围内的大多数 h 值， h % (n - 1) > (n - 1) 或 < 0&nbsp;。正如@Zubuza 指出的那样，余数 (%) 和除法 (/) 不是可交换的。