嘮嘮數據結構——哈希表

第一次結束哈希表是在數據結構課上，在講查找的時候老師隨便提了一下哈希表這個概念，最近在做聊天室的時候要用到哈希表，更加深入的理解了哈希表。

1.什麼是HashMap?

先說說存儲結構，實際上在我們學過的數據結構可以歸結為兩類：連續的的存儲結構和不聯繫的存儲結構，其代表分別為數組和鏈表。而我們學過的堆棧，隊列，樹，圖，都可以用這兩種結構來實現。連續的存儲結構——數組，在數據的查找和修改上具有很好的優點，很方便，時間複雜度很小。但是在數據的增添和刪除上則顯得很麻煩，空間複雜度很大。而非連續，非順序的存儲結構——鏈表恰和數組相反，數據的增添和刪除容易，空間複雜度很小，查找和修改複雜，時間複雜度很大。

那麼有沒有一種數據結構能折衷一下數組和鏈表的優缺點呢？那就是——哈希表，既滿足了數據的查找和修改很容易，同時又不佔用很多空間的特點。

哈希表是基於哈希函數的，哈希表中的元素是有哈希函數確定的，哈希表作為一種數據結構，我們用哈希表來存儲數據，在保存的時候存入的是一個<key—value>的結構，value由哈希函數作用於key上得到。但是存在一個哈希衝突問題，那就是當你用hash函數作用在兩個互不相同的key上，得到的value值相等。這就好比「一個班裡面有兩個叫做李洋的同學，老師上課的時候叫到李洋起來回答問題，這時就不知道是哪個李洋起來回答問題。」

因此在創建一個哈希表的時候要考慮兩個方面的問題：

一. 構造一個好的哈希函數：所謂一個好的哈希函數指的就是，當用這個hash函數作用在不同的key時，所得到的value能夠均勻的分布在hash表中，即能儘可能少的減少hash衝突。比較常見的hash函數的構造方法有：

• 直接定址法
• 數字分析法
• 平方取中法
• 摺疊法
• 除留餘數法
• 隨機數法

這裡就不再對這些方法一一闡述。

二. .hash衝突是不可能完全避免的，那麼我們要考慮的還有就是當產生哈希衝突的時候，我們如何來解決。比較常見的hash衝突的解決方法有：

• 開放定址法
• 鏈地址法
• 再哈希法

2.為什麼要用HashMap?

首先，我們採用哈希表的初衷就是對連續的存儲結構數組和非連續的存儲結構鏈表，在數據的增刪查改等操作上進行折衷。

我們不妨設想一下有這樣的一個場景：

我們要設計一個數據表來保存用戶信息，如果我們對用戶信息有一個大致的估算為五萬個，如果我們採用數組來保存的話，我們設計一個可以保存六萬個用戶的數組來作為數據表。我們在前面已經分析過了，如果用數組來保存，在數據的查詢和修改方面相當方便，但是隨著客戶的增長，如果有一天客戶增長到了五萬零一個呢？？？這個時候我們就要建一個更大的數組來進行數據得遷徙。那如果用鏈表來進行存儲呢？鏈表存儲的話，在對用戶的信息進行查詢時，我們得從鏈表的第一個節點往後一個一個找，這個也是耗時耗力的。

所以這個地方我有一種思路，那就是用鏈地址這種哈希構造方法來創建一個哈希表。在數據的增刪查改方法上可以做到相對的要好。

我們可以發現上面這個由「鏈地址法」構造的哈希表是由數組+鏈表構成的。元素的存入方法可以這樣簡單的來描述：

首先我們創建一個容量為n的數組，讓要存入的數據x對n取模，那麼結果就存入對應的數組的下標中，當有一個元素要存入數組時，這個位置已經有一個元素了，那麼我們就把這些哈希值相同的元素掛在已有的元素的後面生成一條鏈表。這就是對鏈地址法的哈希表的簡單的描述。

OK，我們簡單的介紹到這裡，下面我們會介紹一下JDK中的HashMap，和自己來寫一個我的HashMap,並在數據存儲的效率方面進行一下比對。

3.實現我的HashMap

/* * Entry類,相當於定義了鏈表一個節點的結構。 */public class Entry<K, V> { Entry<K, V> next; K key; V value; int hash; public Entry(K k, V v, int hash) { this.key = k; this.value = v; this.hash = hash; }}

每個Entry對象包括key(鍵)，value(值)，next(Entry的引用，可以形成單鏈表，用於解決哈希衝突)以及hash(哈希值)。

/** * 哈希表的實現 * * @author ZhanHaoxin * */public class MyHashMap<K, V> { private int size;// 當前容量 private static int initialCapacity = 16; // 默認初始容量為16 private static float loadFactor = 0.75f; // 默認裝載因子為0.75 private Entry<K, V>[] container; // 存儲數據的數據表 private int max; // 能存的最大數據量 等於裝載因子和初始容量的乘積 /* * 使用默認參數的構造方法 */ public MyHashMap() { this(initialCapacity, loadFactor); } /* * 使用自定義參數的構造方法 */ public MyHashMap(int Capacity, float factor) { if (Capacity < 0) { throw new IllegalArgumentException("容量有錯:" + Capacity); } if (factor <= 0) { throw new IllegalArgumentException("裝載因子有錯： " + factor); } this.loadFactor = factor; max = (int) (loadFactor * Capacity); container = new Entry[Capacity]; size = 0; } /* * 實現數據 存 的功能 * */ public boolean put(K k, V v) { // 因為取模運算要求均為整數運算，這裡key值不一定是整形， //所以調用JDK的hashcode()方法 // 取得key的hash值用來進行取模運算 int hash = k.hashCode(); // 將參數信息封裝為一個entry，entry即為哈希表中的「桶」中的元素 Entry<K, V> temp = new Entry(k, v, hash); if (setEntry(temp, container)) { // 如果哈希表中無此值便插入 size++; return true; } return false; } /* * 實現數據 取 的功能 */ public V get(K k) { Entry<K, V> entry = null; // 計算K的hash值 int hash = k.hashCode(); // 根據hash值找到下標 int index = indexFor(hash, container.length); // 根據index找到鏈表 entry = container[index]; // 若鏈表為空，返回null if (null == entry) { return null; } // 若不為空，遍歷鏈表，比較k是否相等,如果k相等，則返回該value while (null != entry) { if (k == entry.key || entry.key.equals(k)) { return entry.value; } entry = entry.next; } // 如果遍歷完了不相等，則返回空 return null; } /* * 將指定的節點temp添加到哈希表中 添加時判斷該結點是否已經存在 * 如果已經存在，返回false 添加成功返回true */ private boolean setEntry(Entry<K, V> temp, Entry<K, V>[] map) { // 根據hash值找到下標 int index = indexFor(temp.hash, map.length); // 找到下標位置對應的元素 Entry<K, V> entry = map[index]; if (null != entry) { // 若元素存在則遍歷整個鏈表，判斷值是否相等 while (null != entry) { // 判斷值是否相等除了要判斷值相等還要判斷地址是否相等 // 都相等的話就不存這個元素，返回false if ((temp.key == entry.key || temp.key.equals(entry.key)) && temp.hash == entry.hash && (temp.value == entry.value || temp.value.equals(entry.value))) { return false; } else if (temp.key == entry.key && temp.value != entry.value) { entry.value = temp.value; return true; } else if (temp.key != entry.key) { // 不相等則往由鏈表往下比較 if (null == entry.next) { break; // 到達鏈尾則跳出循環 } entry = entry.next; // 沒到鏈尾則繼續下一個元素 } } // 此時遍歷到了鏈尾還沒相同的元素則把它掛在鏈尾 addEntry2Container(entry, temp); return true; } // 若不存在,直接設置初始化元素 setFirstEntry(index, temp, map); return true; } //桶中沒有元素，把這個元素設為初始化元素 private void setFirstEntry(int index, Entry<K, V> temp, Entry<K, V>[] map) { if (size > max) { reSize(map.length * 2); } map[index] = temp; temp.next = null; } //把hash值相同的元素掛在鏈表的尾部 private void addEntry2Container(Entry<K, V> temp, Entry<K, V> entry) { if (size > max) { reSize(container.length * 2); } entry.next = temp; } /* * 擴容的方法 */ private void reSize(int newSize) { // 創建一個新的數組 Entry<K, V>[] newMap = new Entry[newSize]; max = (int) (loadFactor * newSize); // 將原來數組中的元素遷移到新數組中 for (int i = 0; i < container.length; i++) { Entry<K, V> entry = container[i]; // 因為「桶」是鏈表，所以還要用next把桶中的元素連接起來 while (null != entry) { setEntry(entry, newMap); entry = entry.next; } } container = newMap; } /* * 根據hashcode，容器數組長度，計算hashcode在容器數組中的下表值 */ private int indexFor(int hashcode, int lengthOfContainer) { return hashcode & (lengthOfContainer - 1); // h & (length-1)就相當於h%length，用於計算index也就是在table數組中的下標 }}

其中table就是HashMap的核心，即為Entry數組，為數據結構圖中綠色的部分；size 為HashMap中的Entry的數目，即數據結構中橙黃色部分的數目；loadFactor為載入因子，表示HashMap中元素的填滿的程度。當載入因子大時，HashMap中的元素比較多，因而更容易產生哈希衝突；而當載入因子比較小時，HashMap中的元素比較少，會浪費空間。實時載入因子的計算方法為size/capacity，capacity即為 table數組的數目，均為2的n次冪。載入因子的默認值為0.75，即當實時載入因子到達0.75時，就會進行HashMap的擴容了。threshold表示當HashMap的size大於threshold時會執行哈希表的擴容即resize操作。 所以，其計算方法為 threshold = capacity * loadFactor。

這裡要說明的幾個點：

• 我們知道HashMap是由數組+鏈表組成，那麼HashMap存在的兩個極端就是HashMap可能退化為了一個數組或者是一個鏈表。
• HashMap的resize是一個十分消耗資源的過程，在此基礎上，就要求我們在哈希表的創建之初對數據的數量有一個良好的估計，還有就是rehash方法的優化。
• Hash表的resize方法，在這裡我們可以簡單的理解為原有的桶不裝不下這些數據了，還需要更多的桶，那麼就是在hash函數中，我們還需要更大的模，產生更多的結果。

HashMap方法操作的核心是找到key值所在的桶，然後便是按照單鏈表的操作進行查找、插入、刪除或者其它操作了。

put 方法主要進行以下4個步驟：

1、判斷key是否是null，是null的話單獨處理，因為key為null總會將數據存儲在第一個桶里；

2、計算key的哈希值，並尋找到要存放該key的桶；

3、判斷桶內是否有該key，如果有的話，將老數據進行覆蓋；

4、將該key的相關數據添加到該桶里。

get 方法要比 put 方法簡單很多，主要流程為：

1、判斷key是否是null，是null的話單獨處理，因為key為null總會將數據存儲在第一個桶里；

2、計算key的哈希值，並尋找到要存放該key的桶；

3、尋找桶內是否有該key的Entry，如果有，返回其value值，如果沒有，返回null。

在我的代碼里只實現了哈希表的存和取的方法，其他的方法之後會更新，後面也會分析一下：

• HashMap和HashTable的區別。
• 一致性哈希。
• JDK中HashMap源碼解讀

4.我的HashMap和JDK中的HashMap在存取效率上的比較

/** * 測試我的哈希表的存取速度 * */public class testMyHashMap { public static void main(String[] args) { MyHashMap<String, String> testmap = new MyHashMap<String, String>(); long startTime = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { testmap.put("user" + i, "password" + i); } long endTime = System.currentTimeMillis(); System.out.println("MyHashMap Insert Time:" + (endTime - startTime)); Long BeginTime = System.currentTimeMillis();// 記錄BeginTime testmap.get("user" + 9999); Long EndTime = System.currentTimeMillis();// 記錄EndTime System.out.println("MyHashMap seach time：" + (EndTime - BeginTime)); }}

結果為：

/* * JDK中哈希表的存取速度 */import java.util.HashMap;import java.util.Map;public class TestJDK { public static void main(String[] args) { HashMap<String, String> map = new HashMap<String, String>(); long startTime = System.currentTimeMillis(); for (int i = 0; i < 100000; i++) { map.put("user" + i, "password" + i); } long endTime = System.currentTimeMillis(); System.out.println("JDK HashMap Insert Time:" + (endTime - startTime)); Long BeginTime = System.currentTimeMillis();// 記錄BeginTime map.get("user" + 9999); Long EndTime = System.currentTimeMillis();// 記錄EndTime System.out.println("JDK HashMap seach time：" + (EndTime - BeginTime)); }}

結果為：

為什麼我寫的哈希表存入的速度比JDK的快呢？？？

下次帶你一起解讀源碼！！！