1.什么是hash表？

答：簡單回答散列表，在hash結(jié)構(gòu)散列(分散)存放的一種數(shù)據(jù)集結(jié)構(gòu)。

2.如何散列排布，如何均勻排布？

答：取余運算

3.Java中如何實現(xiàn)？

答：hash&(h-1)

4.為什么hash&(h-1)=等價于hash%h

java的h(表長)一定是2的指數(shù)次冪，2的指數(shù)次冪2n

2n的結(jié)果：一定長這樣10000...(n個0)

2n-1的結(jié)果：一定這樣1111(n-1)個1

舉個例子：

當(dāng)h=16,對應(yīng)的二進制：00010000

h-1=15,對應(yīng)的二進制：00001111

可以知道所有的數(shù)與00001111進行&運算

高位都是0(進行位運行無論怎樣高位都是0)，低位取決于這個數(shù)的后四位(因此低位可能為0，也可能為1)

因此：(24-1)& hash=0 ~(24-1)之間=hash%(24)

只要知道是取余就行這種寫法就行。只是對cpu指令的優(yōu)化，

5.總結(jié)取余是為了散列分布，而hash桶的長度以2的指數(shù)被增長，可以使用位運算代替取余運算(顯示的告訴計算機采用位運算，但是你去取余計算機應(yīng)該也是這么用位去算的，.net里就是直接取余的，但表長也是2的指數(shù)倍)

hahs結(jié)構(gòu)的重點算法應(yīng)該是求hashcode，比如字符串，既要保證運算相同的串值的hash相同，又要使hash值盡量不同(不然也不能散列分布)，就要去遍歷串來計算hahscode，而hashcode一般占4字節(jié)

總結(jié)

以上是生活随笔為你收集整理的java hash取余_为什么Java的hash表的长度一直是2的指数次幂？为什么这个(hash(h-1)=hash%h)位运算公式等价于取余运算？...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。