我從未見(jiàn)過(guò)如此精辟的解說(shuō)方式，雙列集合框架 Map，看一遍就夠了

1.常用的實(shí)現(xiàn)類(lèi)結(jié)構(gòu)

一、HashMap

實(shí)現(xiàn)了Map、Cloneable、Serializable接口，繼承了AbstractMap類(lèi)

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable    
    /**
     * Map接口: 實(shí)現(xiàn)鍵值對(duì),Map接口規(guī)定了一個(gè)key對(duì)應(yīng)一個(gè)value
     *          HashMap使用該接口用來(lái)替換Dictionary類(lèi)
     *
     * AbstractMap類(lèi): 繼承Map的抽象類(lèi),減少M(fèi)ap操作的實(shí)現(xiàn)
     *
     * Cloneable接口: 可以顯示的調(diào)用Object.clone()方法,合法的對(duì)該類(lèi)
     *                實(shí)例進(jìn)行字段復(fù)制
     *
     * Serializable接口: 實(shí)現(xiàn)該接口后,該類(lèi)可以被序列化和反序列化
     */

1.HashMap是否線程安全？

HashMap是線程不安全的，在并發(fā)的環(huán)境下可以使用ConcurrentHashMap。

2.HashMap的內(nèi)部實(shí)現(xiàn)

內(nèi)部實(shí)現(xiàn)：在JDK1.8之前是數(shù)組+鏈表，JDK1.8之后是數(shù)組+鏈表+紅黑樹(shù)
加入紅黑樹(shù)的原因:JDK1.8之前HashMap使用的是數(shù)組加鏈表，由于哈希函數(shù)不能百分百的讓元素均勻的分布，就會(huì)造成有大量的元素存入同一個(gè)index（桶）下，這樣index就形成了一條很長(zhǎng)的鏈表，由此元素的遍歷的時(shí)間復(fù)雜度為O(n),失去了HashMap的優(yōu)勢(shì)，加入了紅黑樹(shù)，查找的時(shí)間復(fù)雜度為O(log n),實(shí)現(xiàn)了優(yōu)化
數(shù)組的特點(diǎn)：查找快，時(shí)間復(fù)雜度是O(1),增刪慢，時(shí)間復(fù)雜度是O(n)
鏈表的特點(diǎn)：查找慢，時(shí)間復(fù)雜度是O(n),增刪快，時(shí)間復(fù)雜度是O(1)
紅黑樹(shù)的特點(diǎn)：在遍歷鏈表的基礎(chǔ)上，紅黑樹(shù)查找的時(shí)間復(fù)雜度是O(log n)
紅黑樹(shù)的查詢效率遠(yuǎn)大于鏈表，但是插入/刪除要比鏈表慢

3.HashMap的主要參數(shù)

1.默認(rèn)初始容量：16，必須是2的整數(shù)次方

2.默認(rèn)加載因子：0.75

3.閾值：容量*加載因子

4.樹(shù)形閾值：默認(rèn)是8，當(dāng)bucket中的鏈表長(zhǎng)度大于8時(shí)，則進(jìn)行鏈表樹(shù)化

5.非樹(shù)形閾值：默認(rèn)是6，當(dāng)進(jìn)行擴(kuò)容時(shí)，當(dāng)進(jìn)行擴(kuò)容（resize（））時(shí)（這時(shí)候的HashMap的數(shù)據(jù)存儲(chǔ)位置會(huì)重新計(jì)算），在計(jì)算完后，原有的紅黑樹(shù)內(nèi)的數(shù)量<6時(shí)，則由紅黑樹(shù)轉(zhuǎn)換為鏈表

6.樹(shù)形最小容量：桶可能是樹(shù)的哈希表的最小容量，至少是TREEIFY_THRESHOLD 的 4 倍，這樣能避免擴(kuò)容時(shí)的沖突

//鏈表轉(zhuǎn)紅黑樹(shù)的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹(shù)轉(zhuǎn)鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
/**
*最小樹(shù)形化容量閾值：即 當(dāng)哈希表中的容量 > 該值時(shí)，才允許樹(shù)形化鏈表 （即 將鏈表 轉(zhuǎn)換成紅黑樹(shù)）
*否則，若桶內(nèi)元素太多時(shí)，則直接擴(kuò)容，而不是樹(shù)形化
*為了避免進(jìn)行擴(kuò)容、樹(shù)形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
**/
static final int MIN_TREEIFY_CAPACITY = 64;

只有在數(shù)組的長(zhǎng)度大于64時(shí)，且鏈表的長(zhǎng)度>8時(shí)，才能樹(shù)形化鏈表
鏈表的長(zhǎng)度大于8時(shí)會(huì)調(diào)用treeifyBin方法轉(zhuǎn)換為紅黑樹(shù)，但是treeifyBin方法內(nèi)部有一個(gè)判斷，當(dāng)只有數(shù)組的長(zhǎng)度>64的時(shí)候，才能將鏈表樹(shù)形化，否則只進(jìn)行resize擴(kuò)容
因?yàn)殒湵磉^(guò)長(zhǎng)而數(shù)組過(guò)短，會(huì)經(jīng)常發(fā)生hash碰撞，這時(shí)進(jìn)行樹(shù)形化的作用不大，因?yàn)殒湵磉^(guò)長(zhǎng)的原因就是數(shù)組過(guò)短。樹(shù)形化之前要檢查數(shù)組的長(zhǎng)度，<64進(jìn)行擴(kuò)容，而不是進(jìn)行樹(shù)形化
鏈表的長(zhǎng)度>8，但數(shù)組的長(zhǎng)度<64時(shí),不會(huì)進(jìn)行樹(shù)形化，而是進(jìn)行resize后rehash重新排序

4.HashMap的常用方法

添加：V put(K key,V value) -->添加元素（也可以實(shí)現(xiàn)修改）

刪除：void clear() -->清空所有鍵值對(duì)元素

? V remove(Object key) -->根據(jù)鍵刪除對(duì)應(yīng)的值，并把值返回

判斷：containsKey(Object key) -->是否包含指定的鍵

? containsValue(Object value)–>是否包含指定的值

遍歷：Set<Map.Entry<K,V>> entrySet()–>獲取鍵值對(duì)

? V get(Object key) -->根據(jù)鍵獲取值

? Collection value()–>獲取值的集合

獲?。篠et setKey()–>獲取鍵的集合

? int size()–>獲取集合元素的個(gè)數(shù)

基本方法的使用

HashMap<Integer,String> map=new HashMap<>();
        //添加元素
        map.put(1, "a");
        map.put(2, "b");
        map.put(3, "c");
        //鍵不可重復(fù)，值被覆蓋
        map.put(3, "C");
        
        //通過(guò)鍵刪除整個(gè)鍵值對(duì)
        map.remove(3);
        //清空
        map.clear();
        //是否為空
        System.out.println(map.isEmpty());//false
        //是否包含4
        System.out.println(map.containsKey(4));//false
        //是否包含“b”值
        System.out.println(map.containsValue("b"));//true
        //獲取集合元素個(gè)數(shù)
        System.out.println(map.size());//3
        //通過(guò)鍵獲取值
        System.out.println(map.get(3));//C
        //獲取所有值構(gòu)成的集合
        Collection<String> values=map.values();
        for(String v:values){
            System.out.println("值:"+v);//值：a    值：b   值：c
        }
        
        System.out.println(map);
    }

兩種遍歷方式

public static void main(String[] args) {
    Map<String,Integer> map=new HashMap<>();
    map.put("小林",21);
    map.put("小張",35);
    map.put("小王",18);
    demo1(map);
    demo2(map);
  }
  //通過(guò)Set<K>  setKey()方法遍歷
  private static void demo1(Map<String,Integer> map) {
    Set<String> keys=map.keySet();
    for (String key:keys){
      Integer value=map.get(key);
      System.out.println("鍵為："+key+"值為："+value);//鍵為：小林值為：21
                                                      //鍵為：小王值為：18
                                                      //鍵為：小張值為：35
    }
  }
  //通過(guò)Set<Map.Entry<K,V>> entrySet()方法遍歷
  private static void demo2(Map<String, Integer> map) {
    Set<Map.Entry<String,Integer>> kvs=map.entrySet();
    for (Map.Entry<String,Integer> kv:kvs){
      String kstring=kv.getKey();
      Integer istring=kv.getValue();
      System.out.println(kstring+"-----"+istring);
      //小林-----21
      //小王-----18
      //小張-----35
    }
  }

5.關(guān)于hash沖突問(wèn)題

1.原因：

? 當(dāng)對(duì)某個(gè)元素進(jìn)行哈希運(yùn)算后，得到一個(gè)存儲(chǔ)地址，在進(jìn)行插入的時(shí)候，發(fā)現(xiàn)已經(jīng)被其他元素占用了。這就是所謂的哈希沖突，也叫哈希碰撞。

哈希函數(shù)的設(shè)計(jì)至關(guān)重要，好的哈希函數(shù)會(huì)盡量的確保計(jì)算簡(jiǎn)單和散列地址分布均勻，但是，數(shù)組是一塊連續(xù)的固定的長(zhǎng)度的內(nèi)存空間，再好的哈希函數(shù)也不能保證得到的存儲(chǔ)地址絕對(duì)不發(fā)生沖突。
2.解決hash沖突的方法：

開(kāi)放地址法：發(fā)生沖突，繼續(xù)尋找下一塊未被占用的存儲(chǔ)地址。
再散列函數(shù)法：當(dāng)發(fā)生沖突，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無(wú)沖突。
鏈地址法：將所有關(guān)鍵字的同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，我們稱(chēng)這種表為同義詞子表。
HashMap采用的是鏈地址法，也就是數(shù)組+鏈表的方式

HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數(shù)組位置不含鏈表（當(dāng)前的entry的next指向null），那么對(duì)于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表，對(duì)于添加操作，其時(shí)間復(fù)雜度為O(n),首先遍歷鏈表，存在即覆蓋，否則新增，然后通過(guò)key對(duì)象的equals方法逐一比對(duì)查找。所以！對(duì)于性能考慮，HashMap中的鏈表出現(xiàn)越少，性能才會(huì)越好。

6.JDK1.8之前HashMap存在死循環(huán)的問(wèn)題

原因：由于數(shù)組擴(kuò)容后，同一索引位置的節(jié)點(diǎn)順序會(huì)反掉

7.HashMap和Hashtable的區(qū)別


8.重寫(xiě)equals()方法后，是否一定要重寫(xiě)hashCode()方法？為什么？

重寫(xiě)equals()方法，需要重寫(xiě)hashCode()方法。

hashCode規(guī)定：兩個(gè)對(duì)象相等（即equals()返回true），hashCode一定相同；兩個(gè)對(duì)象hashCode相同，兩個(gè)對(duì)象不一定相等；

重寫(xiě)equals，而不重寫(xiě)hashCode方法，默認(rèn)調(diào)用的是Object類(lèi)的hashCode()方法，會(huì)導(dǎo)致兩個(gè)對(duì)象的equals相同但hashCode不同。簡(jiǎn)單的來(lái)說(shuō)，重寫(xiě)equals方法后，重寫(xiě)hashCode方法就是為了確保比較的兩個(gè)對(duì)象是同一對(duì)象。

二、LinkedHashMap

LinkedHashMap的底層結(jié)構(gòu)和HashMap是相同的，因?yàn)長(zhǎng)inkedHashMap繼承了HashMap，

區(qū)別在于：LinkedHashMap內(nèi)部提供了Entry，替換了HashMap中的Node。

LinkedHashMap：保證在遍歷map元素時(shí)，可以照添加的順序?qū)崿F(xiàn)遍歷

原因：在原來(lái)的HashMap底層結(jié)構(gòu)的基礎(chǔ)上，增加了一對(duì)指針，指向前一個(gè)和后一個(gè)元素

對(duì)于頻繁的遍歷操作，LinkedHashMap的效率要高于HashMap

三、TreeMap

保證照key-value對(duì)進(jìn)行排序，實(shí)現(xiàn)排序遍歷，此時(shí)考慮key的自然排序或者定制排序，底層使用的是紅黑樹(shù)

元素根據(jù)鍵排序，元素具有唯一性

1）自然排序

讓元素所在的類(lèi)繼承自然排序Comparable

2）比較器排序

讓集合的構(gòu)造方法接收一個(gè)比較器接口（Comparator的實(shí)現(xiàn)對(duì)象）

四、Hashtable

作為古老的實(shí)現(xiàn)類(lèi)；線程安全的，效率低；不能存儲(chǔ)null的key和value

最后

感謝你看到這里，看完有什么的不懂的可以在評(píng)論區(qū)問(wèn)我，覺(jué)得文章對(duì)你有幫助的話記得給我點(diǎn)個(gè)贊，每天都會(huì)分享java相關(guān)技術(shù)文章或行業(yè)資訊，歡迎大家關(guān)注和轉(zhuǎn)發(fā)文章！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容