1 直接尋址表
直接尋址表是數(shù)組的擴(kuò)展，應(yīng)用范圍是全域U不是很大。它和散列表的區(qū)別是不用處理沖突，因?yàn)椴粫?huì)出現(xiàn)沖突。

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

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

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

• 裝載因子：給定一個(gè)能存放n個(gè)元素的、具有m個(gè)槽位的散列表T，裝載因子定義為n/m。含義是一個(gè)鏈中平均存放的元素?cái)?shù)。
• 簡(jiǎn)單一致散列：任何元素散列到m個(gè)槽中每一個(gè)的可能性是相同的，且與其他元素已被散列到什么位置獨(dú)立無關(guān)。

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

1.2 散列函數(shù)
好的散列函數(shù)應(yīng)（近似的）滿足簡(jiǎn)單一致散列的假設(shè)，但很難去檢驗(yàn)，因?yàn)槿藗兒苌僦狸P(guān)鍵字所符合的概率分布。
1.2.1 將關(guān)鍵字解釋為自然數(shù)
比如：一個(gè)字符串關(guān)鍵字可以被解釋為按適當(dāng)?shù)幕鶖?shù)記號(hào)表示的整數(shù)。如pt表示為(112 * 128) + 116 = 14452。這將字符串看成是以128為基數(shù)的整數(shù)。
1.2.2 除法散列法
h(k) = k mod m，通過取k除以m的余數(shù)來將關(guān)鍵字k映射到m個(gè)槽的某一個(gè)中去。
注意除數(shù)m的選擇，m不應(yīng)該是2的冪，因?yàn)槿绻鹠 = 2^p，則h(k)就是k的p個(gè)最低位數(shù)字。并且，當(dāng)k是一個(gè)按基數(shù)2^p解釋的字符串時(shí)，選m = 2^p - 1可能是個(gè)比較糟糕的選擇，因?yàn)閷的各字符進(jìn)行排列并不會(huì)改變h(k)的值，這個(gè)證明比較簡(jiǎn)單，略。一般選取m為與2的冪不太接近的素?cái)?shù)。
1.2.3 乘法散列法
h(k) = ⌊m(kA - ⌊kA⌋)⌋。其中A為(0, 1)之間的常數(shù)。m一般選為2的某個(gè)冪次。Knuth認(rèn)為A ≅(√5 - 1)/2 = 0.6180339887…是一個(gè)比較理想的值。

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