哈希表 - O(1)的魔法讓查找無需比較072開放尋址哈希表即時(shí)查找的魔法 5W1H 發(fā)明者故事Who何人- 發(fā)明者是誰發(fā)明者漢斯·彼得·盧恩Hans Peter Luhn1896-1964IBM研究工程師背景盧恩是德裔美國人他更廣為人知的發(fā)明是信用卡校驗(yàn)碼Luhn算法1954年至今每次你刷卡都在用他的算法。他在IBM工作期間于1953年提出了將數(shù)據(jù)鍵映射到內(nèi)存地址的哈希思想——當(dāng)時(shí)他稱之為計(jì)算尋址computed addressing。其他獨(dú)立發(fā)明者阿諾德·達(dá)姆Arnold Dumey1956年發(fā)表了第一篇學(xué)術(shù)論文韋斯利·彼得森Wesley Peterson1957年研究了開放尋址和線性探測(cè)克努斯在TAOCP中系統(tǒng)化了整個(gè)理論當(dāng)時(shí)的處境1953年計(jì)算機(jī)存儲(chǔ)昂貴IBM的大型機(jī)用磁鼓drum存儲(chǔ)數(shù)據(jù)。每次查找都要按順序檢索既慢又占用處理器時(shí)間。盧恩的洞察是與其搜索不如直接計(jì)算出目標(biāo)在哪里。When何時(shí)- 什么時(shí)候發(fā)明的時(shí)間1953年盧恩的內(nèi)部備忘錄1957年彼得森學(xué)術(shù)論文詳細(xì)分析線性探測(cè)時(shí)代背景IBM 7011952年和7041954年商用大型機(jī)投入使用內(nèi)存很貴每個(gè)字節(jié)都寶貴減少查找時(shí)間是硬需求匯編語言時(shí)代程序員直接操作內(nèi)存地址Where何地- 在哪里發(fā)明的地點(diǎn)IBM 圣何塞研究實(shí)驗(yàn)室San Jose Research Laboratory環(huán)境戰(zhàn)后美國工業(yè)界的黃金時(shí)期IBM幾乎壟斷計(jì)算機(jī)市場(chǎng)研究投入充裕。What何事- 發(fā)明了什么數(shù)據(jù)結(jié)構(gòu)哈希表Hash Table核心思想哈希函數(shù)將鍵key映射到數(shù)組下標(biāo)index hash(key) % capacity直接存取通過計(jì)算出的下標(biāo)直接存儲(chǔ)/訪問數(shù)據(jù)無需比較沖突處理多個(gè)鍵映射到同一下標(biāo)時(shí)的解決方案鏈?zhǔn)椒?開放尋址哈希名字的由來hash在英語中意為切碎混合——就像把鍵打碎成一個(gè)數(shù)字下標(biāo)。兩種主要沖突解決方案鏈?zhǔn)椒–haining同一下標(biāo)的元素用鏈表連接開放尋址Open Addressing沖突時(shí)探測(cè)下一個(gè)空槽線性探測(cè)、二次探測(cè)、雙重哈希Why何因- 為什么發(fā)明問題二分查找需要O(log n)數(shù)據(jù)庫查找需要O(1)。洞察如果我們知道一本詞典的目標(biāo)詞在哪一頁就可以直接翻到那頁——不需要逐頁翻。哈希函數(shù)就是直接計(jì)算出目標(biāo)在哪里的魔法。代價(jià)需要額外空間負(fù)載因子1且哈希沖突增加了復(fù)雜性。How何果- 如何實(shí)現(xiàn)有什么影響負(fù)載因子Load Factor n/mn為元素?cái)?shù)m為槽數(shù) 0.5沖突少快但浪費(fèi)空間0.7-0.8工程上常用的平衡點(diǎn)0.9沖突急劇增多性能劣化歷史影響Python的dict字典是哈希表是語言核心Java的HashMapGo的mapC的unordered_map數(shù)據(jù)庫的索引結(jié)構(gòu)哈希索引編譯器的符號(hào)表緩存系統(tǒng)Redis, Memcached的核心數(shù)據(jù)結(jié)構(gòu)克努斦在TAOCP第三卷6.4節(jié)提供了完整的數(shù)學(xué)分析 自然語言需求定義需求名稱實(shí)現(xiàn)開放尋址哈希表線性探測(cè)惰性刪除支持整數(shù)鍵值對(duì)功能需求創(chuàng)建指定初始容量內(nèi)部取下一個(gè)質(zhì)數(shù)分配內(nèi)存插入/更新hash(key)定位線性探測(cè)找空槽已存在則更新值查找同樣的探測(cè)序列遇EMPTY停止遇DELETED繼續(xù)刪除惰性刪除標(biāo)記DELETED不物理移除防止斷開探測(cè)鏈負(fù)載因子監(jiān)控超過0.7時(shí)發(fā)出警告約束條件容量用質(zhì)數(shù)減少哈希沖突三種槽狀態(tài)EMPTY從未用、OCCUPIED有數(shù)據(jù)、DELETED已刪除惰性刪除物理刪除會(huì)斷開線性探測(cè)鏈導(dǎo)致查找失敗驗(yàn)收標(biāo)準(zhǔn)編號(hào)測(cè)試場(chǎng)景預(yù)期結(jié)果驗(yàn)證方式1插入(10,100),(20,200),(30,300)大小為3size檢查2查找存在的鍵返回對(duì)應(yīng)值三個(gè)鍵全部查找3查找不存在的鍵(99)返回false檢查返回值4更新已有鍵(10, 999)值變?yōu)?99大小不變查找驗(yàn)證5刪除key20后查找返回false惰性刪除6刪除后插入DELETED槽復(fù)用成功插入查找新鍵7哈希碰撞3個(gè)鍵mod capacity相同全部可查三鍵查找 C語言實(shí)現(xiàn)文件對(duì)應(yīng)文件:hash_table.c編譯運(yùn)行:gcc-ohash_table_test hash_table.c ./hash_table_test核心函數(shù):ht_create(capacity)- 創(chuàng)建哈希表ht_insert(ht, key, value)- 插入/更新ht_get(ht, key, value)- 查找ht_delete(ht, key)- 惰性刪除ht_free(ht)- 釋放內(nèi)存