1 直接尋址表
直接尋址表是數組的擴展，應用范圍是全域U不是很大。它和散列表的區別是不用處理沖突，因為不會出現沖突。

2 散列表
當全域U很大的時候，由于內存的限制，直接尋址表出現問題，因此可以用散列表解決。對于直接尋址表，具有關鍵字k的元素在槽k中，而該元素則在散列表的h(k)處，其中，h(k)是散列函數，這個函數將全域U映射到散列表T的[0...m-1]的槽位上。對于兩個關鍵字映射到同一個槽位上的情況，我們稱之為碰撞。
解決碰撞有：

• 鏈接法解決碰撞
• 開放尋址法

1.1 鏈接法
鏈接法解決碰撞的思想很簡單，當有多個元素同時被映射到散列表T的同一個槽位的時候，就使用鏈表的方式鏈接到該槽位上。這樣，在某些發生沖突的槽位后面形成一條長度隨機不等的鏈表。
定義兩個概念：

• 裝載因子：給定一個能存放n個元素的、具有m個槽位的散列表T，裝載因子定義為n/m。含義是一個鏈中平均存放的元素數。
• 簡單一致散列：任何元素散列到m個槽中每一個的可能性是相同的，且與其他元素已被散列到什么位置獨立無關。

定理：對一個用連接技術來解決碰撞的散列表，在簡單一致散列的假設下，一次不成功查找的期望時間為θ(1+α)，這個時間包含計算h(k)的時間。
證明：由于簡單一致散列，因此元素被映射到第i個槽的概率為1/m，假設槽i的鏈表有ni個元素，則期望時間為1+Σni/m = 1+(Σni)/m = 1 + α，證畢。
定理：在簡單一致散列的假設下，對于用鏈接技術解決碰撞的散列表，平均情況下一次成功的查找需要θ(1+α)時間。
證明見書。

1.2 散列函數
好的散列函數應（近似的）滿足簡單一致散列的假設，但很難去檢驗，因為人們很少知道關鍵字所符合的概率分布。
1.2.1 將關鍵字解釋為自然數
比如：一個字符串關鍵字可以被解釋為按適當的基數記號表示的整數。如pt表示為(112 * 128) + 116 = 14452。這將字符串看成是以128為基數的整數。
1.2.2 除法散列法
h(k) = k mod m，通過取k除以m的余數來將關鍵字k映射到m個槽的某一個中去。
注意除數m的選擇，m不應該是2的冪，因為如果m = 2^p，則h(k)就是k的p個最低位數字。并且，當k是一個按基數2^p解釋的字符串時，選m = 2^p - 1可能是個比較糟糕的選擇，因為將k的各字符進行排列并不會改變h(k)的值，這個證明比較簡單，略。一般選取m為與2的冪不太接近的素數。
1.2.3 乘法散列法
h(k) = ⌊m(kA - ⌊kA⌋)⌋。其中A為(0, 1)之間的常數。m一般選為2的某個冪次。Knuth認為A ≅(√5 - 1)/2 = 0.6180339887…是一個比較理想的值。

1.3 開放尋址法
在開放尋址法中，所有的元素都存放在散列表中，和連接法處理沖突時采用連接形式不同，開放尋址法的散列表每個表項或包含動態集合的一個元素，或包含NIL。
在開放尋址法中，當要插入一個元素時，可以連續地探查散列表的各項，直到找到一個空槽來放置待插入的關鍵字為止。
1.3.1 線性探查
h(k, i) = (h'(k) + i) mod m, i = 0, 1, ... ,m - 1
在線性探查方法中，初始探查位置確定了整個序列，因此只有m種不同的探查序列。且它存在一次群集現象。
1.3.2 二次探查
h(k, i) = (h'(k) + c * i + d * i^2) mod m
其中c和d為輔助常數。初始探查位置為T[h'(k)]，后續的探查位置要在此基礎上加上一個偏移量，該偏移量以二次的方式依賴于探查號i。它比線性探查好的多。但是如果兩個關鍵字初始探查位置相同，那么他們的探查序列也是相同的。因此它存在程度較一次群集輕的二次群集現象。
1.3.3 雙重散列
h(k, i) = (f(k) + i * g(k)) mod m
其中f(k)和g(k)為輔助散列函數。與線性探查和二次探查不同的是，這里的探查序列以兩種方式依賴于關鍵字k。為能查找整個散列表，值g(k)要與m互素。可以取m為2的冪，并設計g(k)為總產生奇數。或者取m為素數，設計g(k)總產生比m小的正整數。比如：可以取m為素數，并取f(k) = k mod m, g(k) = 1 + (k mod n) 其中n略小于m（比如為m - 1）。雙重散列法用了θ(m^2)種探查序列。