1.1基本概念

散列表也叫作雜湊表（hash table），這種資料結構提供了鍵（Key）和值（Value）的對映關係。只要給出一個Key，就可以高效查詢到它所匹配的Value，時間複雜度接近於O(1) 。

儲存原理

散列表在本質上也是一個陣列，其中key對應陣列下標，key主要以字串為主，透過hash函式把key和陣列下標進行轉換，把任意長度的輸入透過雜湊演算法轉換成固定型別、固定長度的雜湊值。

hash演算法很多種，CRC16、CRC32、siphash 、murmurHash、times 33等 。java中簡單一種實現方式如下

//陣列下標=取key的hashcode模陣列的長度後的餘數index = HashCode (Key) % Array.lengthint index=Math.abs("Hello".hashCode())%10; （0-9）

這種Hash計算方式叫固定Hash方式，也稱傳統Hash.在陣列長度固定的時候能快速檢索，但是陣列長度變化時，需要重新計算hash%陣列長度，效能很低，另外hash值取模之後可能導致值重複。大概過程如下：

1.2 操作1.2.1 寫操作(put)

在散列表中插入新的鍵值對（在JDK中叫作Entry或Node）。

第一步：透過雜湊函式，把Key轉化成陣列下標

第二步：如果陣列下標對應的位置沒有元素，就把這個Entry填充到陣列下標的位置

Hash碰撞(衝突)：由於陣列的長度是有限的，當插入的Entry越來越多時，不同的Key透過雜湊函式獲得的下標有可能是相同的，這種情況，就叫作雜湊衝突。 其中陣列長度越小，碰撞的可能性越高

解決辦法：

方式一：開放定址法：開放定址法的原理是當一個Key透過雜湊函式獲得對應的陣列下標已被佔用時，就尋找下一個空檔位置

Java中，ThreadLocal所使用的就是開放定址法。

方式二、連結串列法

陣列的每一個元素不僅是一個Entry物件，還是一個連結串列的頭節點。每一個Entry物件透過next指標 指向它的下一個Entry節點。當新來的Entry對映到與之衝突的陣列位置時，只需要插入到對應的鏈 表中即可，預設next指向null。

1.2.2 讀操作（get）

讀操作就是透過給定的Key，在散列表中查詢對應的Value.

第1步，透過雜湊函式，把Key轉化成陣列下標

第2步，找到陣列下標所對應的元素，如果key不正確，說明產生了hash衝突，則順著頭節點遍歷該單鏈表，再根據key即可取值.

1.2.3 Hash擴容（resize）

因散列表是基於陣列實現的，所以散列表也需要擴容。當經過多次元素插入，散列表達到一定飽和度時，Key對映位置發生衝突的機率會逐漸提高。這樣一來，大量元素擁擠在相同的陣列下標位置，形成很長的連結串列，對後續插入操作和查詢操作的效能都有很大影響。

影響擴容的因素有兩個 Capacity：HashMap的當前長度 LoadFactor：HashMap的負載因子（閾值），預設值為0.75f 。

當HashMap.Size >= Capacity×LoadFactor時，需要進行擴容。

擴容步驟

1. 建立一個新的Entry空陣列，長度是原陣列的2倍

1. 重新Hash，遍歷原Entry陣列，把所有的Entry重新Hash到新陣列中

關於HashMap的實現，JDK 8和以前的版本有著很大的不同。當多個Entry被Hash到同一個陣列下標位置時，為了提升插入和查詢的效率，HashMap會把Entry的連結串列轉化為紅黑樹這種資料結構。 JDK1.8前在HashMap擴容時，會反序單鏈表，這樣在高併發時會有死迴圈的可能

1.2.4 手寫一個HashMap

為了演示原理，不考慮擴容、不考慮引數合法性，k-v都採用String型別。

由上面的原理了解，HashMap其實就是一個數組，陣列元素是一個單向連結串列，連結串列就有節點Node,先新建Node

package com.david.hashtable.hashmap;/** * 節點資料，包含存入的key,value,以及單鏈表指向下一個節點的引用 */public class Node {    String key;    String value;    Node next;    public Node(String key, String value, Node next) {        this.key = key;        this.value = value;        this.next = next;    }}

線性連結串列：包含head，以及addNode,getVal方法。

addNode方法：遍歷連結串列，首先判斷連結串列是否存在相同key的節點，存在的話就直接覆蓋掉，並將覆蓋標記變為true,當節點node.next==null的時候，說明遍歷完成，如果覆蓋標記為false，則在尾部新增一個新的節點。

getVal：遍歷連結串列，查詢key相同的節點，並返回其value值

package com.david.hashtable.hashmap;public class ListNode {    Node head;    /**     * 新增節點     * @param key     * @param value     */    public void addNode(String key,String value){        if (head==null) return;        Node node =new Node(key,value,null);        Node tmp=head;        //遍歷連結串列        boolean b=false;        while (true){            //連結串列中有相同key,則覆蓋            if (key.equals(tmp.key)){                tmp.value=value;                b=true;            }            if (tmp.next==null){                break;            }            tmp=tmp.next;        }        if (!b){            tmp.next=node;        }    }    /**     * 透過key獲取值     * @param key     * @return     */    public String getVal(String key){        if (head==null) return null;        if (head.next==null){            return head.value;//只有一個節點        }else {            Node tmp=head;            while (tmp!=null){                if (key.equals(tmp.key)){                    return tmp.value;                }                tmp=tmp.next;            }        }        return null;    }}

HashMap實現：底層維護一個ListNode連結串列陣列，初始容量固定8個，size記錄連結串列個數

put方法：向map新增元素，首先獲取key的hashcode，並取絕對之後對陣列長度取餘，找到陣列對應餘數下標的ListNode,並判斷是否為空，來決定是對連結串列新增節點還是新增一個節點

get方法：對key進行hashcode對映，直接呼叫ListNode的getVal方法獲取元素值。

package com.david.hashtable.hashmap;public class MyHashMap {    //陣列初始化8個容量    ListNode[] map=new ListNode[8];    //元素個數    private int size;    /**     * 存值     * @param key     * @param value     */    public void put(String key,String value){        if (size>=map.length*0.75){            System.out.println("map 需要擴容");            return;        }        int index=Math.abs(key.hashCode())%map.length;        //先看陣列該位置有沒有值        ListNode listNode = map[index];        //        if (listNode==null){            //該位置無值            ListNode ln=new ListNode();            ln.head=new Node(key,value,null);            map[index]=ln;            size++;        }else{            //有值，hash衝突了            listNode.addNode(key,value);        }    }    /**     * 透過key獲取值     * @param key     * @return     */    public String get(String key){        int i=Math.abs(key.hashCode())%map.length;        ListNode listNode = map[i];        if (listNode!=null){            return listNode.getVal(key);        }        return null;    }}

時間複雜度分析：

寫操作：O(1)+O(m)=O(m),需要遍歷連結串列

讀操作：O(1)

hash衝突寫連結串列：O(1)

Hash衝突讀連結串列：O(n),因為讀取需要遍歷連結串列

優缺點:

優點：讀寫快

缺點：雜湊表的元素沒有排序，hash衝突，擴容需要重新計算hash

1.3 散列表應用1.3.1 HashMap

JDK1.7中HashMap使用一個table陣列來儲存資料，用key的hashcode取模來決定key會被放到數組裡的位置，如果hashcode相同，或者hashcode取模後的結果相同，那麼這些key會被定位到Entry陣列的同一個格子裡，這些key會形成一個連結串列，在極端情況下比如說所有key的hashcode都相同，將會導致這個連結串列會很長，那麼put/get操作需要遍歷整個連結串列，那麼最差情況下時間複雜度變為O（n）,而且擴容會導致死鏈。針對JDK1.7中的這個效能缺陷，JDK1.8中的table陣列中可能存放的是連結串列結構，也可能存放的是紅黑樹結構，如果連結串列中節點數量不超過8個則使用連結串列儲存，超過8個會呼叫treeifyBin函式，將連結串列轉換為紅黑樹。那麼即使所有key的hashcode完全相同，由於紅黑樹的特點，查詢某個特定元素，也只需要O（logn）的開銷 。

1.3.2 字典

Redis字典dict又稱散列表（hash），是用來儲存鍵值對的一種資料結構。Redis整個資料庫是用字典來儲存的。（K-V結構）對Redis進行CURD操作其實就是對字典中的資料進行CURD操作。Redis字典實現包括：字典(dict)、Hash表(dictht)、Hash表節點(dictEntry)。

1.3.3 布隆過濾器

布隆過濾器的原理是，當一個元素被加入集合時，透過K個Hash函式將這個元素對映成一個數組中的K 個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如 果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的 基本思想。

1.3.4 點陣圖

Bitmap 的基本原理就是用一個 bit 來標記某個元素對應的 Value，而 Key 即是該元素。由於採用一個 bit 來儲存一個數據，因此可以大大的節省空間。