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

一、HashMap

實現(xiàn)了Map、Cloneable、Serializable接口，繼承了AbstractMap類

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

1.HashMap是否線程安全？

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

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

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

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

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

2.默認加載因子：0.75

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

4.樹形閾值：默認是8，當bucket中的鏈表長度大于8時，則進行鏈表樹化

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

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

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

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

4.HashMap的常用方法

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

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

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

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

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

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

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

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

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

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

基本方法的使用

HashMap<Integer,String> map=new HashMap<>();
        //添加元素
        map.put(1, "a");
        map.put(2, "b");
        map.put(3, "c");
        //鍵不可重復，值被覆蓋
        map.put(3, "C");
        
        //通過鍵刪除整個鍵值對
        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
        //獲取集合元素個數(shù)
        System.out.println(map.size());//3
        //通過鍵獲取值
        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);
  }
  //通過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
    }
  }
  //通過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沖突問題

1.原因：

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

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

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

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

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

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

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

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

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

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

重寫equals，而不重寫hashCode方法，默認調(diào)用的是Object類的hashCode()方法，會導致兩個對象的equals相同但hashCode不同。簡單的來說，重寫equals方法后，重寫hashCode方法就是為了確保比較的兩個對象是同一對象。

二、LinkedHashMap

LinkedHashMap的底層結(jié)構(gòu)和HashMap是相同的，因為LinkedHashMap繼承了HashMap，

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

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

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

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

三、TreeMap

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

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

1）自然排序

讓元素所在的類繼承自然排序Comparable

2）比較器排序

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

四、Hashtable

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

最后

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