JavaGuide知識(shí)點(diǎn)整理——集合常見知識(shí)點(diǎn)（下）

Map接口

HashMap和Hashtable的區(qū)別

  1. 線程是否安全：HashMap是非線程安全的，Hashtable是線程安全的，因?yàn)镠ashtable內(nèi)部的方法基本都經(jīng)過synchronized修飾(這是很老的一個(gè)實(shí)現(xiàn)，如果現(xiàn)在需要保證線程安全的話推薦使用ConcurrentHashMap)
  2. 效率：因?yàn)榫€程安全的問題，HashMap要比Hashtable的效率高一些，另外Hashtable基本被淘汰，不建議在代碼中使用。
  3. 對(duì)Null key和Null value的支持：HashMap可以存儲(chǔ)null的key和value。但是null作為鍵只能有一個(gè)。null作為值可以有多個(gè)。Hashtable不允許有null鍵和null值，否則會(huì)拋出空指針異常。
  4. 初始容量大小和每次擴(kuò)充容量大小不同：
    • 創(chuàng)建時(shí)如果不指定容量初始值，Hashtable默認(rèn)的初始大小為11，之后每次擴(kuò)容容量變?yōu)樵瓉淼?n+1.HashMap默認(rèn)初始化大小16.之后每次擴(kuò)容，容量都變?yōu)樵彽?倍。
    • 創(chuàng)建時(shí)如果給定了容量初始值，Hashtable會(huì)直接使用你給定的大小。而HashMap會(huì)將其擴(kuò)容為2的冪次方發(fā)小。也就是說HashMap永遠(yuǎn)使用2的冪次方作為哈希表的大小。
  5. 底層數(shù)據(jù)結(jié)構(gòu)：JDK1.8以后HashMap在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值(默認(rèn)8)(將鏈表轉(zhuǎn)化成紅黑樹前會(huì)判斷，如果當(dāng)前數(shù)組長(zhǎng)度小于64，那么會(huì)先進(jìn)性數(shù)組擴(kuò)容，而不是轉(zhuǎn)化成紅黑樹)時(shí)，會(huì)將鏈表轉(zhuǎn)化 成紅黑樹，以減少搜索時(shí)間，Hashtable沒有這樣的機(jī)制。

HashMap和HashSet的區(qū)別

HashSet的源碼中很清楚的寫的：HashSet的底層是基于HashMap實(shí)現(xiàn)的。HashSet的源碼非常少，因?yàn)槌薈lone(),writeObject(),readObject()等是HashSet自己不得不實(shí)現(xiàn)的以外，其他的方法都是直接調(diào)用HashMap中的方法.


HashMap和HashSet

HashMap和TreeMap的區(qū)別

TreeMap和HashMap都繼承自AbstractMap，但是需要注意的是TreeMap它還實(shí)現(xiàn)了NavigableMap接口和SortedMap接口。
實(shí)現(xiàn)了NavigableMap接口讓TreeMap有了對(duì)集合內(nèi)元素的搜索的能力。
實(shí)現(xiàn)SortedMap接口讓TreeMap有了對(duì)集合中的元素根據(jù)鍵排序的能力。默認(rèn)是按照key的升序排序，不過我們也可以指定排序的比較器。

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

這個(gè)代碼的執(zhí)行可以看出TreeMap已經(jīng)按年齡升序來排列了。當(dāng)然也可以用lambda來實(shí)現(xiàn)排序：

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

綜上，相比于HashMap，TreeMap主要是多了對(duì)集合中的元素根據(jù)鍵值排序的能力以及對(duì)集合內(nèi)元素的搜索的能力。

HashSet如何檢查重復(fù)

據(jù)說java8之前的版本：把對(duì)象加入HashSet的時(shí)候，會(huì)先計(jì)算對(duì)象的hashcode值來判斷對(duì)象加入的位置，同事也會(huì)與其他加入的對(duì)象的hashCode值比較，如果沒有相同的，HashSet會(huì)假設(shè)對(duì)象沒有重復(fù)出現(xiàn)，如果發(fā)現(xiàn)有hashCode值相同的對(duì)象，會(huì)調(diào)用equals()方法來檢查hashCode相等的對(duì)象是否真的相同。如果兩者相同說明有重復(fù)，不會(huì)加入成功。
而在JDK1.8中，HashSet的add方法只是簡(jiǎn)單的調(diào)用了一下HashMap的put方法，并且判斷了一下返回值以確保是否有重復(fù)元素。下面是源碼截圖：


HashSet的add方法

也就是說在1.8中，無論HashSet中是否已經(jīng)存在了某元素，HashSet都會(huì)直接插入。只是會(huì)在add方法的返回值處告訴我們插入前是否已經(jīng)存在相同的元素。

HashCode與equals的相關(guān)規(guī)定：

  1. 如果兩個(gè)對(duì)象相等，則hashCode一定也是相同的
  2. 如果兩個(gè)對(duì)象相等，equals判斷一定是true
  3. 兩個(gè)對(duì)象有相同的hashCode值，他們也不一定是相等的
  4. 綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋。
  5. hashCode默認(rèn)行為是對(duì)堆上的對(duì)象產(chǎn)生獨(dú)特值，如果沒有重寫hashCode，則該class的兩個(gè)對(duì)象無論如何都不會(huì)相等。

HashMap的底層實(shí)現(xiàn)

JDK1.8之前HashMap底層是數(shù)組和鏈表結(jié)合在一起使用，也就是鏈表散列。HashMap通過key的hashCode經(jīng)過擾動(dòng)函數(shù)處理后得到hash值，然后通過(n-1)&hash判斷當(dāng)前元素存放的位置(這里n是數(shù)組的長(zhǎng)度)。如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的hash值以及key是否相同，如果相同的話直接覆蓋，不相同就通過拉鏈法解決沖突。
所謂擾動(dòng)函數(shù)指的就是HashMap的hash方法，使用哈希方法也就是擾動(dòng)函數(shù)是為了防止一些實(shí)現(xiàn)比較差的hashCode方法，從而減少哈希碰撞。

所謂“拉鏈法”就是：將鏈表和數(shù)組相結(jié)合，也就是說創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一個(gè)格就是一個(gè)鏈表，若遇到哈希沖突，將沖突的值加到鏈表中即可。


拉鏈法

相比于之前的版本，jdk1.8之后在解決哈希沖突的時(shí)候有了較大的變化：當(dāng)鏈表長(zhǎng)度大于閾值(默認(rèn)是8.但是將鏈表轉(zhuǎn)化紅黑樹前會(huì)判斷當(dāng)前數(shù)組長(zhǎng)度，數(shù)組小于64的話會(huì)先數(shù)組擴(kuò)容，而不是轉(zhuǎn)化紅黑樹)時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間。


jdk1.8的數(shù)據(jù)結(jié)構(gòu)

TreeMap,TreeSet,以及1.8以后的HashMap底層都用到了紅黑樹，紅黑樹就是為了解決二叉查找樹的缺陷，因?yàn)槎娌檎覙淠承┣闆r下會(huì)退化成一個(gè)線性結(jié)構(gòu)。
下圖可以看做是一個(gè)簡(jiǎn)單的HashMap添加元素的步驟：


添加元素

HashMap的長(zhǎng)度為什么是2的冪次方

為了能讓HashMap存取高效，盡量減少碰撞，也就是盡量把數(shù)據(jù)分配均勻，我們上面也講到了Hash值的范圍-2147483648 到 2147483647，前后加起來40億的映射空間，只要哈希函數(shù)映射的比較均勻松散，一般應(yīng)該是很難出現(xiàn)碰撞的，但是問題是一個(gè)40億長(zhǎng)度的數(shù)組內(nèi)存是放不下的。所以這個(gè)散列值不能直接拿來用。用之前還要對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才能用來要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)。這個(gè)數(shù)組下標(biāo)的計(jì)算公式是(n-1)&hash。這也就解釋了為什么HashMap的長(zhǎng)度為什么是2的冪次方。

這里有一個(gè)公式：在length是2的n次方的時(shí)候：hash%length==hash&(length-1)
這個(gè)公式成立。
我們上面說的對(duì)數(shù)組長(zhǎng)度取模，之所以能演變成(n-1)&hash也是為了讓這個(gè)公式成立。因?yàn)檫@樣二進(jìn)制位操作比用%效率要高的多。

HashMap多線程操作死鎖問題

主要原因在于并發(fā)下的Rehash會(huì)造成元素之間形成一個(gè)循環(huán)鏈表。不過JDK1.8后解決了這個(gè)問題，但是還是不建議多線程的情況下使用HashMap，因?yàn)槎嗑€程下使用還會(huì)有其他問題，比如數(shù)據(jù)丟失等，并發(fā)環(huán)境建議使用ConcurrentHashMap.

HashMap有哪幾種常見的遍歷方式、

從大方向來說有四種：

  1. 迭代器方式遍歷(Iterator)
  2. For Each方式遍歷
  3. Lambda表達(dá)式遍歷
  4. streams API遍歷

但是美中類型又有不同的實(shí)現(xiàn)，所以一共有七中遍歷方式：

  • 使用迭代器（Iterator）EntrySet 的方式進(jìn)行遍歷；
  • 使用迭代器（Iterator）KeySet 的方式進(jìn)行遍歷；
  • 使用 For Each EntrySet 的方式進(jìn)行遍歷；
  • 使用 For Each KeySet 的方式進(jìn)行遍歷；
  • 使用 Lambda 表達(dá)式的方式進(jìn)行遍歷；
  • 使用 Streams API 單線程的方式進(jìn)行遍歷；
  • 使用 Streams API 多線程的方式進(jìn)行遍歷。

下面是簡(jiǎn)單是使用代碼：

    public static void main(String[] args) {
        Map<Integer,String> map = new HashMap<>();
        map.put(1,"f");
        map.put(2,"s");
        map.put(3,"t");


        // 第一種遍歷方式entrySet
        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            System.out.println(entry.getKey()+":"+entry.getValue());
        }

        //第二種遍歷方式keySet
        Iterator<Integer> iterator1 = map.keySet().iterator();
        while (iterator1.hasNext()) {
            Integer key = iterator1.next();
            System.out.println(key+":"+map.get(key));
        }

        // 第三種遍歷方式For Each EntrySet
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey()+":"+entry.getValue());
        }

        //第四種遍歷方式For Each keySet
        for (Integer key : map.keySet()) {
            System.out.println(key+":"+map.get(key));
        }

        // 第五種遍歷方式lambda
        map.forEach((key, value) -> {
            System.out.println(key+":"+value);
        });

        // 第六種遍歷方式Streams API 單線程
        map.entrySet().stream().forEach((entry) -> {
            System.out.println(entry.getKey()+":"+entry.getValue());
        });
        
        // 第七種遍歷方式Streams API 多線程
        map.entrySet().parallelStream().forEach((entry) -> {
            System.out.println(entry.getKey()+":"+entry.getValue());
        });

    }

ConcurrentHashMap和Hashtable的區(qū)別

二者的主要區(qū)別體現(xiàn)在實(shí)現(xiàn)線程安全的方式不同

  • 底層數(shù)據(jù)結(jié)構(gòu):jdk1.7的ConcurrentHashMap底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)，JDK1.8采用的數(shù)據(jù)結(jié)構(gòu)和HashMap一樣，數(shù)組+鏈表/紅黑樹.Hashtable1.8之前和HashMap的底層數(shù)據(jù)結(jié)構(gòu)類似都是數(shù)組+鏈表。
  • 實(shí)現(xiàn)線程安全的方式：在JDK1.7的時(shí)候，ConcurrentHashMap(分段鎖)對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段，每一把鎖只鎖容器中一部分?jǐn)?shù)據(jù)，多線程訪問容器中不同數(shù)據(jù)段的數(shù)據(jù)就不會(huì)存在競(jìng)爭(zhēng)。提高并發(fā)訪問率。到了JDK1.8已經(jīng)摒棄了分割分段的概念。直接用Node數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，并發(fā)控制使用synchronized和CAS來操作。整個(gè)看起來就像是優(yōu)化過且線程安全的HashMap。
    Hashtable(同一把鎖)使用synchronized來保證線程安全，效率非常低，當(dāng)一個(gè)線程訪問同步方法時(shí)，其他線程也訪問同步方法可能進(jìn)入阻塞或者輪詢狀態(tài)。如使用put添加元素，另一個(gè)線程不能使用put，而且也不能使用get，競(jìng)爭(zhēng)越激烈效率越低。

ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7

JDK1.7的時(shí)候?qū)?shù)據(jù)分為一段一段存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖。當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問


JDK1.7分段鎖

ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。
Segment繼承了ReentrantLock，所以Segment是一種可重入鎖，扮演鎖的角色，HashMap用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。
一個(gè)ConcurrentHashMap里包含一個(gè)Segment數(shù)組，Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)。一個(gè)Segment包含一個(gè)HashEntry數(shù)組，每個(gè)HashEntry是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè)Segment守護(hù)一個(gè)HashEntry數(shù)組里的元素，當(dāng)對(duì)HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須先獲取對(duì)應(yīng)的Segment的鎖。

JDK1.8

ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)和HashMap1.8的結(jié)構(gòu)類似。數(shù)組+鏈表/紅黑樹。java8在鏈表長(zhǎng)度超過一個(gè)閾值(8)時(shí)將鏈表轉(zhuǎn)化成紅黑樹。
synchronized只鎖定當(dāng)前鏈表或者紅黑樹的首節(jié)點(diǎn)。這樣只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)，效率大大的提升了。

Collections工具類

Collections工具類常用方法：

  1. 排序
  2. 查找替換操作
  3. 同步控制

排序操作

void reverse(List list)//反轉(zhuǎn)
void shuffle(List list)//隨機(jī)排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序邏輯
void swap(List list, int i , int j)//交換兩個(gè)索引位置的元素
void rotate(List list, int distance)//旋轉(zhuǎn)。當(dāng)distance為正數(shù)時(shí)，將list后distance個(gè)元素整體移到前面。當(dāng)distance為負(fù)數(shù)時(shí)，將 list的前distance個(gè)元素整體移到后面

查找，替換操作

int binarySearch(List list, Object key)//對(duì)List進(jìn)行二分查找，返回索引，注意List必須是有序的
int max(Collection coll)//根據(jù)元素的自然順序，返回最大的元素。 類比int min(Collection coll)
int max(Collection coll, Comparator c)//根據(jù)定制排序，返回最大元素，排序規(guī)則由Comparatator類控制。類比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//統(tǒng)計(jì)元素出現(xiàn)次數(shù)
int indexOfSubList(List list, List target)//統(tǒng)計(jì)target在list中第一次出現(xiàn)的索引，找不到則返回-1，類比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替換舊元素

同步控制

Collections提供了多個(gè)synchronizedXxx()方法，該方法可以將指定集合包裝成線程同步的集合，從而解決多線程并發(fā)訪問集合時(shí)的線程安全問題。
我們知道HsahSet,TreeSet，ArrayList,LinkedList,HashMap,TreeMap都是線程不安全的。Collections提供了多個(gè)靜態(tài)方法可以把他們包裝秤線程安全的集合。

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（線程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（線程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（線程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（線程安全的）set。

不過最好不用下面這些方法，因?yàn)樾史浅５?，需要線程安全的集合類型時(shí)最好用JUC包下的并發(fā)集合。

本篇筆記就整理到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注，也祝大家工作順順利利！

最后編輯于 ：
?著作權(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)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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

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