HashTable

Hash Table 哈希表 哈希表是一種資料結構，計算機在對大量資料進行查找的時候會使用到這種資料結構。大家可以想象，在計算機中存儲的資料量那麼多，找起來就是對于機器來說也是煩人的事情，那麼有沒有辦法讓查找的速度變得很快呢？哈希表法就是一種方法。使資料和唯一（或幾個）位置相對應，這樣查找起來的速度就會大大提高（起碼比什麼都沒有硬找要好）。我們把這個函數關系H稱為哈希函數，把用哈希函數構造的表稱為哈希表，把利用哈希表進行查找這一過程有時也稱為哈希查找。    稱為散列法，也叫哈希法。由于通過更短的哈希值比用原始值進行資料庫搜尋更快，這種方法一般用來在資料庫中建立索引并進行搜尋，同時還用在各種解密算法中。     實（|K|比|U|小得多）。。     　散列方法是使用函數hash将U映射到表T[0..m-1]的下标上（m=O(|U|)）。進而達到在O(1)時間内就可完成查找。 其中：     ① hash：U→{0，1，2，…，m-1} ，通常稱h為散列函數(Hash Function)。散列函數h的作用是壓縮待處理的下标範圍，使待處理的|U|個值減少到m個值，進而降低空間開銷。     　②     　③ 亦稱散列值或散列位址)。 比如：有一組資料包括使用者名字、電話、住址等，為了快速的檢索，我們可以利用名字作為關鍵碼，hash規則就是把名字中每一個字的拼音的第一個字母拿出來，把該字母在26個字母中的順序值取出來加在一塊作為改記錄的位址。比如張三，就是Z+S＝26+19＝45。就是把張三存在位址為45處。         但是這樣存在一個問題，比如假如有個使用者名字叫做：周四，那麼計算它的位址時也是Z+S＝45，這樣它與張三就有相同的位址，這就是，也叫作！         沖突：兩個不同的關鍵字，由于散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突(Collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。         沖突基本上不可避免的，除非資料很少，我們隻能采取措施盡量避免沖突，或者尋找解決沖突的辦法。    　沖突的頻繁程度除了與h相關外，還與表的填滿程度相關。     　設m和n分别表示表長和表中填人的結點數，則将α=n/m定義為散清單的裝填因子(Load Factor)。α越大，表越滿，沖突的機會也越大。通常取α≤1。 散列函數的構造方法： 1、散列函數的選擇有兩條标準：簡單和均勻。     　 2、常用散列函數 （1）直接定址法：比如在一個0～100歲的年齡統計表，我們就可以把年齡作為位址。 （2）    　具體方法：先通過求關鍵字的平方值擴大相近數的差别，然後根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，是以由此産生的散列位址較為均勻。 （3）除留餘數法 取關鍵字被某個不大于哈希表表長m的數p除後所得餘數為哈希位址。 該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數（4）    　選擇一個随機函數，取關鍵字的随機函數值為它的散列位址，即          h(key)=random(key) 其中random為僞随機函數，但要保證函數值是在0到m-1之間。 處理沖突的方法： １、開放定址法 Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1) 其中m為表長，di為增量序列 如果di值可能為1,2,3,...m-1，稱。 如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2) 稱。