1、Map的實(shí)現(xiàn)

• HashMap
• Hashtable
• LinkedHashMap
• TreeMap
• ConcurrentHashMap

2、HashMap 和 Hashtable 的區(qū)別

• HashMap：底層是基于數(shù)組+鏈表實(shí)現(xiàn)，非線程安全的，默認(rèn)容量是16、允許有空的健和值
• Hashtable：基于哈希表實(shí)現(xiàn)，線程安全的(加了synchronized鎖)，默認(rèn)容量是11，不允許有空的健和值

3、介紹下對(duì)象的 hashCode()和equals()，使用場(chǎng)景

hashCode：

頂級(jí)類Object里面的方法，所有的類都是繼承Object,返回是一個(gè)int類型的數(shù)

根據(jù)一定的hash規(guī)則(存儲(chǔ)地址，字段，長(zhǎng)度等)，映射成一個(gè)數(shù)值，即散列值

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

equals：

頂級(jí)類Object里面的方法，所有的類都是繼承Object,返回是一個(gè)boolean類型

根據(jù)自定義的匹配規(guī)則，用于匹配兩個(gè)對(duì)象是否一樣，一般邏輯如下：

1、判斷地址是否一樣

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

3、強(qiáng)轉(zhuǎn)

4、對(duì)象里面的字段一一匹配

@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);
}

使用場(chǎng)景：對(duì)象比較、或者集合容器里面排重、比較、排序

4、HashMap和TreeMap應(yīng)該怎么選擇，使用場(chǎng)景

hashMap:

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

treeMap:

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

5、Set和Map的關(guān)系 TODO

核心就是不保存重復(fù)的元素，存儲(chǔ)一組唯一的對(duì)象

set的每一種實(shí)現(xiàn)都是對(duì)應(yīng)Map里面的一種封裝，

HashSet對(duì)應(yīng)的就是HashMap，treeSet對(duì)應(yīng)的就是treeMap

• set：無序，不允許存在重復(fù)的元素
• list：有序，可以存在重復(fù)元素
• set 和 list 對(duì)比： 都是Collection的子接口，Collection是集合類；
• set 檢查元素效率低下，刪除和插入的效率高，插入和刪除不會(huì)引起元素的位置變化；
• list 和數(shù)組類似，List可以動(dòng)態(tài)增長(zhǎng)，查找元素的效率較高，插入元素和刪除元素效率低，因?yàn)闀?huì)引起其他元素位置發(fā)生變化
• map： Map接口不是Collection接口的繼承，而是從自己的用于維護(hù)鍵值對(duì)關(guān)聯(lián)的接口層次結(jié)構(gòu)入手，按定義，該接口描述了從不重復(fù)的鍵到值的映射

6、常見Map的排序規(guī)則是怎樣的？

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

7、如果需要線程安全，且效率高的Map，應(yīng)該怎么做？

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

8、介紹下 HashMap

• HashMap底層(數(shù)組+鏈表+紅黑樹 jdk8才有紅黑樹)，在JDK1.8中，鏈表的長(zhǎng)度大于8，鏈表會(huì)轉(zhuǎn)換成紅黑樹
• 數(shù)組中每一項(xiàng)是一個(gè)鏈表，即數(shù)組和鏈表的結(jié)合體
• Node<K,V>[] table

是數(shù)組，數(shù)組的元素是Entry(Node繼承Entry)，Entry元素是一個(gè)key-value的鍵值對(duì)，它持有一個(gè)指向下個(gè)Entry的引用，table數(shù)組的每個(gè)Entry元素同時(shí)也作為當(dāng)前Entry鏈表的首節(jié)點(diǎn)，也指向了該鏈表的下個(gè)Entry元素

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

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

10、HashMap底層是 數(shù)組+鏈表+紅黑樹，為什么要用這幾類結(jié)構(gòu)呢？

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

11、為什么選擇紅黑樹而不用其他樹，比如二叉查找樹，為什么不一直開始就用紅黑樹，而是到8的長(zhǎng)度后才變換

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

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

• ConcurrentHashMap是線程安全的Map,因?yàn)閔ashtable類基本上所有的方法都是采用synchronized進(jìn)行線程安全控制，高并發(fā)情況下效率就降低
• ConcurrentHashMap是采用了分段鎖的思想提高性能，鎖粒度更細(xì)化

13、jdk1.7和jdk1.8里面ConcurrentHashMap實(shí)現(xiàn)的區(qū)別有沒了解

• JDK8之前，ConcurrentHashMap使用鎖分段技術(shù)，將數(shù)據(jù)分成一段段存儲(chǔ)，每個(gè)數(shù)據(jù)段配置一把鎖，即segment類，這個(gè)類繼承ReentrantLock來保證線程安全 【技術(shù)點(diǎn)：Segment + HashEntry】
• JKD8的版本取消Segment這個(gè)分段鎖數(shù)據(jù)結(jié)構(gòu)，底層也是使用Node數(shù)組+鏈表+紅黑樹，從而實(shí)現(xiàn)對(duì)每一段數(shù)據(jù)就行加鎖，也減少了并發(fā)沖突的概率，CAS(讀)+Synchronized(寫)【技術(shù)點(diǎn)：Node + Cas + Synchronized】

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!   

最新評(píng)論