1.哈希表結(jié)構(gòu)的優(yōu)勢蹦锋？

哈希表作為一種優(yōu)秀數(shù)據(jù)結(jié)構(gòu)
本質(zhì)上存儲結(jié)構(gòu)是一個數(shù)組冲杀，輔以鏈表和紅黑樹
數(shù)組結(jié)構(gòu)在查詢和插入刪除復(fù)雜度方面分別為O(1)和O(n)
鏈表結(jié)構(gòu)在查詢和插入刪除復(fù)雜度方面分別為O(n)和O(1)
二叉樹做了平衡 兩者都為O(lgn)
而哈希表兩者都為O(1)

2.哈希表簡介

哈希表本質(zhì)是一種(key,value)結(jié)構(gòu)
由此我們可以聯(lián)想到平斩，能不能把哈希表的key映射成數(shù)組的索引index呢力喷？
如果這樣做的話那么查詢相當(dāng)于直接查詢索引家卖，查詢時間復(fù)雜度為O(1)
其實(shí)這也正是當(dāng)key為int型時的做法 將key通過某種做法映射成index寿谴，從而轉(zhuǎn)換成數(shù)組結(jié)構(gòu)

3.數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)步驟

1.使用hash算法計(jì)算key值對應(yīng)的hash值h(默認(rèn)用key對應(yīng)的hashcode進(jìn)行計(jì)算(hashcode默認(rèn)為key在內(nèi)存中的地址)),得到hash值
2.計(jì)算該(k,v)對應(yīng)的索引值index 
  索引值的計(jì)算公式為 index = (h % length) length為數(shù)組長度
3.儲存對應(yīng)的(k,v)到數(shù)組中去捕发，從而形成a[index] = node<k,v>,如果a[index]已經(jīng)有了結(jié)點(diǎn)
即可能發(fā)生碰撞疏旨，那么需要通過開放尋址法或拉鏈法(Java默認(rèn)實(shí)現(xiàn)）解決沖突

當(dāng)然這只是一個簡單的步驟，只實(shí)現(xiàn)了數(shù)組 實(shí)際實(shí)現(xiàn)會更復(fù)雜
hash表 數(shù)組類似下圖

兩個重要概念

哈希算法

h 通過hash算法計(jì)算得到的的一個整型數(shù)值 
h可以近似看做一個由key的hashcode生成的隨機(jī)數(shù)扎酷，區(qū)別在于相同的hashcode生成的h必然相同
而不同的hashcode也可能生成相同h檐涝，這種情況叫做hash碰撞，好的hash算法應(yīng)盡量避免hash碰撞
(ps:hash碰撞只能盡量避免霞玄，而無法杜絕,由于h是一個固定長度整型數(shù)據(jù),原則上只要有足夠多的輸入骤铃，就一定會產(chǎn)生碰撞)
關(guān)于hash算法有很多種，這里不展開贅述坷剧，只需要記住h是一個由hashcode產(chǎn)生的偽隨機(jī)數(shù)即可
同時需要滿足key.hashcode -> h 分布盡量均勻(下文會解釋為何需要分布均勻)
可以參考https://blog.csdn.net/tanggao1314/article/details/51457585

解決碰撞沖突

由上我們可以知道惰爬，不同的hashcode可能導(dǎo)致相應(yīng)的h即發(fā)生碰撞
那么我們需要把相應(yīng)的<k,v>放到hashmap的其他存儲地址

解決方法1：開放尋址法

通過在數(shù)組以某種方式尋找數(shù)組中空余的結(jié)點(diǎn)放置
基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時
以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1惫企，如果p1仍然沖突撕瞧，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2狞尔，…丛版，直到找出一個不沖突的哈希地址pi ，

解決方法1：鏈地址法

通過引入鏈表 數(shù)組中每一個實(shí)體存儲為鏈表結(jié)構(gòu)偏序，如果發(fā)生碰撞页畦，則把舊結(jié)點(diǎn)指針指向新鏈表結(jié)點(diǎn)，此時查詢碰撞結(jié)點(diǎn)只需要遍歷該鏈表即可
在這種方法下研儒，數(shù)據(jù)結(jié)構(gòu)如下所示
int類型數(shù)據(jù) hashcode 為自身值

鏈地址法示例圖

在JAVA中幾個細(xì)節(jié)點(diǎn)

1.為什么需要擴(kuò)容豫缨？擴(kuò)容因子大還是小好独令？

由于數(shù)組是定長的，當(dāng)數(shù)組儲存過多的結(jié)點(diǎn)時好芭，發(fā)生碰撞的概率大大增加燃箭，此時hash表退化成鏈表

過大的擴(kuò)容因子會導(dǎo)致碰撞概率大大提升，過小擴(kuò)容因子會造成存儲浪費(fèi)舍败，在Java中默認(rèn)為0.75

2.當(dāng)從哈希表中查詢數(shù)據(jù)時招狸，如果key對應(yīng)一條鏈表,遍歷時如何判斷是否應(yīng)該覆蓋？

當(dāng)遍歷鏈表時邻薯，如果兩個key.hashcode的h一致會調(diào)用equals()方法判斷是否為同一對象,equal的默認(rèn)實(shí)現(xiàn)是比較兩者的內(nèi)存地址

因此為什么Java強(qiáng)調(diào)當(dāng)重寫equals()時需要同時重寫hashcode()方法,假設(shè)兩個不同對象裙戏，在內(nèi)存中的地址不同分別為a和b,那么重寫equals()以后a.equals(b) =true 開發(fā)者希望把a(bǔ),b這兩個key視作完全相等
然而由于內(nèi)存地址的不同導(dǎo)致hashcode不同,會導(dǎo)致在hashmap中儲存2個本應(yīng)相同的key值

這里提供一個范例
public class Student {
    //學(xué)號
    public int student_no;
    //姓名
    public String name;
    
    @Override
    public boolean equals(Object o) {
        Student student = (Student) o;
        return student_no == student.student_no;
    }
    
}

通常情況下我們像上圖一樣期望通過判斷兩個Student的學(xué)號是否是否為同一學(xué)生
然而在使用map或set集合時產(chǎn)生出乎意料的結(jié)果

image.png

當(dāng)我們重寫hashcode()時

@Override
    public int hashCode() {
        return Objects.hash(student_no);
    }

可以看到現(xiàn)在可以正常使用集合框架中的一些特性

image.png

3.為什么在HashMap中數(shù)組的長度length = 2^n（初始值為16） ?

當(dāng)計(jì)算索引值index = h % length 由于計(jì)算機(jī)的取余操作速度很慢，而計(jì)算機(jī)的按位取余 & 的操作非吵谒担快,又因?yàn)?h%length = h & (length-1) (需要滿足length = 2^n) 因此規(guī)定了length = 2^n 加快index的計(jì)算速度 上式的證明參考http://yananay.iteye.com/blog/910460

4.HashMap的紅黑樹在哪里體現(xiàn)呢挽懦？

紅黑樹是JDK8中對hashmap作的一個變更，在JDK7之前木人，HashMap采用數(shù)組+鏈表的形式存儲數(shù)據(jù)，我們知道優(yōu)秀的hash算法應(yīng)避免碰撞的發(fā)生,但假如開發(fā)者使用了不合適的hash算法冀偶，O(1)級別的數(shù)組查詢會退化到O(n)級鏈表查詢醒第，因此在JDK8中引入紅黑樹的，當(dāng)一個結(jié)點(diǎn)的鏈表長度大于8時进鸠，鏈表會轉(zhuǎn)換成紅黑樹稠曼，提高查詢效率,而鏈表長度小于6時又會退化成鏈表

5.擴(kuò)容是如何觸發(fā)的?

當(dāng)hashmap中的size > loadFactory * capacity即會發(fā)生擴(kuò)容，size 也是數(shù)組結(jié)點(diǎn)和鏈表結(jié)點(diǎn)的總和,要明確擴(kuò)容是一個非常耗費(fèi)性能的操作客年，因?yàn)閿?shù)組的長度發(fā)生改變霞幅，需要對所有結(jié)點(diǎn)的索引值重新進(jìn)行計(jì)算,而在JDK8中對這部分進(jìn)行了優(yōu)化，詳細(xì)可以參考https://blog.csdn.net/aichuanwendang/article/details/53317351,在擴(kuò)容完后減輕了碰撞產(chǎn)生的影響

在正常的Hash算法下量瓜，紅黑樹結(jié)構(gòu)基本不可能被構(gòu)造出來司恳，根據(jù)概率論，理想狀態(tài)下哈希表的每個箱子中绍傲，元素的數(shù)量遵守泊松分布:

P(X=k) = (λ^k/k!)e^-λ,k=0,1,...

當(dāng)負(fù)載因子為 0.75 時扔傅，上述公式中 λ 約等于 0.5，因此箱子中元素個數(shù)和概率的關(guān)系如下:(參考https://blog.csdn.net/Philm_iOS/article/details/81200601)烫饼，下述分布來自源碼文檔

> * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

JDK的設(shè)計(jì)者為了開發(fā)者真是煞費(fèi)苦心= =