【源码解析】关于List、Map、Set浅析

叁歲伎倆 2022-09-11 14:23 175阅读 0赞

# collection接口： #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

## ArrayList ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]

size为实时元素个数

**初始化的几种情况：**

1、指定容量，直接初始化  
2、指定容量为0，指向空数组“elementData”  
3、不指定容量，延迟初始化

**add**

进入先判断数组是否为空，为空情况下判断初始容量为DEFAULT\_CAPACITY = 10;还是minCapacity（size + 1）  
得到minCapacity  
再去确定准确的容量，如果需求的最小容量也比现在的数组长度（elementData.length）大，那么执行grow方法。  
grow方法通过int newCapacity = oldCapacity + (oldCapacity >> 1);给新数组大小赋值，Arrays.copyOf(原数组，新大小)，实质还是System.copyOf方法调用完成数组的迁移。

**get、set方法都比较简单**

remove方法就是验证完第idx个元素之后，使用System.copyOf(idx+1, idx, moved个元素移动)完成迁移，之后再置null让JVM对最后的元素进行GC操作。

**trimToSize方法**特别直白，就是修改到现在数组元素个数size的大小

## LinkedList ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 2]

其实就是Java的队列实现（底层是双向链表）

**add**  
操作主要是控制first＆last指针，完成链表的加减操作

**remove**  
就是找到对应的元素进行unlink操作。

E unlink(Node<E> x) {
        
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
    
        if (prev == null) {
        
            first = next;
        } else {
        
            prev.next = next;
            x.prev = null;
        }
    
        if (next == null) {
        
            last = prev;
        } else {
        
            next.prev = prev;
            x.next = null;
        }
    
        x.item = null;
        size--;
        modCount++;
        return element;
    }

**set和get方法**  
都没什么意思，主要就是根据下标靠左还是靠右来判断是从头遍历还是从尾遍历

//  node(index).item; 
    //  返回指定元素的item
     if (index < (size >> 1)) {
        
         Node<E> x = first;
         for (int i = 0; i < index; i++)
             x = x.next;
         return x;
     } else {
        
         Node<E> x = last;
         for (int i = size - 1; i > index; i--)
             x = x.prev;
         return x;
     }

### 区别： ###

一般来说都是ArrayList查询快，利用了内存连续的优点；LinkedList增删快，利用了拓展性好，指针比较灵活的优点。  
**几种极端情况：**  
1、如果增加元素⼀直是使⽤add() (增加到末尾)的话，那是ArrayList要快  
2、只remove末尾元素还是ArrayList快。  
3、删除中间元素也是ArrayList快，因为LinkedList前后怎么走都是O(N/2)的时间复杂度。

## CopyOnWriteArrayList ##

说到CopyOnWrite，就和COW有着扯不开的联系  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 3]

private transient volatile Object[] array;

**set操作：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**add操作也是同理：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
1、CopyOnWriteArrayList在使⽤迭代器遍历的时候，操作的是原来的数组  
2、只保证数据的最终⼀致性，不保证数据的实时⼀致性。（拿复制品出来遍历和修改）

## Set ##

### HashSet： ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 6]

好文，解释为什么需要设置Object ：  
https://blog.csdn.net/FU250/article/details/106415918

// Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();

套娃呢？

4个HashMap
    public HashSet() {
        
        map = new HashMap<>();
    }
    1个LinkedHashMap
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    public boolean isEmpty() {
        
        return map.isEmpty();
    }
    map.xx，你懂的

### TreeSet ###

只是可以自然排序的set，底层是TreeHashMap，同上……

### LinkedSet ###

底层是LinkedHashMap，同上……

### CopyOnWriteArraySet ###

public CopyOnWriteArraySet() {
        
        al = new CopyOnWriteArrayList<E>();
    }
    
    汇成一句话：所有方法几乎都是al.xx ，你懂的

### 区别 ###

1、Set集合的底层就是Map！就是Map！就是Map！（大部分）  
2、Set都不涉及线程同步的问题  
3、区别在于是否有序

# Map： #

## HashMap ##

关于哈希Map，可以先看看这篇文章：[https://blog.csdn.net/weixin\_43801418/article/details/120074520][https_blog.csdn.net_weixin_43801418_article_details_120074520]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 7]

**构造函数：**  
1、对initCapacity过小、过大的情况做Exception处理  
2、对loadFactor <0、非数字做做Exception处理  
其他都是套娃

**put方法**  
涉及到寻址算法和hash扰动（无符号右移16位参与寻址）

1、如果数组没有初始化，那么执行resize进行初始化，延迟加载  
2、桶位没有元素，那么在桶位上直接添加元素  
3、在这个桶的第一位，key和hash都相等，赋值给临时变量e  
4、链表或者红黑树两种情况  
5、属于树，调用树的putTreeVal方法接收某个节点为e  
6、属于链表，for循环寻找指定的节点  
7、里面还有一个binCount记录当前节点数，一旦超过阈值，那么指定treeifyBin方法对桶位进行树化  
8、赋值阶段：  
8、将找到的指定node进行覆盖或者验证oldVal  
9、最后检查size是否超过阈值，超过就进行resize操作

### resize： ###

1、初始化会调用  
2、当前元素大于阈值：capacity \* load factor时候也会调用扩容

**初始化的时候，**

int oldCap = (oldTab == null) ? 0 : oldTab.length;
    oldThr没碰的时候还是0

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
到最后就直接return table数组了，中间其实可以直接返回的。

**扩容情况：**  
1、设置newThr和newCap的值  
2、迁移操作

oldCap：
    	＞0：
    		1. 超过最大容量，不能执行扩容，返回oldTab
    		2. 未达到最大容量，newCap扩容为原来的两倍
    	
    	＜=0：
    		newCap = oldThr

迁移操作：

if (oldTab != null) {
        
    	// 对每个桶位都进行搬移操作
        for (int j = 0; j < oldCap; ++j) {
        
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
        
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                    
    			// 确认是RBT
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    
    			// 链表的高低位链搬移
                else {
         // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
        
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
        
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
        
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
        
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
        
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }

高低位使用的是hash的前一位为1或者0来表示在高位还是低位。

**get**

逻辑比较简单：  
![在这里插入图片描述][dc7212ef5b564b4f850e39bde8f4a237.png]  
公开的get方法，查看返回来的值是否找到指定的元素  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 9]

**remove方法：**  
1、找元素  
2、删除元素（本质是指针移动，删除让JVM来做）

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 11]

### **和hashtable区别：** ###

![在这里插入图片描述][bf373d89bddd4cdaa6361918758178b3.png]

## LinkedHashMap ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 12]

// 访问顺序
    final boolean accessOrder;
    //默认插入排序

**put方法：**  
自己没写，调用父类的直接用  
但是自己重写了newNode方法，体现了代码的复用性

### get方法： ###

这个方法比较有意思  
虽然涉及到LRU算法，但是会将最常用的节点放到最后，不知道这是不是在恶作剧了

void afterNodeAccess(Node<K,V> e) {
         // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
        
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
        
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

**remove**

也是偷HashMap的方法，但是自己重写了!\[

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 13]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 14]

## TreeMap ##

实质是对红黑树实现，利用了搜索二叉树有序的特点。  
对Comparable接口的使用比较多（这就是自然排序）

## ConcurrentHashMap ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 15]

**特点：**  
1、get非阻塞，但是得到的值不准确  
2、还是散列表+红黑树  
3、ConcurrentHashMap的key和Value都不能为null

为什么有了Hashtable还需要ConcurrentHashMap？  
1、Hashtable落后；每个方法上都加上了重量级锁synchronized修饰  
2、ConcurrentHashMap锁的粒度更小，而且很多使用CAS自旋锁算法实现同步，并发下性能比Ｈａｓｈｔａｂｌｅ强很多

**构造方法：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 17]

**get方法**

eh < 0 :
    	（1）eh = -1 为FWD节点
    	（2）eh = -2 为TreeBin节点

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 18]

### put方法 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 19]  
截图截不下了，直接代码分析吧

synchronized (f) {
        
    	// 双重验证
        if (tabAt(tab, i) == f) {
        
        	// 1. 链表
            if (fh >= 0) {
        
                binCount = 1;
                for (Node<K,V> e = f;; ++binCount) {
        
                    K ek;
                    // hash和key都对应上了，替换操作
                    if (e.hash == hash && ((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
        
                        oldVal = e.val;
                        if (!onlyIfAbsent)
                            e.val = value;
                        break;
                    }
                    Node<K,V> pred = e;
                    // == null实在没找到，new Node
                    if ((e = e.next) == null) {
        
                        pred.next = new Node<K,V>(hash, key,value, null);
                        break;
                    }
                }
            }
    		
    		// 2. 红黑树（TreeBin结点）
            else if (f instanceof TreeBin) {
        
                Node<K,V> p;
                binCount = 2;
                // p为找到的结点
                if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
        
                    oldVal = p.val;
                    if (!onlyIfAbsent)
                        p.val = value;
                }
            }
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 20]

## 为什么不用旧的容器实现多线程？ ##

线程安全的容器 && 比较粗糙：  
**Hashtable**  
**Vector：** ⼏乎在每个⽅法都加了synchronized重量级锁  
Collections.synchronizedList(new ArrayList())：在方法内部加，在里面等，这不还是要等啊

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 21]

线程安全的容器，优点是什么，有什么优化？  
**ConcurrentHashMap  
CopyOnWriteArrayList**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a764e1ee3fd948ce98127eaefa14c7d0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/3d19b7968a4840e1b84e265c5f309ae4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ab99a9766d964647aafdbbaa1d4f19ac.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/463f716e7d454a59b64f6e219972d9c8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/d1e468dc22f348608870d2f86e768f29.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/31960df53f6f41628a30134c290d1163.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/a30f370e39f9486f955dec2961da06de.png
[https_blog.csdn.net_weixin_43801418_article_details_120074520]: https://blog.csdn.net/weixin_43801418/article/details/120074520
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/49969cd821684ed097fb3cef558fe53b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/7da2298a2ede47a89b86302d0aaf6910.png
[dc7212ef5b564b4f850e39bde8f4a237.png]: /images/20220828/0df16f74b0454cec83b7a625714f8f5c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/2d384b1f12d040f49bb779448fac2bc4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/7824cf7c525f4453975ade1a4dd0c568.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/bcac35237b0f4544ab8cd1121c61d0c2.png
[bf373d89bddd4cdaa6361918758178b3.png]: /images/20220828/6a0fd7e0c446441b97acd4b8da04c0ae.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/dbbf36cd4f424af4871d4d6375170dbc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/28c49cc36a954dedb2f62412a7a22674.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/aa4476b4d42f41eeba51a04dd1d916d0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/f167fec7096b461197bfea53e1398ce8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 16]: /images/20220828/b2dd3e124a8b4feaa2ea2945bdb7b408.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 17]: /images/20220828/3239d26cb45a4e57a4fe6a21f464cabf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 18]: /images/20220828/a50d123998564d55b08cca34e3b86421.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 19]: /images/20220828/a2633491b1f94b8097704463c7e80506.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 20]: /images/20220828/e2cdcf0dab7a44e594fd1f725cf038d6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 21]: /images/20220828/aeb8a148d69a45aab071c1604a715ca7.png