java基本集合源码解读-JDK8/11

文章目录

前言详尽的debugger底层查看源码配置一.集合体系图二.List类集合

2.1.1 ArrayList2.1.2ArrayList底层源码分析

结论:2.1.3 使用ArrayList无参构造2.1.4**`无参构造下ArrayList.add()扩容机制`**2.1.5ArrayList有参构造 2.2.1vector

结论2.2.2以添加方式为例2.2.3vector的扩容机制无参构造 2.3.1 linkedList结论

2.3.2以添加方法为例2.3.3删除例子 2.4 List集合选择 三.set集合

3.1 HashSet

结论3.1.1 HashSet无参构造增添元素3.1.2 扩容机制和转成红黑树机制 3.2 linkedHashSet3.3 TreeSet

3.3.1 无参构造 增添元素 四.Map类集合

4.1 HashMap

4.1.1无参构造 put方法源码4.2 Hashtable

4.2.1 Hashtable扩容机制 4.3 Properties4.4 TreeMap 五.Collections工具类

---

前言

本文章主要针对源码解读.扩展内容很少.

详尽的debugger底层查看源码配置

一.集合体系图

增强for循环的底层也是迭代器,因此只要实现了Collection接口的都可以使用

二.List类集合 2.1.1 ArrayList

ArrayList可以加入多个null,可以放任何值ArrayList是由数组实现数据存储的ArrayList基本等同于Vector,除了ArrayList线程不安全,执行效率高.(在多线程的情况下不建议用ArrayList)

// ArrayList线程不安全,可以看源码没有synchronized
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

2.1.2ArrayList底层源码分析 结论:

1. ArrayList 中维护了一个Object类型的数组 transient Object[] elementData;

2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍.
3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

2.1.3 使用ArrayList无参构造

ArrayList无参构造器为我们创造了一个空的elementData数组

2.1.4**无参构造下ArrayList.add()扩容机制**

可能有人会对add中size的参数产生疑惑.现做以下解答:

	全局变量
char	‘/u0000’
byte	0
short	0
int	0
long	0L
float	0.0L
double	0.0d
boolean	false
引用类型复杂类型	null

add方法中的grow调用了扩容方法.
modCount++,记录当前集合被修改的次数.防止多线程同时修改.

    
     //minCapacity 传入1
    private Object[] grow(int minCapacity) {
    	// 将旧数据复制到新扩容的数组,保护原数据还在
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
    	// 无参构造size为类变量,初始值为0;因此这里参数为1
        return grow(size + 1);
    }
    
    
     
     // minCapacity为1
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        // 保存当前数组长度
        int oldCapacity = elementData.length;
        // 新长度 = 旧长度 + 旧长度/2. 即为原长度的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 当是空数组,即无参第一次添加元素执行
        if (newCapacity - minCapacity <= 0) {
        	// 当数组长度为0
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            	//获得二者较大值,DEFAULT_CAPACITY默认为10. 
            	// 这里比较的原因:当是有参构造就可以初始化min，同样可以符合条件进入比较。这时如果初始化的数值大于10就取min
                return Math.max(DEFAULT_CAPACITY, minCapacity);
                // 越界错误
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        // 判断新开辟的数组容量是否超过虚拟机设定内存的最大限度
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

2.1.5ArrayList有参构造

ArrayList有参构造扩容机制和无参类似.只是初始化容量给多少就是多少.

2.2.1vector 结论

Vector的底层也是一个对象数组,protected Object[] elementData;Vector是线程安全的如果是无参，默认10满后，就按2倍扩容;如果指定大小，则每次直接按2倍扩容 2.2.2以添加方式为例

2.2.3vector的扩容机制 无参构造

vector底层类似于Arraylist,仅多了同步锁和初始默认10不做具体解释,请看源码
默认构造容量为10的数组

2.3.1 linkedList 结论

linkedList底层实现了双向链表和双端队列特点可以添加任意元素(元素可以重复),包括null线程不安全linkedList底层维护了一个双向链表linkedList中维护了两个属性first和last分别指向首节点和尾节点每个节点(Node对象)，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表.所以linkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。 2.3.2以添加方法为例

last维护整个链表的尾节点,first维护整个链表的头节点.Node的三个参数.代表单个节点的前驱,元素,后继.

2.3.3删除例子

默认删除第一个元素

    
    private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        final E element = f.item;
        // 这里的赋值和c指针不同! next和f.next均指向同一块内存地址.并非next指向f.next
        final Node next = f.next;
        // 删除首部节点元素
        f.item = null;
        // 将首部节点的后继置null
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
        // 将 next的前驱置null;使首部节点未被引用被gc回收
            next.prev = null;
        size--;
        // 记录当前修改次数
        modCount++;
        return element;
    }

2.4 List集合选择

集合	底层结构	增删效率	改查效率
ArrayList	可变数组	较低,数组扩容	快,索引定位
linkedList	双向链表	较高.通过链表追加	慢

三.set集合

元素无序(但按照一定算法规则输出,取出的顺序是固定的),没有索引不允许重复添加同一个元素,只能包含一个null子类有HashSet和TreeSet 3.1 HashSet 结论

HashSet的底层是HashMap (HashMap的底层是数组+链表结构+红黑树)HashSet不保证元素是有序的,取决于hash后，再确定索引的结果.可以存放null,但只能是一个不能有重复的元素或值(相同的值经过hash算法得到的索引位置的值equalsequals依据程序员标准比较.相同放弃添加,不相同,在该位置生成链表追加)

1. HashSet底层是HashMap,第一次添加时,table数组扩容到16，临界值(threshold)是16*加载因子(loadFactor)是0.75 =12

2. 如果table数组使用到了临界值12,就会扩容到16*2 = 32,新的临界值就是32*0.75 = 24,依次类推

3. 在Java8/11中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)，否则仍然采用数组扩容机制

4.只要添加了元素,size++.也就是说总元素到达阈值就会触发扩容或树化

5. 若链表元素到了8个,而table表的大小不到64,那么table表会按照2倍扩容

3.1.1 HashSet无参构造增添元素

1.HashsSet底层就是HashMap

2.执行add方法添加"java"值

putVal

    
     //  return putVal(hash(key), key, value, false, true);
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // 定义的辅助变量
        Node[] tab; Node p; int n, i;
        // talbe 是hashMap的一个放Node节点的数组
        // if 表示如果当前table是null,或大小等于0,就是第一次扩容到16个
        if ((tab = table) == null || (n = tab.length) == 0)
        	// 下面细讲resize方法,这里是重新计算并开辟表的空间.无参构造第一次初始化为16
            n = (tab = resize()).length;
        // 根据传入key的hash值去计算该key应该放到table表的哪个索引位置
        //(& 按位与操作,一定比最小的还要小!控制了不会越界) 
        // 并把这个索引对应的对象赋给p 
        // 判断这个p是否为null
        	// 如果为null,就创建一个节点Node(key="java",value=PRESENT)
        if ((p = tab[i = (n - 1) & hash]) == null)
        // value是被共享的PRESENT对象
            tab[i] = newNode(hash, key, value, null);
        else {
        	// 开发技巧提示: 定义辅助变量时,在需要局部变量(辅助变量)的时候再创建
            Node e; K k;
            // 如果当前索引位置对应链表的的第一个元素和准备添加的key的hash值一样
            //满足两个条件之一:如果p指向Node的key元素和准备加入的元素是同一个对象  或者 键不为空,内容相同(equals可能被重写) 就不能加入
            if (p.hash == hash && 
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                // 判断p是不是一颗红黑树
                // 如果是一颗红黑树就调用putTreeval方法,下面详解putTreeval红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
                // 启用索引位置处链表循环比较
            else {
            	// 依次和该链表每一个元素比较
                for (int binCount = 0; ; ++binCount) {
            		// 到最后都不相同,则加入到链表的最后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 添加后,立即判断该节点是否到达8个节点
                        // 对当前链表,进行树化(红黑树)
                        // 注意,在转成红黑树时,还得进行判断表的容量必须大于64.否则先扩容表容量
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 在比较的过程中,如果有相同的直接break
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 统计修改次数
        ++modCount;
        // 检查大小是否是原表的3/4.第一次就是12.超过就扩容
        if (++size > threshold)
            resize();
         // hashmap交给子类如linkedHashMap使用
        afterNodeInsertion(evict);
        // 返回null代表成功
        return null;
    }

3.1.2 扩容机制和转成红黑树机制

1. HashSet底层是HashMap,第一次添加时,table数组扩容到16，临界值(threshold)是16*加载因子(loadFactor)是0.75 =12

2. 如果table数组使用到了临界值12,就会扩容到16*2 = 32,新的临界值就是32*0.75 = 24,依次类推

3. 在Java8/11中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)，否则仍然采用数组扩容机制

4.只要添加了元素,size++.也就是说总元素到达阈值就会触发扩容或树化

模拟代码

import java.util.HashSet;


public class HashSetStructure {

    public static void main(String[] args) {
        HashSet