轉載自http://220.181.18.117/longniao/blog/item/db0f2c1f663e0acba686695e.Html
什麼是散列表（哈希表）2007-12-05 23:32 散列方法不同於順序查找、二分查找、二叉排序樹及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為散列函數(Hash Function)。散列函數h的作用是壓縮待處理的下標范圍，使待處理的|U|個值減少到m個值，從而降低空間開銷。
② T為散列表(Hash Table)。
③ h(Ki)(Ki∈U)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。
④ 將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(Hashing)
3、散列表的沖突現象
（1）沖突
兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突(Collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。
【例】上圖中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的結點的存儲地址相同。
（2）安全避免沖突的條件
最理想的解決沖突的方法是安全避免沖突。要做到這一點必須滿足兩個條件：
①其一是|U|≤m
②其二是選擇合適的散列函數。
這只適用於|U|較小，且關鍵字均事先已知的情況，此時經過精心設計散列函數h有可能完全避免沖突。
（3）沖突不可能完全避免
通常情況下，h是一個壓縮映像。雖然|K|≤m，但|U|>m，故無論怎樣設計h，也不可能完全避免沖突。因此，只能在設計h時盡可能使沖突最少。同時還需要確定解決沖突的方法，使發生沖突的同義詞能夠存儲到表中。
（4）影響沖突的因素
沖突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大，表越滿，沖突的機會也越大。通常取α≤1。
