在許多書籍、教學(xué)大綱、教程中，我看到找到一個項目的合適單元格的一個好選擇是計算單元格的數(shù)量： item.hash()%(n-1) = # of the bucket.但是為什么要提到這個特定的表達呢？倒數(shù)(n-1)%item.hash() = # of the bucket與它有何不同？PS我知道Java HashMap使用(n - 1) & hash，我只想抓住這兩種方法之間稀疏鍵的區(qū)別。
3 回答
四季花海
TA貢獻1811條經(jīng)驗 獲得超5個贊
將運算符模數(shù)%視為通過在較小范圍內(nèi)減少一組數(shù)字來均勻分布一組數(shù)字的方法。這組數(shù)字當然是輸入鍵的哈希碼。小范圍是表的容量。
當您想在小表中分配索引以存儲大數(shù)字時，這是一種有用的技術(shù)。
逆運算聽起來很奇怪（而且沒用）：考慮到哈希碼是大數(shù)且 n 很小，n % hash將返回 always n，因此它根本沒有興趣。
Javahash & (length-1)確實通過 選擇索引，這在算術(shù)上并不等同于hash % length，但它是一種替代 - 并且比模數(shù) - 減少和分發(fā)的公式便宜（歸功于@Zabuza）。
FFIVE
TA貢獻1797條經(jīng)驗 獲得超6個贊
桶的倒數(shù) (n-1)%item.hash() = # 與它有何不同？
基本上是行不通的。
該表達式需要將哈希碼縮減為 0 .. n - 1 范圍內(nèi)的值，以便將其用作大小為 n 的數(shù)組的下標。
但是“逆”函數(shù)不會這樣做。因此，如果您嘗試使用它，（所謂的）桶下標會給出異常，因為對于 Javaint類型范圍內(nèi)的大多數(shù) h 值， h % (n - 1) > (n - 1) 或 < 0 。
正如@Zubuza 指出的那樣，余數(shù) (%) 和除法 (/) 不是可交換的。
添加回答
舉報
0/150
提交
取消