的魔法)
哈希表 - 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ā)表了第一篇學術(shù)論文韋斯利·彼得森Wesley Peterson1957年研究了開放尋址和線性探測克努斯在TAOCP中系統(tǒng)化了整個理論當時的處境1953年計算機存儲昂貴IBM的大型機用磁鼓drum存儲數(shù)據(jù)。每次查找都要按順序檢索既慢又占用處理器時間。盧恩的洞察是與其搜索不如直接計算出目標在哪里。When何時- 什么時候發(fā)明的時間1953年盧恩的內(nèi)部備忘錄1957年彼得森學術(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且哈希沖突增加了復雜性。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ù)學分析 自然語言需求定義需求名稱實現(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已刪除惰性刪除物理刪除會斷開線性探測鏈導致查找失敗驗收標準編號測試場景預期結(jié)果驗證方式1插入(10,100),(20,200),(30,300)大小為3size檢查2查找存在的鍵返回對應值三個鍵全部查找3查找不存在的鍵(99)返回false檢查返回值4更新已有鍵(10, 999)值變?yōu)?99大小不變查找驗證5刪除key20后查找返回false惰性刪除6刪除后插入DELETED槽復用成功插入查找新鍵7哈希碰撞3個鍵mod capacity相同全部可查三鍵查找 C語言實現(xiàn)文件對應文件: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)存 072哈希表 - O(1)的魔法
哈希表 - 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ā)表了第一篇學術(shù)論文韋斯利·彼得森Wesley Peterson1957年研究了開放尋址和線性探測克努斯在TAOCP中系統(tǒng)化了整個理論當時的處境1953年計算機存儲昂貴IBM的大型機用磁鼓drum存儲數(shù)據(jù)。每次查找都要按順序檢索既慢又占用處理器時間。盧恩的洞察是與其搜索不如直接計算出目標在哪里。When何時- 什么時候發(fā)明的時間1953年盧恩的內(nèi)部備忘錄1957年彼得森學術(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且哈希沖突增加了復雜性。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ù)學分析 自然語言需求定義需求名稱實現(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已刪除惰性刪除物理刪除會斷開線性探測鏈導致查找失敗驗收標準編號測試場景預期結(jié)果驗證方式1插入(10,100),(20,200),(30,300)大小為3size檢查2查找存在的鍵返回對應值三個鍵全部查找3查找不存在的鍵(99)返回false檢查返回值4更新已有鍵(10, 999)值變?yōu)?99大小不變查找驗證5刪除key20后查找返回false惰性刪除6刪除后插入DELETED槽復用成功插入查找新鍵7哈希碰撞3個鍵mod capacity相同全部可查三鍵查找 C語言實現(xiàn)文件對應文件: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)存