二級hash

一級hash函數是固定的。

每個槽有自己的二級hash函數。 且 二級hash長度是該槽內相同element個數的平方。 這樣能保證二級hash無碰撞發生。

一級hash中， 某個槽內有n個元素， 對應的二級hash長度為m=n^2;

這n個元素在該二級hash中的碰撞的pair有 C(n,2)； 出現碰撞的概率為1/m

因此， 碰撞次數的期望就是 C(n, 2) * 1/m < 1/2

???????????????????

整個hash表空間 與 待存儲的元素空間成正比。 O(n)

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的二级hash。。？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。