時間複雜度上，紅黑樹在平均情況下插入，查找以及刪除上都達到了lgN的時間複雜度。 那麼有沒有查找效率更高的數據結構呢，答案就是本文接下來要介紹了散列表，也叫哈希表(Hash Table) 什麼是哈希表 哈希表就是一種以 鍵-值(key-indexed) 存儲數據的結構，我們只要輸入待查找的值即key ...
時間複雜度上，紅黑樹在平均情況下插入，查找以及刪除上都達到了lgN的時間複雜度。
那麼有沒有查找效率更高的數據結構呢，答案就是本文接下來要介紹了散列表，也叫哈希表(Hash Table)
什麼是哈希表
哈希表就是一種以 鍵-值(key-indexed) 存儲數據的結構，我們只要輸入待查找的值即key，即可查找到其對應的值。
哈希的思路很簡單，如果所有的鍵都是整數，那麼就可以使用一個簡單的無序數組來實現：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對於簡單的鍵的情況，我們將其擴展到可以處理更加複雜的類型的鍵。
使用哈希查找有兩個步驟:
- 使用哈希函數將被查找的鍵轉換為數組的索引。在理想的情況下，不同的鍵會被轉換為不同的索引值，但是在有些情況下我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理衝突
- 處理哈希碰撞衝突。有很多處理哈希碰撞衝突的方法，本文後面會介紹拉鏈法和線性探測法。
哈希表是一個在時間和空間上做出權衡的經典例子。如果沒有記憶體限制，那麼可以直接將鍵作為數組的索引。那麼所有的查找時間複雜度為O(1)；如果沒有時間限制，那麼我們可以使用無序數組併進行順序查找，這樣只需要很少的記憶體。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調整哈希函數演算法即可在時間和空間上做出取捨。
哈希函數
哈希查找第一步就是使用哈希函數將鍵映射成索引。這種映射函數就是哈希函數。如果我們有一個保存0-M數組，那麼我們就需要一個能夠將任意鍵轉換為該數組範圍內的索引（0~M-1）的哈希函數。哈希函數需要易於計算並且能夠均勻分佈所有鍵。比如舉個簡單的例子，使用手機號碼後三位就比前三位作為key更好，因為前三位手機號碼的重覆率很高。再比如使用身份證號碼出生年月位數要比使用前幾位數要更好。
在實際中，我們的鍵並不都是數字，有可能是字元串，還有可能是幾個值的組合等，所以我們需要實現自己的哈希函數。
1. 正整數
獲取正整數哈希值最常用的方法是使用除留餘數法。即對於大小為素數M的數組，對於任意正整數k，計算k除以M的餘數。M一般取素數。
2. 字元串
將字元串作為鍵的時候，我們也可以將他作為一個大的整數，採用再採用保留除餘法。我們可以將組成字元串的每一個字元取值然後進行哈希，比如
public int GetHashCode(string str)
{
char[] s = str.ToCharArray();
int hash = 0;
for (int i = 0; i < s.Length; i++)
{
hash = s[i] + (31 * hash);
}
return hash;
}
java中String的預設實現就是類似於此。
上面的哈希值是Horner計算字元串哈希值的方法，公式為:
h = s[0] · 31L–1 + … + s[L – 3] · 312 + s[L – 2] · 311 + s[L – 1] · 310
舉個例子，比如要獲取”call”的哈希值，字元串c對應的unicode為99，a對應的unicode為97，L對應的unicode為108，所以字元串”call”的哈希值為 3045982 = 99·313 + 97·312 + 108·311 + 108·310 = 108 + 31· (108 + 31 · (97 + 31 · (99)))
如果對每個字元去哈希值可能會比較耗時，所以可以通過間隔取N個字元來獲取哈西值來節省時間，比如，可以 獲取每8-9個字元來獲取哈希值：
public int GetHashCode(string str)
{
char[] s = str.ToCharArray();
int hash = 0;
int skip = Math.Max(1, s.Length / 8);
for (int i = 0; i < s.Length; i+=skip)
{
hash = s[i] + (31 * hash);
}
return hash;
}
但是，對於某些情況，不同的字元串會產生相同的哈希值，這就是前面說到的哈希衝突（Hash Collisions），比如下麵的四個字元串：
如果我們按照每8個字元取哈希的話，就會得到一樣的哈希值。所以下麵來講解如何解決哈希碰撞：
避免哈希衝突
拉鏈法
通過哈希函數，我們可以將鍵轉換為數組的索引(0-M-1)，但是對於兩個或者多個鍵具有相同索引值的情況，我們需要有一種方法來處理這種衝突。
一種比較直接的辦法就是，將大小為M 的數組的每一個元素指向一個條鏈表，鏈表中的每一個節點都存儲散列值為該索引的鍵值對，這就是拉鏈法。
基於拉鏈法的散列表的實現簡單，在鍵的順序並不重要的應用中，它可能是最塊的（也是使用最廣泛的）符號表實現。
線性探測法
線性探測法是開放定址法解決哈希衝突的一種方法，基本原理為，使用大小為M的數組來保存N個鍵值對，其中M>N，我們需要使用數組中的空位解決碰撞衝突。
開放定址法中最簡單的是線性探測法：當碰撞發生時即一個鍵的散列值被另外一個鍵占用時，直接檢查散列表中的下一個位置即將索引值加1，這樣的線性探測會出現三種結果：
- 命中，該位置的鍵和被查找的鍵相同
- 未命中，鍵為空
- 繼續查找，該位置和鍵被查找的鍵不同。
空元素（記為null）可以作為查找結束的標誌。
和拉鏈法一樣，開放地址類的三列表的性能也依賴於a=N/M的比值，我們稱為散列表的使用率。
對於拉鏈法，a是每條鏈的長度，因此一般大於1；對於基於先行探測的散列表，a是表中已被占用的空間比例，它是不可能大於1的，
為保證性能。我們動態調整數組的大小來保證使用率在1/8和1/2之間。
