👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜歡《數據結構》部分筆記的小伙伴可以訂閱專欄，今后還會不斷更新。🧑?💻
感興趣的小伙伴可以點一下訂閱、收藏、關注！🚀
謝謝大家！🙏

散列表、散列函數

散列表（哈希表，Hash Table）：是一種數據結構

• 特點是：可以根據數據元素的關鍵字計算出它在散列表中的存儲地址

散列函數（哈希函數）：Addr = H(key)建立了 “關鍵字” -> “存儲地址” 的映射關系

理想情況下，在散列表中查找一個元素的時間復雜度為 $O(1)$
查找元素 19：根據散列函數計算出元素的存儲地址 $=19\%13=6$

沖突、同義詞

沖突（碰撞）：在散列表中插入一個數據元素時，需要根據關鍵字的值確定其存儲地址，若該地址已經存儲了其他元素，則稱這種情況為“沖突（碰撞）”

如何減少“沖突”？

• 構造更適合的散列函數，讓各個關鍵字盡可能地映射到不同的存儲位置，從而減少“沖突”

那么，如何構造更適合的散列函數呢？

• 拉鏈法（又稱鏈接法、鏈地址法）：把所有“同義詞”存儲在一個鏈表中
• 開放定址法：如果發生“沖突”，就給新元素找另一個空閑位置