前言
首先給大家拋一個(gè)問(wèn)題，現(xiàn)有一個(gè)Person類包含name(假設(shè)姓名唯一)屬性，要從1000個(gè)Person對(duì)象中找出name為“張三”的對(duì)象你該怎么做讹剔？有些同學(xué)要說(shuō)話了：將1000個(gè)Person對(duì)象放入ArrayList中把沼，再遍歷ArrayList找出name為“張三”的對(duì)象不就得了。是的這種方法是可以的秩伞，但是假如張三恰好在最后一個(gè)那么就意味著要遍歷1000次逞带，這樣效率就會(huì)非常低下，那么我們有沒(méi)有什么辦法來(lái)解決這種問(wèn)題呢纱新？別急學(xué)完散列表數(shù)據(jù)結(jié)構(gòu)后答案自會(huì)揭曉展氓。
1. 概述
什么是散列表數(shù)據(jù)結(jié)構(gòu)呢？來(lái)看一下它的官方解釋:
散列表（也叫哈希表）脸爱，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)遇汞。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄簿废，以加快查找的速度空入。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表捏鱼。
什么亂七八糟的执庐，越看越暈~~~其實(shí)就是通過(guò)鍵將一條記錄保存到表中響應(yīng)的位置，再通過(guò)鍵從表中取出記錄导梆。是不是有種似曾相識(shí)的感覺(jué)轨淌？沒(méi)錯(cuò)Java中的HashTable和HashMap內(nèi)部就是散列表數(shù)據(jù)結(jié)構(gòu)。
2. 散列表設(shè)計(jì)
回到前面1000個(gè)Person的話題看尼，假設(shè)如果我們用一個(gè)數(shù)組來(lái)存儲(chǔ)Person對(duì)象递鹉，通過(guò)一個(gè)算法將Person中的name返回一個(gè)int類型值(這個(gè)算法也稱之為hash算法)，我們就將這個(gè)int類型值最為數(shù)組的角標(biāo)存儲(chǔ)在數(shù)組中藏斩，獲取的時(shí)候直接通過(guò)hash算法計(jì)算出數(shù)組角標(biāo)然后直接獲取到對(duì)應(yīng)角標(biāo)的元素躏结，通過(guò)這種方式可以很大程度的提升查詢效率。
嗯狰域，看似很完美媳拴，那么問(wèn)題來(lái)了，如果通過(guò)hash算法得到的int值為10000那么是不是就意味著我至少要?jiǎng)?chuàng)建一個(gè)長(zhǎng)度為10000的數(shù)組兆览？看似是這樣的屈溉，問(wèn)題更嚴(yán)重，我還是老老實(shí)實(shí)用我的ArrayList吧~~~~哈哈哈抬探，有問(wèn)題就要解決啊子巾，要不然我寫著文章還有mao用。。线梗。首先我們可不可以這樣做椰于，我們將hash算法得到的值進(jìn)行一個(gè)限制比如0-15，這樣我們創(chuàng)建一個(gè)長(zhǎng)度為16的數(shù)組就行了仪搔，那那那那問(wèn)題又來(lái)了瘾婿，假如張三和李四通過(guò)hash計(jì)算得到的值都是5而數(shù)組中一個(gè)角標(biāo)只能存一個(gè)元素，怎么搞僻造？憋他？？其實(shí)這種情況就是我們經(jīng)常聽(tīng)說(shuō)的哈希沖突髓削，怎么解決？別急镀娶，請(qǐng)看下一小節(jié)立膛。
3. 哈希沖突
解決哈希沖突的方法有很多，本篇文章就選一種比較典型方式：鏈表法梯码，所以不了解鏈表數(shù)據(jù)結(jié)構(gòu)的同學(xué)可以先去熟悉一下宝泵。再回到Person的例子，假如張三和李四的hash值都是5那么我們可以將張三放在數(shù)組的第5個(gè)位置轩娶，李四以鏈表的形式放在張三后面儿奶，又來(lái)個(gè)王五hash值恰好也是5，那么我們就可以將王五放在李四的后面了鳄抒，以此類推闯捎。詳情如下圖所示：
查詢的時(shí)候首先計(jì)算出hash值得到角標(biāo)，通過(guò)角標(biāo)找到對(duì)應(yīng)的鏈表頭結(jié)點(diǎn)许溅，然后再根據(jù)key值去鏈表中找具體的元素瓤鼻。
4. 代碼實(shí)現(xiàn)
通過(guò)上面幾個(gè)小節(jié)相信你已經(jīng)熟悉了散列表的數(shù)據(jù)結(jié)構(gòu)，下面我來(lái)帶著大家通過(guò)代碼實(shí)現(xiàn)一個(gè)簡(jiǎn)單的HashMap贤重。實(shí)現(xiàn)步驟如下：
- 設(shè)計(jì)節(jié)點(diǎn)類
- 設(shè)計(jì)hash算法
- 插入元素
- 擴(kuò)展數(shù)組
- 查詢?cè)?/li>
4.1 設(shè)計(jì)節(jié)點(diǎn)類
本例中解決哈希沖突采用單向鏈表茬祷，代碼如下：
//節(jié)點(diǎn)對(duì)象
public class Node<K,V>{
K key;//鍵
V value;//值
Node<K,V> next;//下一個(gè)節(jié)點(diǎn)對(duì)象
public Node(K key,V value,Node<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
節(jié)點(diǎn)的鍵值為泛型類型，包含三個(gè)屬性：鍵并蝗、值祭犯、后繼節(jié)點(diǎn)，沒(méi)啥難的就不多做解釋滚停。
4.2 hash算法
前面我提到過(guò)hash算法有很多種沃粗，本篇文章側(cè)重點(diǎn)為散列表數(shù)據(jù)結(jié)構(gòu)，所以我就設(shè)計(jì)了一個(gè)較為簡(jiǎn)單的hash算法(難的我也寫不出來(lái)啊~~~)铐刘，代碼如下：
//傳入key值
public int hash(K key){
//獲取到key的hashCode值
int code = key.hashCode();
//defaultCapacity為數(shù)組長(zhǎng)度陪每，默認(rèn)為16
return code%(defaultCapacity-1);
}
是有點(diǎn)簡(jiǎn)單，加上大括號(hào)才四行代碼。檩禾。挂签。。defaultCapacity為當(dāng)前數(shù)組的長(zhǎng)度盼产，所以該hash算法的值被限制在了0-(defaultCapacity-1)饵婆。
4.3 插入元素
插入元素需要考慮的因素比較多，我個(gè)人把它細(xì)分為4步
步驟：
- 計(jì)算key的哈希值戏售，即存儲(chǔ)角標(biāo)
- 判斷key值是否已經(jīng)存在(散列表中不允許重復(fù)key)侨核，如果存在就將value替換
- 判斷是否需要擴(kuò)容(下一小節(jié)會(huì)講到)
- 將key、value生成節(jié)點(diǎn)對(duì)象以頭結(jié)點(diǎn)的形式存入到數(shù)組中
代碼：
//添加元素
public V put(K key,V value){
//初始化數(shù)組
if(nodes==null){
nodes = new Node[defaultCapacity];
}
int index = hash(key);//計(jì)算存儲(chǔ)角標(biāo)
//獲取到數(shù)組角標(biāo)元素灌灾，可視為頭結(jié)點(diǎn)
Node<K,V> node = nodes[index];
//遍歷鏈表中節(jié)點(diǎn)對(duì)象
while (node!=null){
//存在重復(fù)key將value替換
if(node.key.equals(key)){
node.value = value;
return value;
}else {
node = node.next;
}
}
//判斷是否需要擴(kuò)展defaultCapacity為數(shù)組長(zhǎng)度搓译，
//defaultLoadFactor為擴(kuò)展因子默認(rèn)0.75
if(size>=defaultCapacity*defaultLoadFactor){
resize();
}
//將新添加的數(shù)據(jù)作為頭結(jié)點(diǎn)添加到數(shù)組中
nodes[index] = new Node<>(key,value,nodes[index]);
size++;
return value;
}
4.4 擴(kuò)展數(shù)組
關(guān)于數(shù)組擴(kuò)容這一塊我詳細(xì)說(shuō)一下，如果defaultCapacity的值始終是16锋喜，那么當(dāng)數(shù)據(jù)量較大的情況下數(shù)組中的鏈表會(huì)很長(zhǎng)些己，雖然通過(guò)hash算法可以得到角標(biāo)中頭結(jié)點(diǎn)，但仍要花大量時(shí)間去鏈表中查找元素嘿般，所以要在相應(yīng)的時(shí)機(jī)對(duì)數(shù)組進(jìn)行擴(kuò)容段标，擴(kuò)容后對(duì)所有數(shù)據(jù)重新再散列。一般來(lái)說(shuō)通過(guò)定義的擴(kuò)展因子來(lái)決定是否擴(kuò)容炉奴，假如擴(kuò)展因子為0.75逼庞，那么當(dāng)散列表中元素達(dá)到defaultCapacity*0.75時(shí)需進(jìn)行擴(kuò)容操作。具體代碼如下：
//擴(kuò)展數(shù)組
public void resize(){
//擴(kuò)容后要對(duì)元素重新put(重新散列)瞻赶，所以要將size置為0
size=0;
//記錄先之前的數(shù)組
Node<K,V>[] oldNodes = nodes;
defaultCapacity = defaultCapacity*2;
nodes = new Node[defaultCapacity];
//遍歷散列表中每個(gè)元素
for (int i = 0;i<oldNodes.length;i++){
//擴(kuò)容后hash值會(huì)改變赛糟，所以要重新散列
Node<K,V> node = oldNodes[i];
while (node!=null){
Node<K,V> oldNode = node;
put(node.key,node.value);//散列
node = node.next;//角標(biāo)往后移
oldNode.next = null;//將當(dāng)前散列的節(jié)點(diǎn)next置為null
}
}
}
重新散列后一定要將當(dāng)前節(jié)點(diǎn)的next置為null。注釋寫的很清楚就不過(guò)多贅述共耍。
4.5 查詢?cè)?/h5>
查詢?cè)鼐捅容^簡(jiǎn)單了虑灰，首先通過(guò)hash算法計(jì)算出角標(biāo)位置，然后獲取頭結(jié)點(diǎn)再對(duì)鏈表進(jìn)行遍歷痹兜，如果存在符合的key就將value返回穆咐，代碼如下：
//獲取元素
public V get(K key){
//獲取角標(biāo)位置
int index = hash(key);
//獲取頭結(jié)點(diǎn)
Node<K,V> node = nodes[index];
if(node!=null){
//遍歷鏈表
while (node!=null&&!node.key.equals(key)){
node = node.next;
}
if(node==null){
return null;
}else {
return node.value;
}
}
return null;
}
4.6 完整代碼
public class ZsHashMap<K,V> {
private Node<K,V>[] nodes;//存儲(chǔ)頭節(jié)點(diǎn)的數(shù)組
private int size;//元素個(gè)數(shù)
private static int defaultCapacity = 16;//默認(rèn)容量
private static float defaultLoadFactor = 0.75f;//擴(kuò)展因子
public ZsHashMap(){}
public ZsHashMap(int capacity,int loadFactor){
defaultCapacity = capacity;
defaultLoadFactor = loadFactor;
}
//添加元素
public V put(K key,V value){
//初始化數(shù)組
if(nodes==null){
nodes = new Node[defaultCapacity];
}
int index = hash(key);//計(jì)算存儲(chǔ)角標(biāo)
//獲取到數(shù)組角標(biāo)元素，可視為頭結(jié)點(diǎn)
Node<K,V> node = nodes[index];
//遍歷鏈表中節(jié)點(diǎn)對(duì)象
while (node!=null){
//存在重復(fù)key將value替換
if(node.key.equals(key)){
node.value = value;
return value;
}else {
node = node.next;
}
}
//判斷是否需要擴(kuò)展defaultCapacity為數(shù)組長(zhǎng)度字旭，
//defaultLoadFactor為擴(kuò)展因子默認(rèn)0.74
if(size>=defaultCapacity*defaultLoadFactor){
resize();
}
//將新添加的數(shù)據(jù)作為頭結(jié)點(diǎn)添加到數(shù)組中
nodes[index] = new Node<>(key,value,nodes[index]);
size++;
return value;
}
//獲取元素
public V get(K key){
//獲取角標(biāo)位置
int index = hash(key);
//獲取頭結(jié)點(diǎn)
Node<K,V> node = nodes[index];
if(node!=null){
//遍歷鏈表
while (node!=null&&!node.key.equals(key)){
node = node.next;
}
if(node==null){
return null;
}else {
return node.value;
}
}
return null;
}
//擴(kuò)展數(shù)組
public void resize(){
//擴(kuò)容后要對(duì)元素重新put(重新散列)对湃，所以要將size置為0
size=0;
//記錄先之前的數(shù)組
Node<K,V>[] oldNodes = nodes;
defaultCapacity = defaultCapacity*2;
nodes = new Node[defaultCapacity];
//遍歷散列表中每個(gè)元素
for (int i = 0;i<oldNodes.length;i++){
//擴(kuò)容后hash值會(huì)改變，所以要重新散列
Node<K,V> node = oldNodes[i];
while (node!=null){
Node<K,V> oldNode = node;
put(node.key,node.value);//重新散列
node = node.next;//指針往后移
oldNode.next = null;//將當(dāng)前散列的節(jié)點(diǎn)next置為null
}
}
}
//hash算法
public int hash(K key){
int code = key.hashCode();
return code%(defaultCapacity-1);
}
//節(jié)點(diǎn)對(duì)象
public class Node<K,V>{
K key;
V value;
Node<K,V> next;
public Node(K key,V value,Node<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
}
來(lái)做一下測(cè)試：
ZsHashMap<String,Integer> map = new ZsHashMap<>();
map.put("a",1);
map.put("b",2);
map.put("b",3);
System.out.println(map.get("a"));
System.out.println(map.get("b"));
打印結(jié)果：
1
3
我刻意的將b添加兩次遗淳，從打印結(jié)果來(lái)看第二次對(duì)第一次進(jìn)行了覆蓋拍柒。到這一個(gè)簡(jiǎn)單的散列表就實(shí)現(xiàn)了，其實(shí)還可以加入很多擴(kuò)展的方法屈暗， 比如remove()拆讯、迭代器等等文章中就比一一講解脂男，感興趣的同學(xué)可以自己實(shí)現(xiàn)。
總結(jié)
我一直都認(rèn)為种呐，一個(gè)合格的Coder要保持一種精神：“知其然更要知其所以然”宰翅，比如今天的散列表，如果你不清楚它的內(nèi)部原理你是不會(huì)明白它的優(yōu)點(diǎn)是什么爽室，更別說(shuō)去靈活的運(yùn)用汁讼，當(dāng)然學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)好處遠(yuǎn)不止此。本篇文章內(nèi)容差不多就這些了阔墩，以后我還會(huì)陸續(xù)推出數(shù)據(jù)結(jié)構(gòu)的文章嘿架，希望大家繼續(xù)關(guān)注。
