散列技術的方法指的是不同於順序查找、二分查找、二叉排序樹及B-樹上的查找。它不以關鍵字的比較為基本操作，採用直接定址技術。在理想情況下，無須任何比較就可以找到待查關鍵字，查找的期望時間為O(1)。
基本介紹
- 中文名：散列技術
- 專業：計算機科學技術
- 相似方法：順序查找、二分查找等
- 工具：散列表
散列表的概念
1、散列表
設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K（|K|比|U|小得多）。
散列方法是使用函式h將U映射到表T[0..m-1]的下標上（m=O(|U|)）。這樣以U中關鍵字為自變數，以h為函式的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。
其中：
①h：U→{0，1，2，…，m-1}，通常稱h為散列函式(HashFunction)。散列函式h的作用是壓縮待處理的下標範圍，使待處理的|U|個值減少到m個值，從而降低空間開銷。
②T為散列表(HashTable)。
③h(Ki)(Ki∈U)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。
④將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(Hashing)
3、散列表的衝突現象
（1）衝突
兩個不同的關鍵字，由於散列函式值相同，因而被映射到同一表位置上。該現象稱為衝突(Collision)或碰撞。發生衝突的兩個關鍵字稱為該散列函式的同義詞(synonym)。
【例】上圖中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的結點的存儲地址相同。
（1）衝突
兩個不同的關鍵字，由於散列函式值相同，因而被映射到同一表位置上。該現象稱為衝突(Collision)或碰撞。發生衝突的兩個關鍵字稱為該散列函式的同義詞(synonym)。
【例】上圖中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的結點的存儲地址相同。
（2）安全避免衝突的條件
最理想的解決衝突的方法是安全避免衝突。要做到這一點必須滿足兩個條件：
①其一是|U|≤m
②其二是選擇合適的散列函式。
這隻適用於|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函式h有可能完全避免衝突。
最理想的解決衝突的方法是安全避免衝突。要做到這一點必須滿足兩個條件：
①其一是|U|≤m
②其二是選擇合適的散列函式。
這隻適用於|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函式h有可能完全避免衝突。
（3）衝突不可能完全避免
通常情況下，h是一個壓縮映像。雖然|K|≤m，但|U|>m，故無論怎樣設計h，也不可能完全避免衝突。因此，只能在設計h時儘可能使衝突最少。同時還需要確定解決衝突的方法，使發生衝突的同義詞能夠存儲到表中。
通常情況下，h是一個壓縮映像。雖然|K|≤m，但|U|>m，故無論怎樣設計h，也不可能完全避免衝突。因此，只能在設計h時儘可能使衝突最少。同時還需要確定解決衝突的方法，使發生衝突的同義詞能夠存儲到表中。
（4）影響衝突的因素
衝突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(LoadFactor)。α越大，表越滿，衝突的機會也越大。通常取α≤1
衝突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(LoadFactor)。α越大，表越滿，衝突的機會也越大。通常取α≤1
