Ⅰ Hash表處理沖突的方法
處理哈希表中的沖突是關鍵任務，當關鍵字映射到的哈希地址已被佔用時，需要尋找一個"空"的位置。常見的解決沖突策略有開放定址法、拉鏈法和建立公共溢出區。
開放定址法分為幾種變體：線性探查法，從初始哈希地址開始，逐個嘗試直到找到空位置或表滿。線性探查法有簡單線性、二次探測和偽隨機探測。線性探查要求裝填因子α不大於0.5至0.9，以確保高效性。二次探查法雖然避免了線性探查的聚集現象，但可能錯過整個空間。雙重散列法使用兩個散列函數，效果更佳。
拉鏈法則是通過鏈接沖突的哈希地址，形成單鏈表，散列表的長度m決定了單鏈表的長度。拉鏈法允許較高的裝填因子，但一般保持在1以下。
建立公共溢出區方法是在哈希表之外設置一個額外的存儲空間，用於存放沖突的記錄。這種方法對哈希函數的值域要求明確，同時對裝填因子沒有嚴格限制。
性能分析顯示，散列表的查找時間取決於沖突和哈希函數的質量。查找成功的平均查找長度優於順序和二分查找，而查找不成功的長度則取決於沖突的數量。散列表的平均查找長度與裝填因子α有關，可以通過選擇合適的α來優化性能。對比其他查找方法，如順序查找和二分查找，散列法不依賴關鍵字比較，查找時間期望為常數時間o(1)。
以h(k) = (3k) % 11和線性探測再散列為例，構造哈希表並計算等概率下查找不成功的平均查找長度，需要具體計算和分析，這里略去具體數值的計算過程。
hashing定義了一種將字元組成的字元串轉換為固定長度(一般是更短長度)的數值或索引值的方法，稱為散列法，也叫哈希法。由於通過更短的哈希值比用原始值進行資料庫搜索更快，這種方法一般用來在資料庫中建立索引並進行搜索，同時還用在各種解密演算法中。