本文主要介紹散列表（Hash Table）這一常見數(shù)據(jù)結(jié)構(gòu)的原理與實(shí)現(xiàn)。由于個(gè)人水平有限，文章中難免存在不準(zhǔn)確或是不清晰的地方六水，希望大家可以指正：）
概述
符號(hào)表是一種用于存儲(chǔ)鍵值對(duì)（key-value pair）的數(shù)據(jù)結(jié)構(gòu)增炭，我們平常經(jīng)常使用的數(shù)組也可以看做是一個(gè)特殊的符號(hào)表，數(shù)組中的“鍵”即為數(shù)組索引搬俊，值為相應(yīng)的數(shù)組元素紊扬。也就是說(shuō)，當(dāng)符號(hào)表中所有的鍵都是較小的整數(shù)時(shí)唉擂，我們可以使用數(shù)組來(lái)實(shí)現(xiàn)符號(hào)表餐屎，將數(shù)組的索引作為鍵，而索引處的數(shù)組元素即為鍵對(duì)應(yīng)的值玩祟，但是這一表示僅限于所有的鍵都是比較小的整數(shù)時(shí)腹缩，否則可能會(huì)使用一個(gè)非常大的數(shù)組。散列表是對(duì)以上策略的一種“升級(jí)”，但是它可以支持任意的鍵而并沒(méi)有對(duì)它們做過(guò)多的限定藏鹊。對(duì)于基于散列表實(shí)現(xiàn)的符號(hào)表润讥，若我們要在其中查找一個(gè)鍵，需要進(jìn)行以下步驟：
- 首先我們使用散列函數(shù)將給定鍵轉(zhuǎn)化為一個(gè)“數(shù)組的索引”伙判，理想情況下象对，不同的key會(huì)被轉(zhuǎn)為不同的索引，但在實(shí)際應(yīng)用中我們會(huì)遇到不同的鍵轉(zhuǎn)為相同的索引的情況宴抚，這種情況叫做碰撞勒魔。解決碰撞的方法我們后面會(huì)具體介紹。
- 得到了索引后菇曲，我們就可以像訪問(wèn)數(shù)組一樣冠绢，通過(guò)這個(gè)索引訪問(wèn)到相應(yīng)的鍵值對(duì)。
以上就是散列表的核心思想常潮，散列表是時(shí)空權(quán)衡的經(jīng)典例子弟胀。當(dāng)我們的空間無(wú)限大時(shí)，我們可以直接使用一個(gè)很大的數(shù)組來(lái)保存鍵值對(duì)喊式，并用key作為數(shù)組索引孵户，因?yàn)榭臻g不受限，所以我們的鍵的取值可以無(wú)窮大岔留，因此查找任何鍵都只需進(jìn)行一次普通的數(shù)組訪問(wèn)夏哭。反過(guò)來(lái)，若對(duì)查找操作沒(méi)有任何時(shí)間限制献联，我們就可以直接使用鏈表來(lái)保存所有鍵值對(duì)竖配，這樣把空間的使用降到了最低，但查找時(shí)只能順序查找里逆。在實(shí)際的應(yīng)用中进胯，我們的時(shí)間和空間都是有限的，所以我們必須在兩者之間做出權(quán)衡原押，散列表就在時(shí)間和空間的使用上找到了一個(gè)很好的平衡點(diǎn)胁镐。散列表的一個(gè)優(yōu)勢(shì)在于我們只需調(diào)整散列算法的相應(yīng)參數(shù)而無(wú)需對(duì)其他部分的代碼做任何修改就能夠在時(shí)間和空間的權(quán)衡上做出策略調(diào)整。
散列函數(shù)
介紹散列函數(shù)前班眯，我們先來(lái)介紹幾個(gè)散列表的基本概念希停。在散列表內(nèi)部，我們使用桶（bucket）來(lái)保存鍵值對(duì)署隘，我們前面所說(shuō)的數(shù)組索引即為桶號(hào)宠能，決定了給定的鍵存于散列表的哪個(gè)桶中。散列表所擁有的桶數(shù)被稱為散列表的**容量（capacity）磁餐。
現(xiàn)在假設(shè)我們的散列表中有M個(gè)桶违崇，桶號(hào)為0到M-1阿弃。我們的散列函數(shù)的功能就是把任意給定的key轉(zhuǎn)為[0, M-1]上的整數(shù)。我們對(duì)散列函數(shù)有兩個(gè)基本要求：一是計(jì)算時(shí)間要短羞延，二是盡可能把鍵分布在不同的桶中渣淳。對(duì)于不同類型的鍵，我們需要使用不同的散列函數(shù)伴箩，這樣才能保證有比較好的散列效果入愧。
我們使用的散列函數(shù)應(yīng)該盡可能滿足均勻散列假設(shè)，以下對(duì)均勻散列假設(shè)的定義來(lái)自于Sedgewick的《算法》一書：
（均勻散列假設(shè)）我們使用的散列函數(shù)能夠均勻并獨(dú)立地將所有的鍵散布于0到M – 1之間嗤谚。
以上定義中有兩個(gè)關(guān)鍵字棺蛛，第一個(gè)是均勻，意思是我們對(duì)每個(gè)鍵計(jì)算而得的桶號(hào)有M個(gè)“候選值”巩步，而均勻性要求這M個(gè)值被選中的概率是均等的旁赊；第二個(gè)關(guān)鍵字是獨(dú)立，它的意思是椅野，每個(gè)桶號(hào)被選中與否是相互獨(dú)立的终畅，與其他桶號(hào)是否被選中無(wú)關(guān)。這樣一來(lái)竟闪，滿足均勻性與獨(dú)立性能夠保證鍵值對(duì)在散列表的分布盡可能的均勻离福，不會(huì)出現(xiàn)“許多鍵值對(duì)被散列到同一個(gè)桶，而同時(shí)許多桶為空”的情況炼蛤。
顯然术徊，設(shè)計(jì)一個(gè)較好的滿足均勻散列假設(shè)的散列函數(shù)是不容易的，好消息是通常我們無(wú)需設(shè)計(jì)它鲸湃，因?yàn)槲覀兛梢灾苯邮褂靡恍┗诟怕式y(tǒng)計(jì)的高效的實(shí)現(xiàn)，比如Java中許多常用的類都重寫了hashCode方法（Object類的hashCode方法默認(rèn)返回對(duì)象的內(nèi)存地址）子寓，用于為該類型對(duì)象返回一個(gè)hashCode暗挑，通常我們用這個(gè)hashCode除以桶數(shù)M的余數(shù)就可以獲取一個(gè)桶號(hào)。下面我們以Java中的一些類為例斜友，來(lái)介紹一下針對(duì)不同數(shù)據(jù)類型的散列函數(shù)的實(shí)現(xiàn)炸裆。
String類的hashCode方法
String類的hashCode方法如下所示：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
hashCode方法中的value是一個(gè)char[]數(shù)組，存儲(chǔ)中字符串的的每字符鲜屏。我們可以看到在方法的最開始我們會(huì)把hash賦給h烹看，這個(gè)hash就表示之前計(jì)算的hashCode，這樣以來(lái)若之前已經(jīng)計(jì)算過(guò)這個(gè)字符串對(duì)象的hashCode洛史，這次我們就無(wú)需再計(jì)算了惯殊，直接返回之前計(jì)算過(guò)得即可。這種把hashCode緩存的策略只對(duì)不可變對(duì)象有效也殖，因?yàn)椴豢勺儗?duì)象的hashCode是不會(huì)變的土思。
根據(jù)上面的代碼我們可以知道，若h為null，意味著我們是第一次計(jì)算hashCode己儒，if語(yǔ)句體中就是hashCode的具體計(jì)算方法崎岂。假設(shè)我們的字符串對(duì)象str包含4個(gè)字符，ck表示的是字符串中的第k個(gè)字符（從0開始計(jì)數(shù)）闪湾，那么str的hashCode就等于：31 * (31 * (31 * c0 + c1) + c2) +c3冲甘。
數(shù)值類型的hashCode方法
這里我們以Integer和Double為例，介紹一下數(shù)值類型的hashCode方法的一般實(shí)現(xiàn)途样。
Integer類的hashCode方法如下：
public int hashCode() {
return Integer.hashCode(value);
}
public static int hashCode(int value) {
return value;
}
其中value表示Integer對(duì)象所包裝的整型值江醇，所以Integer類的hashCode方法僅僅是簡(jiǎn)單的返回了自身的值。
我們?cè)賮?lái)看一下Double類的hashCode方法：
@Override
public int hashCode() {
return Double.hashCode(value);
}
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
我們可以看到Double類的hashCode方法首先會(huì)將它的值轉(zhuǎn)為long類型娘纷，然后返回低32位和高32位的異或的結(jié)果作為hashCode嫁审。
Date類的hashCode方法
前面我們介紹的數(shù)據(jù)類型都可以看做一種數(shù)值型（String可以看做一個(gè)整型數(shù)組），那么對(duì)于非數(shù)值類型對(duì)象的hashCode要怎么計(jì)算呢赖晶，這里我們以Date類為例簡(jiǎn)單的介紹一下律适。Date類的hashCode方法如下：
public int hashCode() {
long ht = this.getTime();
return (int) ht ^ (int) (ht >> 32);
}
我們可以看到，它的hashCode方法的實(shí)現(xiàn)非常簡(jiǎn)單遏插，只是返回了Date對(duì)象所封裝的時(shí)間的低32位和高32位的異或結(jié)果捂贿。從Date類的hashCode的實(shí)現(xiàn)我們可以了解到，對(duì)于非數(shù)值類型的hashCode的計(jì)算胳嘲，我們需要選取一些能區(qū)分各個(gè)類實(shí)例的實(shí)例域來(lái)作為計(jì)算的因子厂僧。比如對(duì)于Date類來(lái)說(shuō)，通常具有相同的時(shí)間的Date對(duì)象我們認(rèn)為它們相等了牛，因此也就具有相同的hashCode颜屠。這里我們需要說(shuō)明一下，對(duì)于等價(jià)的兩個(gè)對(duì)象（也就是調(diào)用equals方法返回true）鹰祸，它們的hashCode必須相同甫窟，而反之則不然。
由hashCode獲取桶號(hào)
前面我們介紹了計(jì)算對(duì)象hashCode的一些方法蛙婴，那么我們獲取了hashCode之后粗井，如何進(jìn)一步得到桶號(hào)呢？一個(gè)直接的辦法就是直接拿得到的hashCode除以capacity（桶的數(shù)量）街图，然后用所得的余數(shù)作為桶號(hào)浇衬。不過(guò)在Java中，hashCode是int型的餐济，而Java中的int型均為有符號(hào)耘擂，所以我們要是直接使用返回的hashCode的話可能會(huì)得到一個(gè)負(fù)數(shù)，顯然桶號(hào)是不能為負(fù)的颤介。所以我們先將返回的hashCode轉(zhuǎn)變?yōu)橐粋€(gè)非負(fù)整數(shù)梳星，再用它除以capacity取余數(shù)赞赖，作為key的對(duì)應(yīng)桶號(hào)，具體代碼如下：
private int hash(K key) { return (x.hashCode() & 0x7fffffff) % M;}
現(xiàn)在我們已經(jīng)知道了如何通過(guò)一個(gè)鍵獲取桶號(hào)冤灾，那么接下來(lái)我們來(lái)介紹使用散列表查找的第二步——處理碰撞前域。
使用拉鏈法處理碰撞
使用不同的碰撞處理方式，我們便得到了散列表的不同實(shí)現(xiàn)韵吨。首先我們要介紹的是使用拉鏈法來(lái)處理碰撞的散列表的實(shí)現(xiàn)匿垄。以這種方式實(shí)現(xiàn)的散列表，每個(gè)桶里都存放了一個(gè)鏈表归粉。初始時(shí)所有鏈表均為空椿疗，當(dāng)一個(gè)鍵被散列到一個(gè)桶時(shí)，這個(gè)鍵就成為相應(yīng)桶中鏈表的首結(jié)點(diǎn)糠悼，之后若再有一個(gè)鍵被散列到這個(gè)桶（即發(fā)生碰撞）届榄，第二個(gè)鍵就會(huì)成為鏈表的第二個(gè)結(jié)點(diǎn)，以此類推倔喂。這樣一來(lái)铝条，當(dāng)桶數(shù)為M，散列表中存儲(chǔ)的鍵值對(duì)數(shù)目為N時(shí)席噩，平均每個(gè)桶中的鏈表包含的結(jié)點(diǎn)數(shù)為N / M班缰。因此，當(dāng)我們查找一個(gè)鍵時(shí)悼枢，首先通過(guò)散列函數(shù)確定它所在的桶埠忘，這一步所需時(shí)間為O(1)；然后我們依次比較桶中結(jié)點(diǎn)的鍵與給定鍵馒索，若相等則找到了指定鍵值對(duì)莹妒，這一步所需時(shí)間為O(N / M)。所以查找操作所需的時(shí)間為O(N / M)绰上，而通常我們都能夠保證N是M的常數(shù)倍动羽，所以散列表的查找操作的時(shí)間復(fù)雜度為O(1)，同理我們也可以得到插入操作的復(fù)雜度也為O(1)渔期。
理解了以上的描述，實(shí)現(xiàn)基于拉鏈法的散列表也就很容易了渴邦，這里簡(jiǎn)單起見疯趟，我們直接使用前面的SeqSearchList作為桶中的鏈表，參考代碼如下：
public class ChainingHashMap<K, V> {
private int num; //當(dāng)前散列表中的鍵值對(duì)總數(shù)
private int capacity; //桶數(shù)
private SeqSearchST<K, V>[] st; //鏈表對(duì)象數(shù)組
public ChainingHashMap(int initialCapacity) {
capacity = initialCapacity;
st = (SeqSearchST<K, V>[]) new Object[capacity];
for (int i = 0; i < capacity; i++) {
st[i] = new SeqSearchST<>();
}
}
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % capacity;
}
public V get(K key) {
return st[hash(key)].get(key);
}
public void put(K key, V value) {
st[hash(key)].put(key, value);
}
}
在上面的實(shí)現(xiàn)中谋梭，我們固定了散列表的桶數(shù)信峻，當(dāng)我們明確知道我們要插入的鍵值對(duì)數(shù)目最多只能到達(dá)桶數(shù)的常數(shù)倍時(shí)，固定桶數(shù)是完全可行的瓮床。但是若鍵值對(duì)數(shù)目會(huì)增長(zhǎng)到遠(yuǎn)遠(yuǎn)大于桶數(shù)盹舞，我們就需要?jiǎng)討B(tài)調(diào)整桶數(shù)的能力产镐。實(shí)際上，散列表中的鍵值對(duì)數(shù)與桶數(shù)的比值叫做負(fù)載因子（load factor）踢步。通常負(fù)載因子越小癣亚，我們進(jìn)行查找所需時(shí)間就越短，而空間的使用就越大获印；若負(fù)載因子較大述雾，則查找時(shí)間會(huì)變長(zhǎng)，但是空間使用會(huì)減小兼丰。比如玻孟，Java標(biāo)準(zhǔn)庫(kù)中的HashMap就是基于拉鏈法實(shí)現(xiàn)的散列表，它的默認(rèn)負(fù)載因子為0.75鳍征。HashMap實(shí)現(xiàn)動(dòng)態(tài)調(diào)整桶數(shù)的方式是基于公式loadFactor = maxSize / capacity黍翎，其中maxSize為支持存儲(chǔ)的最大鍵值對(duì)數(shù)，而loadFactor和capacity（桶數(shù)）都會(huì)在初始化時(shí)由用戶指定或是由系統(tǒng)賦予默認(rèn)值艳丛。當(dāng)HashMap中的鍵值對(duì)的數(shù)目達(dá)到了maxSize時(shí)匣掸，就會(huì)增大散列表中的桶數(shù)。
以上代碼中還用到了SeqSearchST质礼，實(shí)際上這就是一個(gè)基于鏈表的符號(hào)表實(shí)現(xiàn)旺聚，支持向其中添加key-value pair，查找指定鍵時(shí)使用的是順序查找眶蕉，它的代碼如下：
public class SeqSearchST<K, V> {
private Node first;
private class Node {
K key;
V val;
Node next;
public Node(K key, V val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
public V get(K key) {
for (Node node = first; node != null; node = node.next) {
if (key.equals(node.key)) {
return node.val;
}
}
return null;
}
public void put(K key, V val) {
//先查找表中是否已存在相應(yīng)key
Node node;
for (node = first; node != null; node = node.next) {
if (key.equals(node.key)) {
node.val = val;
return;
}
}
//表中不存在相應(yīng)key
first = new Node(key, val, first);
}
}
使用線性探測(cè)法處理碰撞
基本原理與實(shí)現(xiàn)
線性探測(cè)法是另一種散列表的實(shí)現(xiàn)策略的具體方法砰粹，這種策略叫做開放定址法。開放定址法的主要思想是：用大小為M的數(shù)組保存N個(gè)鍵值對(duì)造挽，其中M > N碱璃，數(shù)組中的空位用于解決碰撞問(wèn)題。
線性探測(cè)法的主要思想是：當(dāng)發(fā)生碰撞時(shí)（一個(gè)鍵被散列到一個(gè)已經(jīng)有鍵值對(duì)的數(shù)組位置）饭入，我們會(huì)檢查數(shù)組的下一個(gè)位置嵌器，這個(gè)過(guò)程被稱作線性探測(cè)。線性探測(cè)可能會(huì)產(chǎn)生三種結(jié)果：
- 命中：該位置的鍵與要查找的鍵相同谐丢；
- 未命中：該位置為空爽航；
- 該位置的鍵和被查找的鍵不同。
當(dāng)我們查找某個(gè)鍵時(shí)乾忱，首先通過(guò)散列函數(shù)得到一個(gè)數(shù)組索引后讥珍，之后我們就開始檢查相應(yīng)位置的鍵是否與給定鍵相同，若不同則繼續(xù)查找（若到數(shù)組末尾也沒(méi)找到就折回?cái)?shù)組開頭）窄瘟，直到找到該鍵或遇到一個(gè)空位置衷佃。由線性探測(cè)的過(guò)程我們可以知道，若數(shù)組已滿的時(shí)候我們?cè)傧蚱渲胁迦胄骆I蹄葱，會(huì)陷入無(wú)限循環(huán)之中氏义。
理解了以上原理锄列，要實(shí)現(xiàn)基于線性探測(cè)法的散列表也就不難了。這里我們使用數(shù)組keys保存散列表中的鍵惯悠，數(shù)組values保存散列表中的值邻邮，兩個(gè)數(shù)組同一位置上的元素共同確定一個(gè)散列表中的鍵值對(duì)。具體代碼如下：
public class LinearProbingHashMap<K, V> {
private int num; //散列表中的鍵值對(duì)數(shù)目
private int capacity;
private K[] keys;
private V[] values;
public LinearProbingHashMap(int capacity) {
keys = (K[]) new Object[capacity];
values = (V[]) new Object[capacity];
this.capacity = capacity;
}
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % capacity;
}
public V get(K key) {
int index = hash(key);
while (keys[index] != null && !key.equals(keys[index])) {
index = (index + 1) % capacity;
}
return values[index]; //若給定key在散列表中存在會(huì)返回相應(yīng)value吮螺，否則這里返回的是null
}
public void put(K key, V value) {
int index = hash(key);
while (keys[index] != null && !key.equals(keys[index])) {
index = (index + 1) % capacity;
}
if (keys[index] == null) {
keys[index] = key;
values[index] = value; return;
}
values[index] = value; num++;
}
}
動(dòng)態(tài)調(diào)整數(shù)組大小
在我們上面的實(shí)現(xiàn)中饶囚，數(shù)組的大小為桶數(shù)的2倍，不支持動(dòng)態(tài)調(diào)整數(shù)組大小鸠补。而在實(shí)際應(yīng)用中萝风，當(dāng)負(fù)載因子（鍵值對(duì)數(shù)與數(shù)組大小的比值）接近1時(shí)，查找操作的時(shí)間復(fù)雜度會(huì)接近O(n)紫岩，而當(dāng)負(fù)載因子為1時(shí)规惰，根據(jù)我們上面的實(shí)現(xiàn)，while循環(huán)會(huì)變?yōu)橐粋€(gè)無(wú)限循環(huán)泉蝌。顯然我們不想讓查找操作的復(fù)雜度退化至O(n)歇万，更不想陷入無(wú)限循環(huán)。所以有必要實(shí)現(xiàn)動(dòng)態(tài)增長(zhǎng)數(shù)組來(lái)保持查找操作的常數(shù)時(shí)間復(fù)雜度勋陪。當(dāng)鍵值對(duì)總數(shù)很小時(shí)贪磺，若空間比較緊張，可以動(dòng)態(tài)縮小數(shù)組诅愚，這取決于實(shí)際情況寒锚。
要實(shí)現(xiàn)動(dòng)態(tài)改變數(shù)組大小，只需要在上面的put方法最開始加上一個(gè)如下的判斷：
if (num == capacity / 2) {
resize(2 * capacity);
}
resize方法的邏輯也很簡(jiǎn)單：
private void resize(int newCapacity) {
LinearProbingHashMap<K, V> hashmap = new LinearProbingHashMap<>(newCapacity);
for (int i = 0; i < capacity; i++) {
if (keys[i] != null) {
hashmap.put(keys[i], values[i]);
}
}
keys = hashmap.keys;
values = hashmap.values;
capacity = hashmap.capacity;
}
關(guān)于負(fù)載因子與查找操作的性能的關(guān)系违孝，這里貼出《算法》（Sedgewick等）中的一個(gè)結(jié)論：
在一張大小為M并含有N = a*M（a為負(fù)載因子）個(gè)鍵的基于線性探測(cè)的散列表中刹前，若散列函數(shù)滿足均勻散列假設(shè)，命中和未命中的查找所需的探測(cè)次數(shù)分別為：~ 1/2 * (1 + 1/(1-a))和~1/2*(1 + 1/(1-a)^2)
關(guān)于以上結(jié)論雌桑，我們只需要知道當(dāng)a約為1/2時(shí)喇喉，查找命中和未命中所需的探測(cè)次數(shù)分別為1.5次和2.5次。還有一點(diǎn)就是當(dāng)a趨近于1時(shí)校坑，以上結(jié)論中的估計(jì)值的精度會(huì)下降拣技，不過(guò)我們?cè)趯?shí)際應(yīng)用中不會(huì)讓負(fù)載因子接近1，為了保持良好的性能耍目，在上面的實(shí)現(xiàn)中我們應(yīng)保持a不超過(guò)1/2过咬。
參考資料
《算法（第四版）》（Sedgewick等）
