使用的JDK11版本
全文较长,建议选择性查看
图文较少,注释较多,建议在电脑上打开idea配套查看
写的比较详细,可以针对某一点(例如HashSet的Add方法)来查看.

Collection接口结构图

1.png

List接口

3.png
我们可以看到常用的List接口实现类有这三种
可以用一张表来描述它们之间的差异

实现类型底层数据结构线程安全性执行效率扩容规则
ArrayList数组不安全查找快增删慢首次默认10,后序1.5倍
LinkedList双向链表不安全查找慢增删快双向链表无需扩容
Vector数组安全比ArrayList效率低构造方法指定10元素,后序2倍扩容

ArrayList

一些属性

//数组大小默认值
private static final int DEFAULT_CAPACITY = 10;

//空Object数组
private static final Object[] EMPTY_ELEMENTDATA = {};

//空Object数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList底层存储数据的数组
transient Object[] elementData;

//数组内元素的个数
private int size;

构造方法


//无参构造方法,创建的时候把空数组赋值给elementData 
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//带参数(大小)的构造函数
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) { //构造一个固定长度的底层数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {   //没人会传入一个0吧。。。。
            this.elementData = EMPTY_ELEMENTDATA;
        } else {	//不能传入负数
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//带参数(集合)的构造函数
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();  //把构造函数中的集合赋值给当前List的数组
        if ((size = elementData.length) != 0) { 
            if (elementData.getClass() != Object[].class)
		//把传入的数组copy到当前的底层数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
	    //如果传入的集合是空的,还是赋值一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add方法-扩容机制

1.
public boolean add(E e) {
	//当前这个集合修改的次数;目前没看出来作用
        modCount++;
        add(e, elementData, size);
        return true;
    }
2.
private void add(E e, Object[] elementData, int s) {
	//这个条件成立的时间是 第一次add 或者 当前的容量已经满了 不足以再add元素了
        if (s == elementData.length)
	    //扩容方法	
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
   }
3.
private Object[] grow() {
        //传入的参数是最小需要空间的个数,也就是说我要再放一个,你最低得给我再加一个位置
        return grow(size + 1);
    }
4.
private Object[] grow(int minCapacity) {
	//把当前的数组copy到一个新的数组中,容量在newCapacity方法内
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
5.
private int newCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
	//在这里计算要扩容的数量
	//old右移一位就相当于/2 右移两位就相当于 /2/2 左移相反是*2
	//相当于扩大了1.5倍,当然第一次进来的话 old是0 0位移还是0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
	//这个条件只有第一次Add的时候满足 可能还有其它情况 我还没想出来...
        if (newCapacity - minCapacity <= 0) {
	    //如果是第一次 nameelementData肯定是空的 满足这个条件
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
		//会返回默认大小 10 
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
	//看新扩容的值是否溢出了,溢出的话 就调用hugeCapacity方法根据情况 赋值int的最大值 或者 -8
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
6.
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }
最后返回到第四步 copy一个数组,扩容容量
然后返回第二步 添加数据,size+1

和jdk8还是有点不一样的。

add(int index, E element)-在指定位置插入数据

public void add(int index, E element) {
	//校验数组是否越界
        rangeCheckForAdd(index);
	//修改次数+1
        modCount++;
	//临时变量 数组元素个数
        final int s;
	//临时变量 数组
        Object[] elementData;
	//判断是否扩容,看当前数组的元素数量是不是和当前数组的长度一样
        if ((s = size) == (elementData = this.elementData).length)
	    //扩容机制和上边是一致的
            elementData = grow();
	//我们看下这个方法的官方参数解释
	//Object src : 原数组
	//int srcPos : 从元数据的起始位置开始
	//Object dest : 目标数组
	//int destPos : 目标数组的开始起始位置
	//int length  : 要copy的数组的长度
	//这个方法是个本地方法,它可以根据要copy的长度 把原数组的某段元素拷贝到目标数组内
	//在下边我会写一个demo验证一下
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
	//替换掉原数组index位置的元素
        elementData[index] = element;
	//长度+1
        size = s + 1;
    }
	
    //验证System.arraycopy方法
    @Test
    public void testArraycopy(){
        String[] arr = new String[10];
        arr[0] = "jack";
        arr[1] = "tom";
        arr[2] = "lucy";
        System.out.println(Arrays.toString(arr));
        System.arraycopy(arr,1,arr,2,2);
        System.out.println(Arrays.toString(arr));
        //[jack, tom, lucy, null, null, null, null, null, null, null]
        //[jack, tom, tom, lucy, null, null, null, null, null, null]
	//和我预想的结果是一样的。先把数组从index坐标 向后平移一位 然后替换掉index坐标的值
    }

LinkedList

一些属性


//数组元素个数
transient int size = 0;

//头结点
transient Node<E> first;

//尾节点
transient Node<E> last;

//内部节点类
private static class Node<E> {
	//当前节点值
        E item;
	//后向指针节点
        Node<E> next;
	//前向指针节点
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

构造方法

//空的..
public LinkedList() {
}

//调用无参构造方法 之后 调用addAll方法 后边看下这个方法
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

add(E e)

1.
public boolean add(E e) {
        linkLast(e);
        return true;
    }
2.
//第一次add
void linkLast(E e) {
	//把当前的尾节点指向l 因为last也是null 所以 l = last = null
        final Node<E> l = last;
	//新建一个节点,前节点指针指到l 后向指针指到 null 类似这样  null <- newNode -> null
        final Node<E> newNode = new Node<>(l, e, null);
	//然后让newNode又指向了last 类似这样  null <- last -> null
        last = newNode;
	//第一次的add的话 l肯定是空的 因为last是空的
        if (l == null)
	    //这样的话 first也有值了
            first = newNode;
        else
            l.next = newNode;
	//元素+1
        size++;
	//修改次数+1
        modCount++;
    }

//第二次add
void linkLast(E e) {
	//把当前的尾节点指向临时节点 l 
        final Node<E> l = last;
	//新建一个节点,前节点指针指到l 后向指针指到 null 类似这样  l <- newNode -> null
        final Node<E> newNode = new Node<>(l, e, null);
	//新的节点就变成了尾节点
        last = newNode;
	//除了第一次add,其它时候这个l永不为null
        if (l == null)
            first = newNode;
        else
	    //l后向指针指向了新节点 类似 l ->newNode
            l.next = newNode;
	//元素+1
        size++;
	//修改次数+1
        modCount++;
    }

简单来说,就是第一次添加的时候,当前元素即使头结点又是尾结点,后边继续添加的时候,总是丢到链表的尾部

根据索引来查找node节点

Node<E> node(int index) {
	//这个方法经常被其它方法调用,看一下怎么通过索引来查找对应的节点

	//判断要查询的索引在链表的左边还是右边~
        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;
        }
    }

remove方法

public E remove(int index) {
        checkElementIndex(index);
	//获取对应索引的节点~
        return unlink(node(index));
    }

E unlink(Node<E> x) {
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
	
	//如果删除的是头结点 只需要让它的next节点指向头结点就ok
        if (prev == null) {
            first = next;
        } else {
	    //让当前节点的pre节点的next节点直接指向自己的next节点。。有点绕,意思就是跳过当前的这个节点
            prev.next = next;
	    //把当前的后节点指为null
            x.prev = null;
        }
	
	//如果删除的是尾节点 只需要让它的pre节点指向尾节点就ok
        if (next == null) {
            last = prev;
        } else {
	    //让自己的next节点的pre节点指向自己的pre节点
            next.prev = prev;
	    //让自己的next节点指向空 供gc使用
            x.next = null;
        }
	//情况当前的元素
        x.item = null;
	//元素数量减1
        size--;
	//集合修改次数加1
        modCount++;
        return element;
    }

链表的方法其实还是比较简单的。

Vector

一些属性


//底层数组
protected Object[] elementData;

//元素个数
protected int elementCount;

//指定扩容数量
protected int capacityIncrement;

构造方法

//无参构造,看来它又调用自己的有参构造器了
public Vector() {
        this(10);
    }

//根据容量初始化构造器  
public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

//根据容量初始化构造器 可以指定扩容数量
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

根据构造参数来看,无论调用的是哪个,都会初始化一个固定长度为10的底层数组

add方法-扩容机制

1.
//可以看到方法都是加锁的。证明是线程安全的
public synchronized boolean add(E e) {
	//修改次数+1
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }
2.
private void add(E e, Object[] elementData, int s) {
	//如果当前数组的元素个数和数组大小一样,就需要扩容了
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        elementCount = s + 1;
    }

3.
private Object[] grow() {
	//元素当前数量+1代表最小需要空间个数
        return grow(elementCount + 1);
    }

4.
private Object[] grow(int minCapacity) {
	//newCapacity方法计算要扩容的数量大小
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

5.
private int newCapacity(int minCapacity) {
	//当前数组的长度
        int oldCapacity = elementData.length;
	//capacityIncrement这个参数如果没有设置就是0就默认扩容2倍否则根据设置的数量决定
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
	//除非在构造方法创建时指定初始化数量为0的元素 才会满足这个条件...
        if (newCapacity - minCapacity <= 0) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
	//返回扩容数量,如果溢出,则走hugeCapacity方法,这里就不看了~
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

然后返回第4步把原来的数组通过copy的方式扩容到新长度
之后回到第2步添加元素

ArrayList和Vector的扩容机制比较

1.默认情况下,ArrayList首次add必扩容,Vector默认add第11个元素才扩容
2.ArrayList扩容每次1.5倍,Vector可以指定扩容大小,或者默认2倍、

Set接口

4.png

HashSet

一些属性

//hashSet的底层是HashMap
private transient HashMap<E,Object> map;

//占位的对象....
private static final Object PRESENT = new Object();

构造函数


//new了一个hashMap
public HashSet() {
        map = new HashMap<>();
    }

//指定hashMap的大小
public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
//这个loadFactor在Hashmap的时候会具体说,主要是扩容时候的一个参数
public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

//全都是调用HashMap的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

那在这里一起说下HashMap的构造方法吧

//空参构造方法
public HashMap() {
	//赋值加载因子 loadFactor = 0.75
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

//指定map底层数组大小构造方法
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

//指定map底层数组大小 和加载因子构造方法。
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
	//这个threshold要说一下,这个是扩容的阈值,这个参数后边有说到它的作用
        this.threshold = tableSizeFor(initialCapacity);
    }

//看一下这个方法
注释说是返回大于输入参数且最近的2的整数次幂的数。比如10,则返回16
static final int tableSizeFor(int cap) {
	//里边就不看了。
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
大概就是这些方法了~

Hash底层是HashMap 让我们顺便看一下hashMap的源码吧~
看之前要先弄懂hashMap底层是什么样的数据结构 网上找了一张图~侵删
image.png
hashMap底层是一个数组链表,Node[] table, 通常叫它哈希表,
一个坑里有一条链表,当满足一定条件(后边会说到) 链表就会变成一颗树

add-hashMap(put方法)

1.
public boolean add(E e) {
	调用的是hashMap的put方法,value是 占位的空Object对象
        return map.put(e, PRESENT)==null;
    }

2.
public V put(K key, V value) {
	先对key进行了hash扰动~
        return putVal(hash(key), key, value, false, true);
    }

3.这个方法就是最大限度能保证key的hash值不一样。异或加无符号右移
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
4.接下来就是核心方法了,我们这里分两种情况来看,第一种先看首次添加的时候出现的情况
### 首次add时
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
	//这些是一堆临时变量
        Node<K,V>[] tab; Node<K,V> p; int n, i;
	//第一次add时,可以知道table是null的
        if ((tab = table) == null || (n = tab.length) == 0)
	    //在这里进行一次扩容 resize() 记录下n为扩容后的数组长度
            n = (tab = resize()).length;
	//这一行是判断经过上边扰动后的下标对应的数组元素 是否已经有值了 第一次肯定是没有值的
        if ((p = tab[i = (n - 1) & hash]) == null)
	    //创建一个节点存储下来
            tab[i] = newNode(hash, key, value, null);
        else {
	    //由于第一次并不涉及此条件,所以我这里就没贴上来
            ...
        }
	//记录集合修改次数
        ++modCount;
	//这个threshold在这里出现了,就是一个阈值,来决定是否要进行扩容
	//一会看扩容方法的时候会知道,第一次初始化的时候数组大小是16,threshold = 16*0.75 = 12
	//当你元素已经放了13个之后,虽然没有满(16),但是满足这个条件了 就需要扩容了~
        if (++size > threshold)
            resize();
	//方法是空的
        afterNodeInsertion(evict);
        return null;
    }
//上边是首次add的时候,扩容的机制。其实很简单,一系列条件都不满足,创建一个node放数组里就很好了

//接下来看扩容方法,有点长,还是按照首次和其它情况来梳理,
final Node<K,V>[] resize() {
	//table是null的
        Node<K,V>[] oldTab = table;
	//0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
	//0
        int oldThr = threshold;
	//0
        int newCap, newThr = 0;
        if (oldCap > 0) {
           ...不满足
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            ...不满足
        else { 
	    //在这里设置默认值,newCap = 16 newThr = 12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
           ...不满足
        }
	//在这里给阈值赋为12
        threshold = newThr;
	//创建指定大小16的Node数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        	...//这块首次不满足条件,先省略掉..
        }
        return newTab;
    }
首次扩容是不是很简单,只是创建了一个默认值16的Node数组 .

### 非首次add,但是hash相等时
//接下来按照非首次add方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
	    //不为空所以不扩容
            n = (tab = resize()).length;
	//这里其实还分两种情况,如果第二次add的时候 算出来的hash下标对应的元素还是空的那就直接创建元素放进去就好了,但是有种情况是,算出来的hash相等了~但是值确实是不同。这时候就会走下边的分支。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
	    //当hash相等时 走这个分支
            Node<K,V> e; K k;
		//在这里,判断hash相等并且 key(我们要存储的对象)也是相等(== or equals)的时候,表示兄弟 你放的两个元素一模一样~ 把当前的变量指向到临时变量e上 下边的分支就不用看.
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
	    //到这里,如果你存储的valu是 null, name直接返回就是null,
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
		//注意看这一句,前边这个条件永远为真, 所以,这个分支一直会进
                if (!onlyIfAbsent || oldValue == null)
		    //这个作用就是替换掉当前节点的value
                    e.value = value;
                afterNodeAccess(e);
		//返回oladValue 下边的扩容 修改 都不走了,意思就是 我把你老的元素给你返回,把你心的元素给你放进去了。类似更新的方法。
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
上边就是,非首次add 但是hash相等,会直接set新的值,并返回旧的值

### 非首次add,hash不相等时
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
	    //我们继续走到这里,如果hash相等,但是对象却是不同,那么我们就要向里边放新的数据了
	    //这里有个分支,看你当前是链表还是树,这个后边再说,我们假设现在还是链表
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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);
			//这个时候就会判断当前这条链要不要变成树 在这里
			//这个TREEIFY_THRESHOLD 是固定值8 
			//那么满足树化的条件就是 添加完当前元素之后 当前链表已经有7个节点。就会进行树化~ 
			//但是树化的前提,当前数组大小要大于等于64个 在下边会讲到
			//所以最终树化的条件就是,当前hash表的长度大于等于64并且当前链表有7个节点
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
	    //这个时候e 是空的,因为最后一个循环 (e = p.next) == null
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
	//集合修改次数+1
        ++modCount;
        if (++size > threshold)
	    //扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

//上边说到树化这个方法 可以看到 MIN_TREEIFY_CAPACITY 这个值是64 如果当前hash表小于64 就会进行扩容
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
           ...
        }
    }

### 非首次扩容
//我们最后看一下非首次扩容时候的逻辑
final Node<K,V>[] resize() {
	//非首次扩容的时候 这个 oldTab 可就不是null了~
        Node<K,V>[] oldTab = table;
	//把老的hash表长度记录下来
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
	//老的扩容阈值记录下来
        int oldThr = threshold;
	//临时变量
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
		//进入这个分支,把老的hash表长度 和阈值都扩容两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
           ...//不满足条件
        else {               // zero initial threshold signifies using defaults
            ...//不满足条件
        }
        if (newThr == 0) {
           ...//不满足条件
        }
	//新的扩容阈值赋值给成员变量
        threshold = newThr;
	//创建新的扩容后的hash表
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
	    //在这里开始循环老的hash表 把内容都cp过去
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
			//如果当前hash表中仅有一个节点并且没有树化,直接挪坑
                        newTab[e.hash & (newCap - 1)] = e;
                    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;
                        }
                    }
                }
            }
        }
        return newTab;
}

LinkedHashSet

一些属性

//linkedHashSet这个类是继承HashSet的,所以都是用的父类属性
public class LinkedHashSet<E>
    extends HashSet<E>

构造方法

//无参构造
public LinkedHashSet() {
        super(16, .75f, true);
    }
//带初始化长度的构造方法
public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
//带初始化长度和加载因子的构造方法
public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

//我们可以看到,这三个构造方法,统一都是调用父类的一个构造方法
//就是HashSet的这个方法,可以看到 底层用的是LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

//这个LinkedHashMap又是啥? LinkedHashMap继承的是HashMap 绕了一圈下来,还是HashMap
我们具体看一下类图就明白了~

image.png

为什么LinkedHashSet(LinkedHashMap)是有序的?

在这之前,我们已经知道Map底层是如何put进去数据的,
那这个有序我们是如何理解的呢?有序是指 我们加进去元素的顺序 要和 我们取出来元素的顺序保持一致!

我们看一下LinkedHashMap内部的一个类

//这个类很重要,这个类继承了Node类,我们知道Node是链表类型的,它继承了链表的特性,可以指向前也可以指向后,Entry又扩充了两个属性 叫befor,after,什么意思呢 就是双向,有顺序,befor存储前边的节点、after存储后边的节点
static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

这个Entry大概长这样
image.png
黄色的就是一个一个Entry,它们的befor可以指向任意一个Entry(Node) after也是这样。

Add方法

由于LinkedHashSet 底层用的是LinkedHashMap
LinkedHashMap又继承了HashMap
所以add方法用的是父类的add方法
前边我们分析过了HashMap的add方法,但是由于Java的多态机制,我们再重新看一下几个重要的方法


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
	    //注意这个newNode方法,这里走的是LinkedHashMap的nweNode方法
            tab[i] = newNode(hash, key, value, null);
        else {
           ...//不相关
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

2.
//我们先看一下,LinkedHashMap在newNode的时候发生了什么
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
	//它先创建了一个Entry类,也就是双向链表类型的
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
	//这个方法很重要
        linkNodeLast(p);
        return p;
    }

3.
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
	//因为要添加新的node 所以先把尾部赋予临时变量last
        LinkedHashMap.Entry<K,V> last = tail;
	//把要新增的p节点放到链表的尾部tail
        tail = p;
	//如果是第一次 name头部节点肯定是null的
        if (last == null)
	    //让头部节点也指向这个新创建的节点
            head = p;
        else {
	    //如果非首次的话,就让当前创建的节点前向指到临时变量last
            p.before = last;
	    //当然要互相指一下,
            last.after = p;
        }
    }
上边这个方法就完成了新建节点的时候,双向指定的问题,那么无论后边有多少个node添加进来,都能够保证是有顺序的.

这样我们大概就知道LinkedList为什么是有序的了。其实扩容还是走的hashMap的方法,只不过在每次add的时候多了一步维护entrySet的操作,使得整个链表是有序的.

Map接口结构图

2.png

实现类型底层数据结构线程安全性使用场景扩容规则
HashMap数组+单向链表+红黑树不安全无序首次默认16,后序以2倍扩容
HashTable数组+单向链表安全无序首次默认11,后序以2倍+1扩容
TreeMap二叉树不安全可以排序树无需扩容

HashMap

HashMap在前边分析HashSet的时候其实已经看过了,因为HashSet底层用的就是HashMap.所以在这里就不过了~ 可以看前边分析HashSet的过程

HashTable

一些属性

table表,是个数组, 里边存放单向链表
private transient Entry<?,?>[] table;

//数组的实际元素个数
private transient int count;

//table扩容阈值
private int threshold;

//table扩容因子
private float loadFactor;

构造方法


//无参构造方法
public Hashtable() {
	//调用指定大小和指定加载因子构造方法
        this(11, 0.75f);
    }

//指定数组大小构造方法
public Hashtable(int initialCapacity) {
	//调用指定大小和指定加载因子构造方法
        this(initialCapacity, 0.75f);
    }

//指定大小和加载因子构造方法
public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

	//无论如何初始化的时候 数组最小大小为1
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
	//计算扩容阈值, 初始化大小*加载因子
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

put方法


//可以看到hashtabl每个方法都有 synchronized关键词,表示线程安全
public synchronized V put(K key, V value) {
        // 看来 hashtabl的value值不允许为null
        if (value == null) {
            throw new NullPointerException();
        }

        
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
	//计算hash值
        int index = (hash & 0x7FFFFFFF) % tab.length;
	//取出对应hash索引位置的元素
        Entry<K,V> entry = (Entry<K,V>)tab[index];
	//如果取出来不为null,那就遍历这个链表,看有没有相同的,如果有那就替换掉value返回oldValue,如果没有,后边再说
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
	//开始add元素
        addEntry(hash, key, value, index);
        return null;
    }


private void addEntry(int hash, K key, V value, int index) {
        Entry<?,?> tab[] = table;
	//看是否到达了扩容的临界值
        if (count >= threshold) {
	    //扩容方法
            rehash();
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
	//这里需要注意一下,上个方法我们说过,循环到最后发现没有相同的元素怎么办,hashtable是把新添加的元素当成头结点,指向原来的元素...这里和hashmap是不一样的
        Entry<K,V> e = (Entry<K,V>) tab[index];
	//把新添加的元素指向原来的头结点
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
    }

扩容方法


protected void rehash() {
	//取出当前table的长度
        int oldCapacity = table.length;
	//创建临时变量保存当前hash表
        Entry<?,?>[] oldMap = table;
	//计算新的table长度 2倍+1
        int newCapacity = (oldCapacity << 1) + 1;
	//一些长度校验
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
	//创建新的hash表
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
	//计算新的扩容阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
	//把老的hash表指向新的hash表
        table = newMap;
	
	//这里是对老数据的转移~主要是链表+索引的计算.
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

所以看起来HashTable和HashMap还是有些区别的. 最大的区别就是线程的安全性了.

TreeMap

TreeMap最大的特点就是可以对Key进行排序, TreeSet底层用的也是TreeMap,所以这里只对TreeMap源码进行一些研究

一些属性

//这个比较器就是treeMap可以进行排序的秘密,后边会讲
private final Comparator<? super K> comparator;

//树的根节点
private transient Entry<K,V> root;

构造方法


//无参构造
public TreeMap() {
	//不指定排序方法
        comparator = null;
    }

//指定排序方法构造器
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

put方法

public V put(K key, V value) {
	//获取根节点 首次肯定是null的
        Entry<K,V> t = root;
        if (t == null) {
	    //这个方法我刚开始没看懂.搜索了一下才理解,这个是判断当你put的键为"null"时,你有没有实现排序方法,如果没有实现 则就会抛出Null指针异常
	    //我觉得它的意思可能是,null是一个比较特殊的值,如果你要排序呢,那就要实现排序器的时候为"null"值定义好规则.
            compare(key, key); // type (and possibly null) check
	    //初始化root节点
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
	    //直接return掉.添加完成
            return null;
        }
	//非首次put 才会走下边
	//临时变量 存放比较结果
        int cmp;
        Entry<K,V> parent;
	这个cpr 是 初始化时候赋值的比较器
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
	    //如果有指定比较器的话
            do {
		//从根节点开始
                parent = t;
		//开始比较结果
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
		    //继续比较树的左子节点
                    t = t.left;
                else if (cmp > 0)
		    //继续比较树的右子节点
                    t = t.right;
                else
		    //如果两个元素按照你的比较器规则是相等的 那就直接替换当前节点的值 然后return掉 
                    return t.setValue(value);
            } while (t != null);
        }
        else {
	    //在这里我们可以看到,如果没有实现比较器对"null"做处理,那么就会抛出空指针异常
            if (key == null)
                throw new NullPointerException();
		//这里会使用key的数据类型默认实现的比较器来比较
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
	//比较完毕之后,这个parent就是树底的某个节点
        Entry<K,V> e = new Entry<>(key, value, parent);
	//根据比较结果来判断时挂在树的左子节点还是右子节点
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
	//插入一个新子节点之后,会对这棵树进行修正..看不懂..等我学完红黑树再回来看吧~
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

treeMap的排序如何实现

前边我们看treeMap的构造方法 和put方法的时候 可以看到是有一个比较器来决定排序的规则,那么这个排序器是什么东西呢?
//我们可以在创建TreeMap的时候创建一个匿名内部类来决定排序的规则
TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return 0;
            }
        });

//例如我们要根据Dog类的age属性来排序 那么我们可以这么写
TreeMap treeMap = new TreeMap((o1, o2) -> {
            Dog dog1 = (Dog)o1;
            Dog dog2 = (Dog)o2;
            if(dog1.getAge() > dog2.getAge()){
                return 1;
            }
            if(dog1.getAge() < dog2.getAge()){
                return -1;
            }
            return 0;
        });

        treeMap.put(new Dog("a",11),1);
        treeMap.put(new Dog("b",22),1);
        treeMap.put(new Dog("c",14),1);
        treeMap.put(new Dog("d",55),1);
        treeMap.put(new Dog("e",113),1);
        treeMap.put(new Dog("f",14),1);

        System.out.println(treeMap);


{
Dog{name='a', age=11}=1, 
Dog{name='c', age=14}=1, 
Dog{name='b', age=22}=1, 
Dog{name='d', age=55}=1, 
Dog{name='e', age=113}=1}

可以看到我们输出确实是按照age属性的.

总结

到这里为止,我把常用的一些集合实现类的底层数据结构和扩容方法,以及最重要的add\put方法给看了一遍~
感觉难倒不是那么难,关键是,理解底层数据结构之后 在业务场景使用的情况下,可以正确的选择到底要使用哪个集合类.
一步一步写的.可能有错误~可能有些东西我也不知道该如何解释~毕竟我还是个小白.
里边还有好些东西我不懂,像红黑树这块我还没仔细去了解过~下一步可能就要去深耕一下数据结构这块,如果数据结构不熟悉,看源码应该还是挺困难的..

Q.E.D.


今天也要加油鸭~