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