哈希Hash
什麼是Hash
通過一些計算，把關鍵碼值映射到數組中的位置來訪問記錄，這個過程稱為散列（hash）。
重要組成：
- hash函數：把關鍵碼值映射到位置的函數稱為散列函數。用h表示。
- hash表：存放記錄的數組稱為散列表。用HT表示。
- 槽（slot）：散列表中的一個位置稱為一個槽。
設計hash表的目標是：使得對於任何關鍵碼值K和某個散列函數h，i=h(K)是表中滿足0<=h(K)<M（M為HT中槽的數目）的一個槽，並且記錄在HT[i]存儲的關鍵碼值與K相等。
衝突解決
在實際情況中，我們根據散列方法組織的數據庫必須把存儲的記錄存放在不大的散列表中，以避免浪費過多的空間。這樣的話，有可能有多個關鍵碼值計算出來的h(K)是一樣的，但又不能同時放在同一個槽中，此時就要使用衝突解決策略。
衝突解決策略
衝突解決策略一般分為兩類：
- 開散列方法（open hashing；也稱為單鏈方法）
- 閉散列方法（closed hashing；也稱為開地址方法）
開散列方法
開散列方法的最簡單形式把散列表中的每個槽定義為一個鏈表的表頭，散列到一個槽的所有記錄都放在這個槽的鏈表內。
閉散列方法
閉散列方法把所有記錄直接存儲到散列表中。每條關鍵碼值標記為kR，記錄R有一個基槽，就是h(kR)，即由散列函數計算出來的槽。如果要插入一條記錄R，而另一條記錄已經佔據了R的基槽，那麼就把R存儲在表的其他槽內。
桶式散列
- 一種實現閉散列的方法是把散列表中的槽分成多個桶(bucket)。把散列表中的M個槽分成B個桶，每個桶中包含M/B個槽。
- 散列函數把每一條記錄分配到某個桶的第一個槽中。
- 如果這個槽已經被佔用，那麼就順序地沿着桶查找，直到找到一個空槽。
- 如果一個桶全部被佔滿了，那麼就把這條記錄存儲在表後具有無限容量的溢出桶（overflow bucket）中。
線性探查
最常用的散列方法。當發生衝突時，從當前基槽開始往後查找，有空位則將記錄放進去。例如，2037原本應放在7的槽中，但是7已經被佔用，所以往後查找空位，8是空的，於是將2037放進去。
但是這種方法會導致基本聚集。例如在上例中，下一條記錄放到第2個槽的概率就是6/10了，因為取模後值為7,8,9,0,1,2都會放到第2個槽中。在理想情況下，表中的每個空槽都應該有相同的機會接受到下一個要插入的記錄。
改進的衝突解決方法
如何避免基本聚集呢？
一種可能的改進方式是仍然使用線性探查，但是跳過一些槽，而且每次跳過常數c個而不是1個槽。這會生成探查函數：P(K,i)=ci。
例如，如果常數c是2的話：如果基槽被佔用的話，第一次會找基槽+2的位置，看是否被佔用，如果被佔用了，第二次會找基槽+4的位置，如果還是被佔用，則找基槽+6的位置，以此類推。即從基槽開始的偏移量將會為2,4,6。
另一種方法是使用二次探查函數（對於某些常數c1,c2,c3）：p(K,i)=c1i<sup>2</sup>+c2i+c3。一個最簡單的變體就是p(K,i)=i<sup>2</sup>。
例如，對於一個長度M=101的散列表，假定對於關鍵碼k1和k2，h(k1)=30，h(k2)=29。k1的探查序列為30,31,34,39；k2的探查序列為29,30,33,38。這樣，儘管k2會在第二步探查k1的基槽，這兩個關鍵碼的探查序列此後就立即分開了。
雙散列方法
即由兩個散列函數，一個散列函數用於計算基槽，另一個散列函數用於確定線性探查中的常數。即線性探查此時的形式為：p(K,i)=i*h2(K)。
例如，假定散列表的長度是M=101，有3個關鍵碼k1，k2，k3，h(k1)=30，h(k2)=28，h(k3)=30，h2(k1)=2，h2(k2)=5，h2(k3)=5。那麼k1的探查序列為：30,32,34,36等；k2的探查序列為：28,33,38,43等；k3的探查序列為：30,35,40,45等。這樣關鍵碼之間就不會共享同一段探查序列了。
