題圖Pid=68670770

在最近的學(xué)習(xí)過程中，發(fā)現(xiàn)身邊很多朋友對哈希表的原理和應(yīng)用場景不甚了解，處于會用但不知道什么時候該用的狀態(tài)，所以我找出了剛學(xué)習(xí)Java時寫的HashMap實現(xiàn)，并以此為基礎(chǔ)拓展關(guān)于哈希表的實現(xiàn)原理。

什么是哈希表？

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
給定表M，存在函數(shù)f(key)，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。

以上正式的解釋摘自百度百科哈希表頁面。

從這段解釋中，我們理應(yīng)知道的：

• 哈希表是一種數(shù)據(jù)結(jié)構(gòu)
• 哈希表表示了關(guān)鍵碼值和記錄的映射關(guān)系
• 哈希表可以加快查找速度
• 任意哈希表，都滿足有哈希函數(shù)f(key)，代入任意key值都可以獲取包含該key值的記錄在表中的地址

---

官方解釋聽過了，那么如何用大白話來解釋呢？

簡單的來說，哈希表是一種表結(jié)構(gòu)，我們可以直接根據(jù)給定的key值計算出目標(biāo)位置。在工程中這一表結(jié)構(gòu)實現(xiàn)通常采用數(shù)組。

與普通的列表不同的地方在于，普通列表僅能通過下標(biāo)來獲取目標(biāo)位置的值，而哈希表可以根據(jù)給定的key計算得到目標(biāo)位置的值。

在列表查找中，使用最廣泛的二分查找算法，復(fù)雜度為O(log2n)，但其始終只能用于有序列表。普通無序列表只能采用遍歷查找，復(fù)雜度為O(n)。

而擁有較為理想的哈希函數(shù)實現(xiàn)的哈希表，對其任意元素的查找速度始終為常數(shù)級，即O(1)。

---

圖解：

在一個典型的哈希表實現(xiàn)中，我們將數(shù)組總長度設(shè)為模數(shù)，將key值直接對其取模，所得的值為數(shù)組下標(biāo)。

如圖所示的三組數(shù)據(jù)，分別被映射到下標(biāo)為0和7的位置中，顯而易見的，第1組數(shù)據(jù)和第3組數(shù)據(jù)發(fā)生了哈希碰撞。

---

如何解決哈希碰撞？

常用的解決方案有散列法和拉鏈法。散列法又分為開放尋址法和再散列法等，此處不做展開。java中使用的實現(xiàn)為拉鏈法，即：在每個沖突處構(gòu)建鏈表，將所有沖突值鏈入鏈表，如同拉鏈一般一個元素扣一個元素，故名拉鏈法。

需要注意的是，如果遭到惡意哈希碰撞攻擊，拉鏈法會導(dǎo)致哈希表退化為鏈表，即所有元素都被存儲在同一個節(jié)點的鏈表中，此時哈希表的查找速度=鏈表遍歷查找速度=O(n)。

哈希表有什么優(yōu)勢？

通過前面的概念了解，哈希表的優(yōu)點呼之欲出：通過關(guān)鍵值計算直接獲取目標(biāo)位置，對于海量數(shù)據(jù)中的精確查找有非常驚人的速度提升，理論上即使有無限的數(shù)據(jù)量，一個實現(xiàn)良好的哈希表依舊可以保持O(1)的查找速度，而O(n)的普通列表此時已經(jīng)無法正常執(zhí)行查找操作（實際上不可能，受到JVM可用內(nèi)存限制，機器內(nèi)存限制等）。

哈希表的主要應(yīng)用場景

在工程上，經(jīng)常用于通過名稱指定配置信息、通過關(guān)鍵字傳遞參數(shù)、建立對象與對象的映射關(guān)系等。目前最流行的NoSql數(shù)據(jù)庫之一Redis，整體的使用了哈希表思想。

一言以蔽之，所有使用了鍵值對的地方，都運用到了哈希表思想。

Java中的哈希表實現(xiàn)-HashMap

在正式開始對HashMap的介紹和實現(xiàn)之前，你應(yīng)當(dāng)知道以下這些知識：

任意數(shù)對2的N次方取模時，等同于其和2的N次方-1作位于運算。

公式表述為：

k % 2^n = k & (2^n - 1)

而位于運算相比于取模運算速度大幅度提升（按照Bruce Eckel給出的數(shù)據(jù)，大約可以提升5～8倍）。

負(fù)載因子

負(fù)載因子是哈希表的重要參數(shù)，其定義為：哈希表中已存有的元素與哈希表長度的比值。

它是一個浮點數(shù)，表示哈希表目前的裝滿程度。由于表長是定值，而表中元素的個數(shù)越大，表中空余位置就會更少，發(fā)生碰撞的可能性也會進一步增大。

哈希表的擴容策略依賴于負(fù)載因子閾值。基于性能與空間的選擇，JDK標(biāo)準(zhǔn)庫將HashMap的負(fù)載因子閾值定為0.75。

---

HashMap繼承體系

首先來看HashMap的繼承體系：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>public abstract class AbstractMap<K,V> implements Map<K,V>public interface Map<K, V>

可以看到，抽象類AbstractMap就是對Map接口的抽象實現(xiàn)，HashMap通過繼承AbstractMap間接實現(xiàn)了Map接口，同時自身直接聲明了對Map接口的實現(xiàn)，即HashMap就是Map接口的直接實現(xiàn)。

Map接口中定義了一個Map實現(xiàn)類必須要實現(xiàn)的方法。所有Map實現(xiàn)類都應(yīng)當(dāng)實現(xiàn)這些方法。

Map接口定義的需要實現(xiàn)的方法：

在本篇文章剩余的篇幅中，將會基于Map接口實現(xiàn)一個我們自己的HashMap。

MyHashMap實現(xiàn)：

在動手之前，先分析清楚Map接口提供的方法，實現(xiàn)了哪些功能。其中關(guān)鍵的方法提取出來，結(jié)果為：

//實現(xiàn)查找功能。 //containsKey基于此方法實現(xiàn)。 V get(Object key); //實現(xiàn)新增功能。 //由于哈希表同key覆蓋特性，此方法同時實現(xiàn)了更新操作。 V put(K key, V value); //實現(xiàn)刪除功能。 V remove(Object key); //實現(xiàn)對Map的遍歷功能。 Set<Map.Entry<K, V>> entrySet(); Collection<V> values(); Set<K> keySet();

我們的HashMap采用泛型數(shù)組作為存儲數(shù)據(jù)的結(jié)構(gòu)。此時應(yīng)用到兩個類Node和Entry。Node類用作拉鏈法鏈表節(jié)點，其中每個Node存儲了一個Entry類，Entry中包含了Key和Value，是真正存儲數(shù)據(jù)的類型。

前文所述的與模運算等價的位與運算，當(dāng)且僅當(dāng)模數(shù)為2的N次冪時才會生效。所以我們的HashMap初始的數(shù)組長度將會定為16，擴容策略為每次擴容為上一次長度的2倍，負(fù)載因子0.75（這也是JDK標(biāo)準(zhǔn)庫所采用的配置）。

public class MyHashMap<K, V> implements Map<K, V> {private class Node {private MyEntry<K, V> entry = null;public Node next = null;}class MyEntry<K, V> implements Entry<K, V> {private int hash;private K key;private V value;}//常量區(qū)private static final double LOAD_FACTOR = 0.75; //負(fù)載因子閾值private static final int INITIAL_SIZE = 16; //數(shù)組初始大小//成員變量區(qū)private int element_count = 0; //當(dāng)前元素計數(shù)private Node[] node_list = (Node[]) Array.newInstance(Node.class, INITIAL_SIZE); //存儲數(shù)組。//略去Map列表的實現(xiàn)方法 }

值得注意的是

private Node[] node_list = (Node[]) Array.newInstance(Node.class, INITIAL_SIZE)

Java中并不支持直接申請泛型類的數(shù)組。只能通過Array.newInstance靜態(tài)方法構(gòu)造數(shù)組并強制轉(zhuǎn)換為泛型類的數(shù)組。

resize操作時同樣需要用到此方法。

Hash表的核心操作就是通過對key值的計算直接查找目標(biāo)元素下標(biāo)，因此我們首先參考標(biāo)準(zhǔn)庫編寫(fuzhi)出getIndex方法：

private int getIndex( int hash, int mod ){return (hash & 0x7fffffff) & (mod - 1); }

(hash & 0x7fffffff)是為了確保結(jié)果為正數(shù)。

為什么要對0x7fffffff做位于操作？

0x7fffffff是int可以表達的最大正整數(shù)，除了首位為0其他31位都為1。正數(shù)& 0x7fffffff結(jié)果為其本身，負(fù)數(shù)& 0x7fffffff結(jié)果為正數(shù)。

為什么不用Math.abs？

前面說過，位運算很快。而且由于Math.abs只是簡單的return -a，因此Math.abs(Integer.MIN_VALUE)時結(jié)果仍然為負(fù)數(shù)，如下圖所示：

hash & 0x7fffffff保證結(jié)果為正數(shù)。

（結(jié)果是不是負(fù)數(shù)的絕對值不重要，只要參數(shù)同樣時每次計算都可以得出同樣的結(jié)果，就可以作為哈希函數(shù)）

基于getIndex方法，我們可以寫出put和remove方法。

@Override public V put( K key, V value ){put(new MyEntry<>(key, value), node_list, true);return value; }private void put( MyEntry<K, V> entry, Node[] target, boolean check ){put(new Node(entry), target, check); }/*** 如果目標(biāo)位置為空，則創(chuàng)建節(jié)點并保存目標(biāo)位置* 否則在列表中查找并替換重復(fù)項。* 如果沒有重復(fù)項，則插入鏈表尾部。** @param node : 被加入數(shù)組的節(jié)點。* @param target : 目標(biāo)數(shù)組。* @param check : 指示方法是否檢查數(shù)組的當(dāng)前元素數(shù)量。*/ private void put( Node node, Node[] target, boolean check ){int index = getIndex(node.getEntry().getHash(), node_list.length);if (target[index] == null) {target[index] = new Node(null);}if (target[index].next == null) {target[index].next = node;if (check) {//檢查哈希表大小++element_count;checkLoadFactor();}return;}Node temp = target[index].next;while (temp != null) {if (temp.getEntry().getHash() == node.getEntry().getHash()) {temp.setEntry(node.getEntry());return;}if (temp.next == null) {temp.next = node;temp.next.next = null; //截斷節(jié)點，防止出現(xiàn)循環(huán)引用if (check) {//檢查哈希表大小++element_count;checkLoadFactor();}}temp = temp.next;} }

其中幾個值得注意的點：

check參數(shù)：指示方法是否檢查數(shù)組的當(dāng)前元素數(shù)量。由于擴容時同樣會使用這個方法作數(shù)組元素的遷移行為，一個檢查的開關(guān)是必須的，否則會出現(xiàn)死循環(huán)。

temp.next.next = null ：同樣，在數(shù)據(jù)遷移操作時，如果未截斷鏈表的每個節(jié)點，會導(dǎo)致新老數(shù)組中對應(yīng)列表發(fā)生串聯(lián)，最終產(chǎn)生死循環(huán)。

最終MyHashMap中將集成經(jīng)典的鏈表操作。

接著實現(xiàn)remove方法：

@Override public V remove( Object key ){if (key == null) {return null;}int index = getIndex(key.hashCode(), node_list.length);if (node_list[index] == null || node_list[index].next == null) {return null;}//在目標(biāo)位置的鏈表中查找目標(biāo)鍵值。Node last = node_list[index];Node current = node_list[index].next;while (current != null) {if (current.getEntry().getHash() == key.hashCode()) {last.next = current.next;--element_count; //減少數(shù)組元素計數(shù)return current.getEntry().getValue();}last = last.next;current = current.next;}return null; }

在remove方法中，將會計算得到目標(biāo)節(jié)點下標(biāo)，遍歷目標(biāo)鏈表節(jié)點，當(dāng)查找到目標(biāo)元素時，斷開并重連鏈表將目標(biāo)元素從鏈表中移除。

非常典型的鏈表操作。

接下來實現(xiàn)最重要的get操作。然而在HashMap的CRUD三個操作中，get操作最為簡單，因為其不需要移動鏈表節(jié)點或改變鏈表結(jié)構(gòu)，僅需要遍歷鏈表即可。

/*** 從Map中查找目標(biāo)Key。* @param key* @return*/ @Override public V get( Object key ){int index = getIndex(key.hashCode(), node_list.length);//目標(biāo)位置為空則直接返回nullif (node_list[index] == null || node_list[index].next == null) {return null;}//目標(biāo)位置不為空則遍歷鏈表，查找相同的keyNode temp = node_list[index].next;while (temp != null) {if (temp.getEntry().getHash() == key.hashCode()) {return temp.getEntry().getValue();}temp = temp.next;}return null; }

接下來是resize方法，它實現(xiàn)了數(shù)組元素的遷移操作。

但在resize方法之前，我們先來看一個有趣的方法，也是我的實現(xiàn)中不同于JDK標(biāo)準(zhǔn)庫的方法，它提供了對元素數(shù)組的遍歷操作，采用雙指針法實現(xiàn)。它接受一個Consumer接口作為參數(shù)，它會對當(dāng)前數(shù)組中的所有Node調(diào)用Consumer.accept方法。

values方法，containsValue方法，keySet方法，entrySet方法都基于它來實現(xiàn)：

//遍歷list，并對其中的每一個元素執(zhí)行指定的操作 private void traversing( Node[] nl, Consumer<Node> con ){int head = 0, foot = nl.length - 1;Node node;while (head <= foot) {if (nl[head] != null && nl[head].next != null) {node = nl[head];while ((node = node.next) != null) {con.accept(node);}}if (nl[foot] != null && nl[foot].next != null) {node = nl[foot];while ((node = node.next) != null) {con.accept(node);}}++head;--foot;} }

有了traversing方法，可以用輕松（甚至是偷懶）的方式寫出values，keySet，entrySet，containsValue：

@Override public Collection<V> values(){Collection<V> collection = new ArrayList<>();traversing(node_list, (node -> {collection.add(node.getEntry().getValue());}));return collection; }@Override public Set<K> keySet(){Set<K> set = new HashSet<>();traversing(node_list, (node -> {set.add(node.entry.getKey());}));return set; }@Override public Set<Entry<K, V>> entrySet(){Set<Entry<K, V>> set = new HashSet<>();traversing(node_list, ( node ) -> {set.add(node.getEntry());});return set; }//在最壞情況下，這種實現(xiàn)會將HashMap遍歷兩次。 //這樣寫僅僅是為了偷懶。 //如果你要寫一個用于生產(chǎn)環(huán)境的containsValue，不要這樣做。 @Override public boolean containsValue( Object value ){//遍歷哈希表查找值for (Entry<K, V> entry : entrySet()) {V temp_value = entry.getValue();if (temp_value != null && temp_value.equals(value)) {return true;}}return false; }

用于對HashMap進行擴容的resize方法如下，它的實現(xiàn)原理非常簡單易懂：創(chuàng)建一個新數(shù)組，隨后調(diào)用traversing和本類的put方法將原始數(shù)組中的所有元素插入到新數(shù)組中，最終使用新數(shù)組替換原始數(shù)組。

隨便一提，(hash & 0x7fffffff) & (mod - 1)可以保證將每個鏈表中的元素平均的放入新數(shù)組中的兩個對應(yīng)位置。

/*** 列表擴容。*/ private void resize(){//創(chuàng)建新列表Node[] new_list = (Node[]) Array.newInstance(Node.class, node_list.length << 1);traversing(node_list, (node -> {put(node, new_list, false);}));//移動完成后替換當(dāng)前列表。node_list = new_list; }

大功告成！Map接口中的所有核心方法都被實現(xiàn)了。

---

在OrsPced的Github可以找到本文中的完整實現(xiàn)。

如果有更好的想法，評論或建議，歡迎在評論區(qū)提出。

對閱讀至此的您表示誠摯的感謝。

總結(jié)

以上是生活随笔為你收集整理的hashmap是散列表吗_一篇文章教你读懂哈希表-HashMap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。