hash（個人理解 ）

解決沖突
鏈接法，開放尋址

全域散列

  1. 如果從H中隨機選擇一個散列函數(shù)，當關(guān)鍵字k不等于l時，兩者的沖突是多少？
    1.關(guān)鍵字k，選一個散列函數(shù)，然后散列進入T的一個槽中
    2.兩個鍵碰撞的概率
    關(guān)鍵字l（不確定），選一個散列函數(shù)，然后對于l也散列到和k同一個槽中，此時散列函數(shù)確定，而且要散列到同一個槽中（也就是結(jié)果和一樣）
    這樣如果在U中有一個值可以根據(jù)這個散列函數(shù)并散列到指定的槽中，要么在U中有這個值（<= 1/m 查完最后一個的話是1/m）

  2. 與其他鍵沖突的期望？
    C_x 表示除了x外 其他鍵和它碰撞次數(shù)的總數(shù)
    c_xy表示 兩個鍵碰撞 （當碰撞的時候c_xy的值加1，不碰撞保持）
    結(jié)論：E(c_xy) = 1/m （概率都相等，期望也就和概率一樣了） 和

E(C_x) = (n-1)/m

為什么選雙向鏈表？（不考慮首尾是空指針的情況）
.png
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容