hash表原理？解決沖突方式？

概念：

哈希表(散列表)通過將關(guān)鍵碼key映射到表中的某個位置上來存儲元素，然后根據(jù)關(guān)鍵碼來訪問元素。

常用hash函數(shù)

  • 除留余數(shù)法
  • 線性探測
  • 二次探測
  • 開鏈法，在大部分情況下基本就是用開鏈法

解決方式

  1. 開放地址法
    基本思想是：當(dāng)發(fā)生地址沖突時，按照某種方法繼續(xù)探測哈希表中的其他存儲單元，直到找到空位置為止。
    如：線性探測再散列、二次探測再散列

  2. 再哈希法
    當(dāng)發(fā)生沖突時，使用第二個、第三個、哈希函數(shù)計算地址，直到無沖突時。缺點：計算時間增加。比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再沖突，第三位，直到不沖突為止。

  3. 鏈地址法
    將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。

  4. 建立一個公共溢出區(qū)
    假設(shè)哈希函數(shù)的值域為[0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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