一、基本原理：
假設我們使用一個下標范圍比較大的數組來存儲元素。設計一個函數（哈希函數，也叫做散列函數），使得每個元素的關鍵字經過函數運算得到一個函數值（即數組下標），於是用這個數組單元來存儲這個元素。通過函數值即數組下標就可以查找數據元素了。
直接定址”與“解決沖突”是哈希表的兩大特點。
二、優點：
把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的內存。然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。
三、構造方法：
盡力避免沖突但函數也需要易於編碼，即易於實現。
１、直接定址法
例：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。但這種方法效率不高,時間復雜度是O(1),空間復雜度是O(n),n是關鍵字的個數
２、數字分析法
３、平方取中法
取關鍵字平方後的中間幾位為哈希地址。
４、折疊法
將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為哈希地址，這方法稱為折疊法。
這種方法適用於關鍵字位數較多，而且關鍵字中每一位上數字分布大致均勻的情況。
折疊法中數位折疊又分為移位疊加和邊界疊加兩種方法，移位疊加是將分割後是每一部分的最低位對齊，然後相加；邊界疊加是從一端向另一端沿分割界來回折疊，然後對齊相加。
例：當哈希表長為1000時，關鍵字key=110108331119891，允許的地址空間為三位十進制數，則這兩種疊加情況如下
移位疊加891+119+331+108+110=(1)559
邊界疊加 891+911+331+801+110=(3)044
用移位疊加得到的哈希地址是559，而用邊界疊加所得到的哈希地址是44。如果關鍵字不是數值而是字符串，則可先轉化為數。轉化的辦法可以用ASCⅡ字符或字符的次序值。
５、除留余數法
取關鍵字被某個不大於哈希表表長m的數p除後所得余數為哈希地址。H(key)=key MOD p (p<=m)
６、隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即H(key)=random(key) ,其中random為隨機函數。通常用於關鍵字長度不等時采用此法。
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-09/106450p2.htm
