哈希衝突：哈希表爲什麼會衝突？如何解決？
哈希表通過哈希函數將鍵映射到數組位置，但若不同鍵映射到同一位置則產生哈希衝突，核心原因是鍵數量遠超數組容量或哈希函數不均。解決衝突的核心是讓衝突鍵“各佔位置”，常見方法有： 1. **鏈地址法（拉鍊法）**：最常用，每個數組位置爲鏈表，衝突鍵依次掛在對應鏈表後，如鍵5、1、9衝突時，鏈表爲5→1→9。查找時遍歷鏈表，實現簡單且空間利用率高。 2. **開放定址法**：衝突時從後續位置找空位，包括線性探測（步長1）、二次探測（步長平方）、雙重哈希（多函數映射），但易聚集或實現複雜。 3. **公共溢出區**：主數組存無衝突鍵，衝突鍵放入溢出區，查找需主區+溢出區遍歷，空間分配難。 解決衝突需依場景選擇，鏈地址法因高效通用被廣泛採用，理解衝突及解決方法可優化哈希表性能。
閱讀全文哈希函數：哈希函數如何生成哈希值？初學者必知
哈希函數是將任意長度輸入轉爲固定長度哈希值的“翻譯器”，哈希值即數據的“身份證號”。其核心特點：固定長度（如MD5爲32位十六進制字符）、單向不可逆（無法由哈希值反推原數據）、近似唯一（碰撞概率極低）、雪崩效應（輸入微小變化致哈希值鉅變）。生成過程分三步：輸入預處理爲二進制，分段數學運算，合併結果。與加密函數不同，哈希單向無需密鑰，加密可逆需密鑰。應用廣泛：文件校驗（比對哈希值防篡改）、密碼存儲（存哈希值保安全）、數據索引及分佈式系統數據分佈。哈希如數據指紋，關鍵特性使其在安全與校驗中不可或缺。
閱讀全文哈希表怎麼存數據？哈希函數讓查找變簡單
文章用找書類比引出問題：順序查找數據（如數組）效率低，哈希表是高效存儲工具。哈希表核心是哈希函數，將數據映射到“桶”（數組位置），實現快速存取。哈希函數把數據轉爲哈希值（桶編號），如學號取後兩位得哈希值。存儲時，先算哈希值定位桶，若多數據哈希值相同（衝突），用鏈表法（桶內掛鏈表）或開放尋址法（找下一個空桶）解決。查找時，直接算哈希值定位桶，再在桶內查找，無需遍歷全部數據，速度極快。哈希表應用廣泛（如通訊錄、緩存），核心是用哈希函數將查找從“翻遍”轉爲“直達”。
閱讀全文