開放定址法

開放定址法是解決散列表發生碰撞的方法之一，與另外一種方法--連結法相對應。開放定址法把所有的元素都存放在散列表中，也就是每個表項包含動態集合的一個元素，或者包含NIL。
當查找一個元素時，要檢查所有的表項，知道找到所需的元素，或者最終發現元素不在表中。不像在連結法中，這裡沒有鍊表，也沒有元素存放在散列表外。在這裡散列表有可能會被填滿，但是裝載因子（動態集合元素/散列槽數）絕對不會大於1。
在開放定址法中，當要插入一個元素時，可以連續地檢查散列表的個各項，直到找到一個空槽來放置這個元素為止。檢查順序可以是線性的，可以是二次的，也可以是再次散列的。
查找關鍵字和插入關鍵字的算法基本上是一樣的。
在開放定址法中，對散列表元素的刪除操作執行起來比較困難。當我們從槽i中刪除關鍵字時，不能僅將NIL置於其中來標識它為空。因為這樣做的話，會導致在插入另外的關鍵字探查過程中，有可能無法檢索某些關鍵字。這裡有一個解決方法，就是在槽i中置一個特定的槽當作空槽，從而可以插入新元素。
1.線性探查給定一個普通的散列函式h’:U->{0,1,2…m-1}(稱為輔助散列函式)，線性探查方法採用的散列函式為：h(k,i)=(h’(k)+i) mod m , i=0,1,2,…m-1
給定一個關鍵字k，第一個探查的槽式T(h’(k)),接下來探查下一個槽，知道T[m-1]。
線性探查方法比較容易實現，但存在一個問題，成為一次群集。隨著時間的推移，連續被占用的槽不斷增加，平均查找時間也隨著不斷增加。群集現象很容易出現，這是因為當一個空槽前有i個滿的槽時，該空槽為下一個將被占用的槽的機率是(i+1)/m，連續被占用的槽的序列將會變得越來越長，因而平均查找時間也會隨之增加。2.二次探查（quadratic probing）採用的形式如下：
h(k,i)=(h’(k)+c1i+C2I)modm
其中h’是一個輔助散列函式，c1和c2為輔助常數，i=0,1,…m-1。處事的探查位置為T[h’(k)],後續的探查位置要在此基礎上加上一個偏移量，該偏移量是以二次的方式依賴於探查號i的。如果兩個關鍵字的初始探查位置是相同的，那么他們的後續二次探查的序列也是相同的。這種性質會導致一種程度較輕的群集現象，成為二次群集。3.雙重散列是用在開放定址法的最好方法之一，因為它所產生的排列具有隨機選擇的排列的許多特性。它採用如下形式的散列函式：
h(k,i)=(h1(k)+i*h2(k))modm
其中h1和h2是輔助散列函式。初始探查位置為T[h1(k)],後續的探查位置在此基礎上加上偏移量h2(k)模m。與線性探查和二次探查不同的是，這裡的探查序列以兩種方式依賴於k，因為初始探查位置和偏移量都可能發生變化。