注：本文如涉及到代碼，均經過Python 3.7實際運行檢驗，保證其嚴謹性。
本文閱讀時間約為3分鐘。
前面介紹過順序查找和二分查找。
當一組數據項的排列是無序時，我們就用順序查找；當數據項是有序時，我們可以用二分查找法來降低算法複雜度，從順序查找法的O(n)，降低到二分查找法的O(log n)，從而實現更高效的查找。
那麼問題來了，我們能否進一步降低查找的算法複雜度呢？
答案是，能。
現在，我們進一步構造一個新的數據結構，能使得查找算法的複雜度降低到O(1)，也就是常數級別。實現的這種概念就是散列(hashing)。
散列(hashing)
要使得查找的次數降低到常數級別，先要對數據項所處的位置有更多的先驗知識——如果事先能知道要找的數據項應該出現在數據集裡的什麼位置，就可以直接到那個位置查看數據項是否存在即可。
由數據項的值來確定其存放位置，如何能做到這一點呢？
散列表(hash table，又稱哈希表)就是我們的答案。
散列表，是一種數據集，其中數據項的存儲方式尤其有利於將來快速的查找定位。
散列表中的每一個存儲位置，稱為槽(slot)，是用來保存數據項的。每個槽都有唯一的名稱。
實現從數據項到存儲槽名稱轉換的，稱為散列函數(hash function)。
一個散列的示例
下面示例中，散列函數接受數據項作為參數，返回整數值0~10，表示數據項存儲的槽號（名稱）。
假設我們有這麼一些數據項：
<code>54
,
26
,
93
,
17
,
77
,
31
/<code>
有一種常用的散列方法“求餘數”，將數據項除以散列表的大小，得到的餘數作為槽號。
實際上“求餘數”方法會以不同形式出現在所有的散列函數里。
因為散列函數返回的槽號必須在散列表大小範圍之內，所以一般會對散列表大小求餘。
在我們的這個示例中，因為槽號的下標是0~10，一共11個槽，所以散列函數是最簡單的求餘：
<code>h(item)
=
item
%
11
/<code>
按照散列函數h(item)，為每個數據項計算出存放的位置之後，就可以將數據項存入相應的槽中。如下表所示：
<code>Item
Hash
Value
54
10
26
4
93
5
17
6
77
0
31
9
/<code>
可以看到，示例中的6個數據項各自佔據了1個槽，也就是6個數據項一共佔據了11個槽中的6個。這種槽被數據項佔據的比例稱為散列表的“負載因子”。本例中的負載因子是6/11。
我們把數據項都保存在散列表中之後，查找就非常簡單了。
如果要查找某個數據項是否存在於表中，我們需要使用同一個散列函數，對查找項進行計算，測試下返回的槽號所對應的槽中是否有數據項即可。
如此，我們便實現了複雜度為O(1)的查找算法。
散列表查找方法的劣勢
上述例子雖然實現了O(1)複雜度的查找算法，但是，我們注意到，示例比較特殊，6個數據項佔據了6個槽，也就是每個槽只有1個獨一無二的數據項。
那麼問題來了，如果再增加1個數據項，比如44，h(44)=0，就造成了#0槽有兩個數據項，7個數據項只佔據了6個槽的情況，即有一個槽有2個不同的數據項。這種情況稱為衝突（collision）。
關於衝突的情況，我們後面再討論其解決方案。
To be continued.
