Java集合框架之Map詳解

Posted on by

1、Map的實現

  • HashMap
  • Hashtable
  • LinkedHashMap
  • TreeMap
  • ConcurrentHashMap

2、HashMap 和 Hashtable 的區別

  • HashMap：底層是基於數組+鏈表實現，非線程安全的，默認容量是16、允許有空的健和值
  • Hashtable：基於哈希表實現，線程安全的(加瞭synchronized鎖)，默認容量是11，不允許有空的健和值

3、介紹下對象的 hashCode()和equals()，使用場景

hashCode：

頂級類Object裡面的方法，所有的類都是繼承Object,返回是一個int類型的數

根據一定的hash規則(存儲地址，字段，長度等)，映射成一個數值，即散列值

@Override
public int hashCode() {
     return Objects.hash(age,name,time);
}

equals：

頂級類Object裡面的方法，所有的類都是繼承Object,返回是一個boolean類型

根據自定義的匹配規則，用於匹配兩個對象是否一樣，一般邏輯如下：

1、判斷地址是否一樣

2、非空判斷 和 Class類型判斷

3、強轉

4、對象裡面的字段一一匹配

@Override
public boolean equals(Object obj) {
    if (obj == this)
        return true;
    if (obj == null || getClass() != obj.getClass())
        return false;
    User user = (User) obj;
    return age == user.age && Objects.equals(name, user.name) && Objects.equals(time, user.time);
}

使用場景：對象比較、或者集合容器裡面排重、比較、排序

4、HashMap和TreeMap應該怎麼選擇，使用場景

hashMap:

  • 散列桶(數組+鏈表)，可以實現快速的存儲和檢索，但是確實包含無序的元素，適用於在map中插入刪除和定位元素

treeMap:

  • 使用存儲結構是一個平衡二叉樹->紅黑樹，可以自定義排序規則，要實現Comparator接口
  • 能便捷的實現內部元素的各種排序，但是一般性能比HashMap差，適用於安裝自然排序或者自定義排序規則 (寫過微信支付簽名工具類就用這個類)

5、Set和Map的關系 TODO

核心就是不保存重復的元素，存儲一組唯一的對象

set的每一種實現都是對應Map裡面的一種封裝，

HashSet對應的就是HashMap，treeSet對應的就是treeMap

  • set：無序，不允許存在重復的元素
  • list：有序，可以存在重復元素
  • set 和 list 對比： 都是Collection的子接口，Collection是集合類；
  • set 檢查元素效率低下，刪除和插入的效率高，插入和刪除不會引起元素的位置變化；
  • list 和數組類似，List可以動態增長，查找元素的效率較高，插入元素和刪除元素效率低，因為會引起其他元素位置發生變化
  • map： Map接口不是Collection接口的繼承，而是從自己的用於維護鍵值對關聯的接口層次結構入手，按定義，該接口描述瞭從不重復的鍵到值的映射

6、常見Map的排序規則是怎樣的？

按照添加順序使用LinkedHashMap，按照自然排序使用TreeMap，自定義排序 TreeMap(Comparetor c)

7、如果需要線程安全，且效率高的Map，應該怎麼做？

  • 多線程環境下可以用concurrent包下的ConcurrentHashMap,或者使用Collections.synchronizedMap(),
  • ConcurrentHashMap雖然是線程安全，但是他的效率比Hashtable要高很多使用
  • Collections.synchronizedMap包裝後返回的map是加鎖的

8、介紹下 HashMap

  • HashMap底層(數組+鏈表+紅黑樹 jdk8才有紅黑樹)，在JDK1.8中，鏈表的長度大於8，鏈表會轉換成紅黑樹
  • 數組中每一項是一個鏈表，即數組和鏈表的結合體
  • Node<K,V>[] table

是數組，數組的元素是Entry(Node繼承Entry)，Entry元素是一個key-value的鍵值對，它持有一個指向下個Entry的引用，table數組的每個Entry元素同時也作為當前Entry鏈表的首節點，也指向瞭該鏈表的下個Entry元素

數組的一個小格代表一個bucket

9、什麼是Hash碰撞？常見的解決辦法有哪些，hashmap采用哪種方法？

  • hash碰撞的意思是不同key計算得到的Hash值相同，需要放到同個bucket中
  • 常見的解決辦法：鏈表法、開發地址法、再哈希法等
  • HashMap采用的是鏈表法

10、HashMap底層是 數組+鏈表+紅黑樹，為什麼要用這幾類結構呢？

  • 數組：Node<K,V>[] table ，根據對象的key的hash值確定在數組裡面是哪個節點 – 鏈表：作用是解決hash沖突，將hash值一樣的對象存在一個鏈表放在hash值對應的槽位
  • 紅黑樹：JDK8使用紅黑樹來替代超過8個節點的鏈表，主要是查詢性能的提升，從原來的O(n)到O(logn),
  • 通過hash碰撞，讓HashMap不斷產生碰撞，那麼相同key的位置的鏈表就會不斷增長，
  • 當對這個Hashmap的相應位置進行查詢的時候，就會循環遍歷這個超級大的鏈表，性能就會下降，所以改用紅黑樹

11、為什麼選擇紅黑樹而不用其他樹，比如二叉查找樹，為什麼不一直開始就用紅黑樹，而是到8的長度後才變換

  • 二叉查找樹在特殊情況下也會變成一條線性結構，和原先的鏈表存在一樣的深度遍歷問題，查找性能就會慢，
  • 使用紅黑樹主要是提升查找數據的速度，紅黑樹是平衡二叉樹的一種，插入新數據後會通過左旋，右旋、變色等操作來保持平衡，解決單鏈表查詢深度的問題
  • 數據量少的時候操作數據，遍歷線性表比紅黑樹所消耗的資源少，且前期數據少平衡二叉樹保持平衡是需要消耗資源的，所以前期采用線性表，等到一定數之後變換到紅黑樹

12、瞭解ConcurrentHashMap嗎？為什麼性能比hashtable高，說下原理

  • ConcurrentHashMap是線程安全的Map,因為hashtable類基本上所有的方法都是采用synchronized進行線程安全控制，高並發情況下效率就降低
  • ConcurrentHashMap是采用瞭分段鎖的思想提高性能，鎖粒度更細化

13、jdk1.7和jdk1.8裡面ConcurrentHashMap實現的區別有沒瞭解

  • JDK8之前，ConcurrentHashMap使用鎖分段技術，將數據分成一段段存儲，每個數據段配置一把鎖，即segment類，這個類繼承ReentrantLock來保證線程安全 【技術點：Segment + HashEntry】
  • JKD8的版本取消Segment這個分段鎖數據結構，底層也是使用Node數組+鏈表+紅黑樹，從而實現對每一段數據就行加鎖，也減少瞭並發沖突的概率，CAS(讀)+Synchronized(寫)【技術點：Node + Cas + Synchronized】

總結

本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!   

推薦閱讀：