為什么需要哈希表摸吠？

舉個例子（摘自漫畫算法）：

在上學時需要學習英語嚎花，而在當時有很多的電子詞典紊选，同學們遇到不會的單詞兵罢，只要在這個電子詞典上輸入單詞的英文，就可以查出中文的含義巩那。

當時的英語老師強烈反對使用這樣的工具此蜈，因為電子詞典查出來的中文資料太有限即横，而傳統(tǒng)的紙質(zhì)詞典可以查到單詞的多種含義、詞性裆赵、例句等东囚。

但是，同學們還是傾向于使用電子詞典战授。因為電子詞典實在太方便了页藻，只要輸入要查找的單詞，一瞬間就可以得到結(jié)果植兰，而不需要像紙質(zhì)詞典那樣繁瑣地進行人工查找份帐。

在我們程序員的世界里，往往也需要在內(nèi)存中存放這樣一個“詞典”弥鹦，方便我們進行高效的查詢和統(tǒng)計。

例如開發(fā)一個學生管理系統(tǒng)，需要有通過輸入學號快速查出對應學生的姓名的功能彬坏。這里不必每次都去查詢數(shù)據(jù)庫朦促，而可以在內(nèi)存建立一個緩存表，這樣做可以提高查詢效率栓始。

再如我們需要統(tǒng)計一本英文書里某些單詞出現(xiàn)的頻率务冕，就需要遍歷整本書的內(nèi)容，把這些單詞出現(xiàn)的次數(shù)記錄在內(nèi)存中幻赚。

因為這些需求禀忆，一個重要的數(shù)據(jù)結(jié)構(gòu)誕生了，這個數(shù)據(jù)結(jié)構(gòu)就叫做散列表落恼。

散列表也叫做哈希表箩退，這種數(shù)據(jù)結(jié)構(gòu)提供了鍵和值的映射關(guān)系。只要給出key佳谦，就可以高效的查找所對應的值戴涝。

那么，散列表是如何根據(jù)key來快速查找到所匹配的value呢钻蔑？

哈希函數(shù)

散列表在本質(zhì)上是一個數(shù)組啥刻，為什么底層使用數(shù)組呢？

數(shù)組的特點是它的隨機訪問能力咪笑，根據(jù)索引來進行訪問可帽，所以我們需要一個“中轉(zhuǎn)站”，通過某種方式窗怒，把鍵轉(zhuǎn)換為索引映跟，而這個中轉(zhuǎn)站就叫做哈希函數(shù)。

哈希函數(shù).png

那么這個所謂的哈希函數(shù)是如何實現(xiàn)的呢扬虚？

在不同的語言中申窘，哈希函數(shù)的實現(xiàn)方式是不一樣的。這里以Java的常用集合HashMap為例孔轴，來看一看哈希函數(shù)在Java中的實現(xiàn)剃法。

在Java及大多數(shù)面向?qū)ο蟮恼Z言中，每一個對象都有屬于自己的hashcode路鹰，這個hashcode是區(qū)分不同對象的標識贷洲。無論對象自身類型是什么，它們的hashcode都是一個整型變量晋柱。

既然都是整型變量优构，想要轉(zhuǎn)換成數(shù)組的索引也就不難實現(xiàn)了。最簡單的轉(zhuǎn)換方式就是按照數(shù)組的長度進行取模雁竞。

通過哈希函數(shù)钦椭，我們可以把字符串或其他類型的鍵轉(zhuǎn)換為數(shù)組的索引拧额。

例如：給出一個長度為10的數(shù)組，當key=24321時彪腔，index=HashCode("24321") % Array.length侥锦。

哈希表的實現(xiàn)

1、寫操作
寫操作就是在哈希表中插入新的元素德挣。分為兩個步驟：

第一步：通過哈希函數(shù)恭垦，把key轉(zhuǎn)化為數(shù)組的索引

第二步：如果當前key所對應的索引中沒有元素，就把新元素添加進去格嗅。

注意：由于數(shù)組的長度是有限的番挺，當插入的元素越來越多，我們很難保證每一個鍵通過哈希函數(shù)轉(zhuǎn)換

為對應不同的索引屯掖，在這種情況下玄柏，我們不得不處理一個在哈希表中關(guān)鍵的問題，兩個不同的鍵贴铜，通過哈希函數(shù)轉(zhuǎn)換為同一個索引粪摘，這種情況稱為哈希沖突，這也是哈希表中最復雜的阀湿。

解決方式：

• 開放尋址法

  開放尋址法很簡單赶熟，當一個鍵通過哈希函數(shù)轉(zhuǎn)換為索引并且這個索引已被占用時瑰妄，我們可以“另謀高就”陷嘴，尋找下一個空檔的位置。

  例如间坐，newKey通過哈希函數(shù)轉(zhuǎn)換為索引2灾挨，該索引在數(shù)組中已經(jīng)被占用了，那么就向后移動一位竹宋，看看索引為3的位置是否被占用了劳澄，如果占用了，那么繼續(xù)向后移動一位蜈七，看看索引為4的位置是否被占用了秒拔，如果沒有占用，就把key3存放到數(shù)組索引為4的索引飒硅。

  如圖：

  開放尋址法1.png

  開放尋址法2.png

  開放尋址法3.png

  這就是開放尋址法的基本思路砂缩。當然，如果遇到哈希沖突時三娩，尋址方式有很多種庵芭，在這里只是簡單的舉個例子。

• 鏈地址法

  鏈地址法說白就是一個鏈表的數(shù)組雀监，數(shù)組當中每一個元素都是一個鏈表双吆，當遇到哈希沖突時，只需要插入對應的鏈表即可。

2好乐、讀操作

讀操作就是通過給定的鍵匾竿，在哈希表中查找對應的值。分為兩個步驟：

第一步：通過哈希函數(shù)曹宴，把鍵轉(zhuǎn)換為索引搂橙。

第二步：通過索引找到對應的元素，再比較鍵笛坦，如果鍵相等区转，那么就找到了，如果不相等版扩，繼續(xù)找废离。

3、擴容

由于哈希表的底層實際上就是個數(shù)組礁芦，那么哈希表也就要涉及到擴容的問題了蜻韭。

首先，什么時候需要進行擴容呢柿扣？

當經(jīng)過多次寫操作時肖方，哈希表達到一定的飽和度時，鍵映射位置發(fā)生沖突的概率會逐漸提高未状。這樣一來俯画，大量的元素擁擠在相同的數(shù)組索引位置，會形成很長的鏈表司草，對后續(xù)的寫操作和讀操作的性能會造成很大的影響艰垂。這時，哈希表就需要擴展它的長度埋虹，也就是進行擴容猜憎。

擴容分為兩個步驟：

• 擴容

  創(chuàng)建一個新的數(shù)組，并且新的數(shù)組的長度是原來的數(shù)組的2倍搔课。

• 重新Hash

  遍歷原數(shù)組胰柑，把所有的元素重新Hash到新數(shù)組當中。

注意：在Java中爬泥，關(guān)于HashMap的實現(xiàn)柬讨，在Java8之前HashMap的實現(xiàn)每個位置對應著一個鏈表。不過急灭，從Java8開始有了一個改變姐浮，在初始的時候哈希表的每個位置依然是一個鏈表，但是葬馋，當哈希沖突達到一定的程度時卖鲤，會把哈希表中的每一個位置從鏈表轉(zhuǎn)成紅黑樹肾扰！

整體代碼如下（在這里哈希沖突的解決方式使用的是鏈地址法，只不過把鏈表替換為了紅黑樹）：

/**
 * 描述：哈希表（通過紅黑樹解決哈希沖突問題）
 * <p>
 * Create By ZhangBiao
 * 2020/5/12
 */
public class HashTable<K, V> {

    private static final int UPPER_TOL = 10;

    private static final int LOWER_TOL = 2;

    private static final int INIT_CAPACITY = 7;

    private TreeMap<K, V>[] hashtable;

    private int size;

    private int M;

    public HashTable(int M) {
        this.M = M;
        this.size = 0;
        this.hashtable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        this(INIT_CAPACITY);
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if (map.containsKey(key)) {
            map.put(key, value);
        } else {
            map.put(key, value);
            size++;
            if (size >= UPPER_TOL * M) {
                resize(2 * M);
            }
        }
    }

    private void resize(int newM) {
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        int oldM = this.M;
        this.M = newM;
        for (int i = 0; i < oldM; i++) {
            for (K key : hashtable[i].keySet()) {
                newHashTable[hash(key)].put(key, hashtable[i].get(key));
            }
        }
        this.hashtable = newHashTable;
    }

    public V remove(K key) {
        V ret = null;
        TreeMap<K, V> map = hashtable[hash(key)];
        if (map.containsKey(key)) {
            ret = map.remove(key);
            size--;
            if (size <= LOWER_TOL * M && M > INIT_CAPACITY) {
                resize(M / 2);
            }
        }
        return ret;
    }

    public void set(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if (!map.containsKey(key)) {
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        map.put(key, value);
    }

    public boolean contains(K key) {
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key) {
        return hashtable[hash(key)].get(key);
    }

}