• TreeMap分析

1. 時間復(fù)雜度（平均）
   • 添加，刪除海诲，搜索：O(logn)
2. 特點(diǎn)
   • Key必須具備可比較性
   • 元素的分布是有序的
3. 實(shí)際應(yīng)用中炮叶，很多時候的需求
   • Map中存儲的元素不需要講究順序
   • Map中的Key不具備可比較性

不考慮順序哥遮，不考慮Key的可比較性笨使，Map有更好的實(shí)現(xiàn)方案，平均時間復(fù)雜度可達(dá)到O(1)竞阐，那就是采用哈希表來實(shí)現(xiàn)Map

• 需求

設(shè)計一個寫字樓通訊錄缴饭，存放所有公司的通訊信息，其要求如下

1. 座機(jī)號碼作為key（假設(shè)座機(jī)號碼最長是8位）骆莹，公司詳情（名稱颗搂，地址等）作為value
2. 添加，刪除汪疮，搜索的時間復(fù)雜度要求是O(1)

首先幢泼，我們可能想到的是使用TreeMap來實(shí)現(xiàn)睁宰，但是存在一個問題歼指，TreeMap的添加糠悯，刪除，搜索復(fù)雜度為O(logn)盏道，因此不符合要求稍浆。那我們可以這么做

private Company[] companies = new Company[100000000];
public void add(int phone,Company company){
    companies[phone] = company;
}
public void remove(int phone) {
    companies[phone] = null;
}
public Company get(int phone) {
    return companies[phone];
}

那么，最終，這些公司信息存儲到數(shù)組里面衅枫，在內(nèi)存中的一個什么樣的情況呢嫁艇？即如下圖這樣進(jìn)行存儲的

那么，通過這種方式弦撩，存在什么問題呢步咪？

1. 空間復(fù)雜度，非常大
2. 空間使用率極其低益楼，非常浪費(fèi)內(nèi)存空間

其實(shí)猾漫，上面的數(shù)組companies就是一個哈希表，一種典型的【空間換時間】

• 哈希表(Hash Table)

哈希表也叫做散列表（hash有“剁碎”的意思）

它是如何實(shí)現(xiàn)高效處理數(shù)據(jù)的感凤？

假設(shè)我們用哈希表來存儲以下三對數(shù)據(jù)

put(“Jack”,666);
put("Rose",777);
put("Kate",888);

那么悯周，哈希表在內(nèi)存中是怎樣存儲這三對數(shù)據(jù)的呢？

哈希表添加陪竿，搜索禽翼，刪除的流程

1. 利用哈希函數(shù)生產(chǎn)key對應(yīng)的index，復(fù)雜度為O(1)
2. 根據(jù)index操作定位數(shù)組元素族跛，復(fù)雜度為O(1)

• 哈希表是空間換時間的典型應(yīng)用
• 哈希函數(shù)闰挡，也叫做散列函數(shù)
• 哈希表內(nèi)部的數(shù)組元素，很多地方也叫Bucket（桶）庸蔼，整個數(shù)組叫Buckets或者Bucket Array

• 哈希沖突(Hash Collision)

哈希沖突也叫做哈希碰撞

解釋：2個不同的key解总，經(jīng)過哈希函數(shù)計算出相同的結(jié)果，即key1 ≠ key2姐仅，但是hash(key1) = hash(key2)

例如可能會出現(xiàn)以下這種情況

解決哈希沖突的常見方法

1. 開放定址法（Open Addressing）
   • 按照一定的規(guī)則，向其他地址探測刻盐，知道遇到空桶
2. 再哈希法(Re-Hashing)
   • 設(shè)計多個哈希函數(shù)
3. 鏈地址發(fā)(Separate Chaining)
   • 比如通過鏈表掏膏，將同一index的元素串起來[下圖]

• JDK1.8的哈希沖突解決方案

1. java官方是默認(rèn)使用單向鏈表將元素串起來
2. 在添加元素時，可能會由單向鏈表轉(zhuǎn)為紅黑樹來存儲
   • 比如當(dāng)哈希表容量≥64且單向鏈表的節(jié)點(diǎn)數(shù)量＞8的時候[下圖]
3. 當(dāng)紅黑樹節(jié)點(diǎn)數(shù)量少到一定程度時敦锌，又會轉(zhuǎn)為單向鏈表

所以在JDK1.8中的哈希表是使用鏈表+紅黑樹來解決哈希沖突的

??這里為什么使用單項鏈表馒疹？

1. 每次都要從頭還是遍歷，看當(dāng)前鏈表中元素的key是否已經(jīng)存在乙墙，如果存在颖变，就覆蓋，如果不存在听想，才添加
2. 單向鏈表比雙向鏈表少一個指針腥刹，可以節(jié)省內(nèi)存空間

• 哈希函數(shù)

在哈希表中，哈希函數(shù)的實(shí)現(xiàn)步驟大概如下

1. 先生成key的哈希值（必須是整數(shù)）
2. 再讓key的哈希值與數(shù)組的大小進(jìn)行相關(guān)運(yùn)算汉买，生成一個索引值衔峰，如下示例代碼所示

public int hash(Object key){
    return hash_code(key) % table.length;
}

為了提高效率，可以使用&位運(yùn)算取代%運(yùn)算【前提：將數(shù)組的長度設(shè)計為2的冪（2^n）】

public int hash(Object key){
    return hash_code(key) & (table.length - 1);
}

我們來回顧一下&運(yùn)算的特點(diǎn)：相同為上，兩個都為1時垫卤，結(jié)果才為1威彰，如下

 1001010
&1101101
---------
 1001000

那么我們來思考一下，為什么數(shù)組的長度要設(shè)計為2^n穴肘，那我們來看以下二進(jìn)制數(shù)與2的關(guān)系

1              2^0
10             2^1
100            2^3
1000           2^4
10000          2^5

同樣的歇盼，我們來看看二進(jìn)制數(shù)與2的冪次方-1的關(guān)系

0              2^0 - 1
01             2^1 - 1
011            2^3 - 1
0111           2^4 - 1
01111          2^5 - 1

你發(fā)現(xiàn)規(guī)律了嗎？

2^n - 1的二進(jìn)制結(jié)果评抚，全部都是1（n = 0 除外）

那么通過這個方法旺遮，來計算索引的話，是這樣的

 1001010
&1111111
---------
 1001010
 
 1001010
&   1111
---------
 0001010

我們發(fā)現(xiàn)盈咳，最終計算出來的結(jié)果就是原來的hash值的結(jié)果耿眉，但是需要注意的是，通過&運(yùn)算后鱼响，計算出來的結(jié)果鸣剪，必然小于數(shù)組長度 - 1

良好的哈希哈數(shù)是怎么樣的？

1. 讓哈希值更加均勻分布→減少哈希沖突次數(shù)→提升哈希表的性能

• 如何生成key的哈希值

key的常見種類可能有：整數(shù)丈积，浮點(diǎn)數(shù)筐骇，字符串，自定義對象

不同種類的key江滨，哈希值的生成方式不一樣铛纬，但目標(biāo)是一直的

1. 盡量讓每一個key的哈希值都是唯一的
2. 盡量讓key的所有信息都參與運(yùn)算

注意：在Java中，HashMap的key必須實(shí)現(xiàn)hashCode唬滑，equals方法告唆，也允許key為null

接下來，看看常見類型生成哈希值的方式

整數(shù)

直接使用該整數(shù)當(dāng)哈希值晶密，比如10的哈希值就是10

浮點(diǎn)數(shù)

將浮點(diǎn)數(shù)存儲的二進(jìn)制格式轉(zhuǎn)換為整數(shù)后擒悬，當(dāng)做哈希值

Long和Double的哈希值

在Java官方，哈希值只能是int類型稻艰，因此Long類型與Double類型的長度懂牧，都超過了int類型的長度，因此需要轉(zhuǎn)換

官方對Long是這樣處理的

public  static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

對Double類型是這樣處理的

public  static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

其中>>> 與^的作用：將高32bit和低32bit混合計算出32bit的哈希值尊勿，可以充分利用所用信息計算出哈希值

符號>>>表示無符號右移

符號^表示異或（相同為0僧凤，不同為1）

字符串的哈希值

首先我們來思考一個問題！

整數(shù)5489是如何算出來的元扔？

其實(shí)5489是通過 5 * 10^3 + 4 * 10^2 + 8 * 10^1 + 9 * 10^0躯保，這樣算出來的。那么同樣的摇展，字符串也可以通過類似于這種的方式計算

字符串也是由若干個字符組成的

例如：現(xiàn)在有字符串jack吻氧，它是由字符j,a,c,k組成的溺忧，并且我們知道，字符的本質(zhì)就是一個整數(shù)盯孙，那么jack的哈希值可以表示為j * n^3 +a * n^2 + c * n^1 + k * n^0,通過等式變換為[(j * n + a) * n + c] * n + k鲁森。

在JDK中，乘數(shù)n的值為31振惰，為什么使用31歌溉？因?yàn)?1是一個奇素數(shù)，JVM會將31 * i優(yōu)化為(i << 5) - i

那么骑晶，字符串的哈希值可以通過如下的示例進(jìn)行計算

String string = "jack";
int len = string.length();
int hashCode = 0;
for (int i = 0; i < len; i++) {
    char c = string.charAt(i);
    hashCode = hashCode * 31 + c;
}

到這里痛垛，我們都知道整數(shù)，浮點(diǎn)數(shù)桶蛔，字符串的哈希值該如何計算了匙头。但是，好在這些都不用我們自己去計算仔雷，在Java官方蹂析，都已經(jīng)給我們計算好了，直接對應(yīng)的對象類型碟婆，調(diào)用hashCode()方法就可以了电抚，計算結(jié)果與我們自己計算的一致。

但是竖共，我們還有一種類型的哈希值沒有計算蝙叛，那就是自定義類型。

自定義類型的哈希值

如果我們對自定義對象求哈希值的話公给，在Java官方借帘，同樣是右默認(rèn)實(shí)現(xiàn)的，但是需要注意的是妓布，在默認(rèn)實(shí)現(xiàn)中姻蚓，其哈希值與該自定義對象在內(nèi)存中的位置有關(guān)，因此就會有以下的問題

Person p1 = new Person(18,1.85l,"jack");
Person p2 = new Person(18,1.85l,"jack");

最終p1,p2計算出來的哈希值是不一樣的匣沼。因此假設(shè)我們現(xiàn)在有需求，一個Person捂龄，如果它的age释涛，height，name都相同的話倦沧，則認(rèn)為是同一個Person對象唇撬。此時我們就需要手動計算自定義對象的哈希值，因此可以通過如下的示例進(jìn)行計算

public int hashCode(){
    int hashCode = Integer.hashCode(age);
    hashCode = hashCode * 31 + Float.hashCode(height);
    hashCode = hashCode * 31 + (name != null ? name.hashCode() : 0);
    return hashCode;
}

通過自己實(shí)現(xiàn)計算自定義對象的哈希值以后展融，以上兩個Person對象的哈希值相同了窖认。

但是需要注意，hashCode相等的兩個對象，不一定是同一個對象扑浸，因?yàn)閰?shù)的值不同烧给，最終計算出來的值是一樣的，所以不能認(rèn)為hashCode相同的對象是同一個對象喝噪，如果要判斷是否為同一個對象础嫡，我們還需要實(shí)現(xiàn)以下的示例方法

public boolean equals(Object obj) {
    //內(nèi)存地址相等
    if (this == obj) return true;
    //obj為空或者不是同一種類型
    if (obj == null || !(obj instanceof Person)) return false;
    //最后比較成員變量
    Person person = (Person)obj;
    return person.age == age
            && person.height == height
            && (person.name == null ? name == null : person.name.equals(name));
}

只有這樣，最終才能判斷出兩個對象是否相等酝惧。

總結(jié)：

• 重寫hashCode方法的作用是計算索引
• 重寫equals方法的作用是當(dāng)哈希值沖突的時候榴鼎，判斷兩個對象是否相等

自定義對象作為key

自定義對象作為key，最好是同時重寫hashCode,equals方法

• equals：用來判斷2個key是否為同一個key
  • 自反性：對于任何非null的x晚唇，x.equals(x)必須返回true
  • 對稱性：對于任何非null的x,y,如果y.equals(x)返回true巫财，x.equals(y)必須返回true
  • 傳遞性：對于任何非null的x,y,z,如果x.equals(y),y.equals(z)返回true，那么x.equals(z)必須返回true
  • 一致性：對于任何非null的x,y哩陕，只要equals的比較操作在對象中所用的信息沒有被修改平项，對此調(diào)用x.equals(y)就會一致的返回true，或者一致的返回false
  • 對于任何非null的x,x.equals(null)必須返回false
• hashCode：必須保證equals為true的兩個key的哈希值一樣
• 反過來萌踱，如果hashCode相等的key葵礼，不一定equals為true

那么問題來了，在我們計算自定義對象的哈希值時并鸵，如果哈希值太大鸳粉，整型溢出了怎么辦？

這種情況我們不用做任何處理园担，我們只需要計算出一個整型的值就可以了届谈。溢出了也沒有關(guān)系

另外，如果不重寫hashCode方法弯汰，只重寫equals艰山，會有什么后果？

可能會導(dǎo)致2個equals為true的key同時存在哈希表中

• 關(guān)于31的討論

31 * i = (2^5 - 1) * i = i * 2^5 - 1 = (i << 5) - 1

1. 因?yàn)?1不僅僅是符合2^n - 1,并且它還是一個奇素數(shù)（既是奇數(shù)咏闪，又是素數(shù)曙搬，也叫做質(zhì)數(shù)）
2. 素數(shù)與其他數(shù)相乘的結(jié)果，比其他方式更容易產(chǎn)生唯一性鸽嫂，減少哈希沖突
3. 最終選擇31是經(jīng)過觀測分布結(jié)果后的選擇

• 哈希表的擴(kuò)容

在哈希表的擴(kuò)容過程中纵装，會涉及到一個裝填因子（Load Factor）的概念

裝填因子（Load Factor）：節(jié)點(diǎn)總數(shù)量/哈希表數(shù)組長度，也叫做負(fù)載因子

在JDK1.8的HashMap中据某，如果裝填因子超過0.75橡娄，桶數(shù)量就會擴(kuò)容為原來的2倍

我們擴(kuò)容的方案是遍歷舊的表對象，然后將表對象中的所有元素癣籽，移動到新的表中挽唉。其中將桶數(shù)量擴(kuò)容以后滤祖，不僅可以提高哈希表的性能，而且還能減少哈希碰撞的次數(shù)瓶籽。

關(guān)于擴(kuò)容的實(shí)現(xiàn)匠童，可以參考demo中的void resize()函數(shù)

通過對比，我們來看以下處理相同數(shù)量的內(nèi)容棘劣，擴(kuò)容前與擴(kuò)容后的對比

擴(kuò)容前處理900萬條數(shù)據(jù)所花的時間

擴(kuò)容后處理900萬條數(shù)據(jù)所花的時間

我們看到俏让，處理900萬條數(shù)據(jù)，擴(kuò)容前后相差了接近2秒鐘是時間茬暇∈孜簦可見提升是多么的明顯。糙俗、

所以雖然我們在擴(kuò)容的那一刻勒奇，消耗的性能稍微大一點(diǎn)，但是從整體來講巧骚，效率是提升了的赊颠。

• HashMap VS TreeMap

我們來對比一下哈希表與紅黑樹映射表之間，性能的差異

我們還是處理900萬條數(shù)據(jù)劈彪，我們得到以下的結(jié)果

最終我們看到竣蹦，哈希表的性能明顯優(yōu)于紅黑樹映射表的性能。

那關(guān)于HashMap和TreeMap應(yīng)該如何選擇呢沧奴？

• 如果元素具備可比較性痘括，并且要求升序遍歷（按照元素從小到大），此時應(yīng)該選擇TreeMap

• 遍歷是無序的滔吠，選擇HashMap

• LinkedHashMap

在HashMap的技術(shù)上纲菌，維護(hù)元素的添加順序，使得遍歷的結(jié)果是遵從添加順序的

下圖是我們前面的HashMap疮绷，假設(shè)索引03中的元素添加順序?yàn)?7,21,31,41,97,52,42,83

如何維護(hù)每個元素的添加順序呢翰舌？我們可以通過在LinkedHashMap中增加一個指針，該指針指向下一個添加的元素冬骚，如下圖所示

因此我們只需要在原來紅黑樹節(jié)點(diǎn)的基礎(chǔ)上椅贱，增加兩個字段，一個用來指向當(dāng)前節(jié)點(diǎn)的上一個節(jié)點(diǎn)只冻，一個用來指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)夜涕，就可以將所有節(jié)點(diǎn)，通過鏈表的形式串起來属愤。

LinkedHashMap刪除注意點(diǎn)

由于我們知道，在紅黑樹中刪除節(jié)點(diǎn)時酸役，最終真正被刪除掉的節(jié)點(diǎn)是葉子節(jié)點(diǎn)住诸，此時驾胆，如果我們刪除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，紅黑樹會使用前驅(qū)節(jié)點(diǎn)或者后繼節(jié)點(diǎn)來替換當(dāng)前的節(jié)點(diǎn)贱呐，然后刪除后丧诺，再修復(fù)紅黑樹的性質(zhì)。

因此在刪除紅黑樹節(jié)點(diǎn)時奄薇，有三種情況

1. 刪除的是葉子節(jié)點(diǎn)
2. 刪除的是度為1的節(jié)點(diǎn)
3. 刪除的是度為2的節(jié)點(diǎn)

如果刪除的是葉子節(jié)點(diǎn)(如節(jié)點(diǎn)97)

站在紅黑樹的角度驳阎，直接刪除掉就好了，因此直接去掉父節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的線就好了

然后再更新鏈表的線馁蒂，最終結(jié)果為

由我們前面紅黑樹部分知識可以知道呵晚，在刪除紅黑樹節(jié)點(diǎn)時，只有被刪除的節(jié)點(diǎn)有左右子樹的時候沫屡，期望被刪除的節(jié)點(diǎn)才與實(shí)際被刪除的節(jié)點(diǎn)不符饵隙，因此最終被刪除的是當(dāng)前節(jié)點(diǎn)的前驅(qū)或者后繼。所以我們在刪除的時候沮脖，需要特別注意金矛。

因此在刪除以上節(jié)點(diǎn)（如31）時，需要注意更換node與前驅(qū)/后繼節(jié)點(diǎn)的鏈接位置勺届，在理解這句話之前驶俊，我們先來看看下面這種刪除的情況。

站在鏈表的角度免姿，刪除31之前饼酿，我們的遍歷順序?yàn)椋ú糠郑?2 -> 37 - > 21 -> 31 -> 41，刪除之后的遍歷順序應(yīng)該為（部分）52 -> 37 - > 21 -> 41

按照我們一般的邏輯來講养泡，我們直接將31刪除掉就好了嗜湃，因此從紅黑樹的角度講，刪除后最終的結(jié)果為

好了澜掩，此時我們再看看從鏈表角度的遍歷順序购披，發(fā)現(xiàn)變?yōu)榱?52 -> 21 -> 37 -> -> 41，遍歷順序與我們期望的不符肩榕，因此問題就產(chǎn)生了刚陡。因此我們需要注意更換node與前驅(qū)/后繼節(jié)點(diǎn)的鏈接位置，來保證刪除后的正確遍歷順序株汉。

因此筐乳，同樣的，假設(shè)有如下的一棵紅黑樹

刪除是節(jié)點(diǎn)31,31節(jié)點(diǎn)的后繼為37乔妈，我們在刪除之前蝙云，先調(diào)換兩個節(jié)點(diǎn)在鏈表中的位置，注意路召，不交換鏈表在紅黑樹種的位置勃刨，位置交換后的結(jié)果為

然后最終刪除后的結(jié)果為

通過這種方式波材，先交換位置后，再刪除的話身隐，就能順利的解決鏈表遍歷順序不符的問題

LinkedHashMap更換節(jié)點(diǎn)的鏈接位置

下圖是鏈表原始的順序

調(diào)換順序后的期望位置

因此我們可以通過將被刪除的節(jié)點(diǎn)與正在被刪除的節(jié)點(diǎn)通過以下的方式進(jìn)行位置的調(diào)換

//1.交換prev
LinkedNode<K,V> tmp = linkedWillNode.prev;
linkedWillNode.prev = linkedRemoveNode.prev;
linkedRemoveNode.prev = tmp;
if (linkedWillNode.prev == null) {
    first = linkedWillNode;
} else {
    linkedWillNode.prev.next = linkedWillNode;
}

if (linkedRemoveNode.prev == null) {
    first = linkedRemoveNode;
} else {
    linkedRemoveNode.prev.next = linkedRemoveNode;
}

//2.交換next
tmp = linkedWillNode.next;
linkedWillNode.next = linkedRemoveNode.next;
linkedRemoveNode.next = tmp;
if (linkedWillNode.next == null) {
    last = linkedWillNode;
} else  {
    linkedWillNode.next.prev = linkedWillNode;
}

if (linkedRemoveNode.next == null) {
    last = linkedRemoveNode;
} else  {
    linkedRemoveNode.next.prev = linkedRemoveNode;
}

通過以上方法廷区，就可以成功交換兩個鏈表中的位置

• 關(guān)于使用%來計算索引

在前面，我們使用&來計算元素的索引贾铝，可以提高計算性能隙轻，如果我們要使用%好計算索引的話，有以下的建議

建議把哈希表的長度設(shè)計為質(zhì)數(shù)垢揩，這樣可以減少哈希沖突玖绿，如下例所示

10 % 8 = 2      10 % 7 = 3
20 % 8 = 4      20 % 7 = 6
30 % 8 = 6      30 % 7 = 2
40 % 8 = 0      40 % 7 = 5
50 % 8 = 2      50 % 7 = 1
60 % 8 = 4      60 % 7 = 4
70 % 8 = 6      70 % 7 = 0

通過兩組數(shù)據(jù)，我們看到水孩，質(zhì)數(shù)的余數(shù)可以大大的減少哈希沖突镰矿。

下圖是科學(xué)家整理出來的不同數(shù)據(jù)規(guī)模對應(yīng)的最佳素數(shù)，在數(shù)據(jù)規(guī)模介于上界與下界之間時俘种，選擇對應(yīng)的素數(shù)秤标，哈希表的性能最優(yōu)，哈希沖突可以降低到最少宙刘。

以上素數(shù)還有以下兩個特點(diǎn)：

1. 每個素數(shù)略小于前一個素數(shù)的2倍
2. 每個素數(shù)盡可能接近2的冪（2^n）

GitHub地址

本節(jié)完苍姜！