Java集合体系梳理 - Yoka的学习小屋

Java集合的根接口为Collection和Map，前者是单列集合，后者是双列集合

一、Collection
Collectin有三个主要实现，分别是抽象类AbstractCollection和接口List、Set。List、Set只是定义了集合的一些操作
AbstractCollection定义了一些通用的方法：isEmpty、contails、toArray、remove等，基本都是通过迭代器实际操作的，还有两个抽象方法iterator和size，需要子类覆写。
AbstractCollection有抽象子类AbstractList和AbstractSet等，同样定义一些通用方法。
AbstractList中的方法add、set、remove操作都抛出异常，也就是说必须子类具体实现。AbstractList重写了父类的iterator方法，Itr实现了Iterator并重写了hasNext、next等方法。另外还实现了listIterator方法，是个集合专用的迭代器，可以进行增加元素、向前遍历元素等。AbstractList源码中另外写了一个子类SubList和RandomAccessSubList，用于返回子集合。
AbstractSet只重写了equals、hashCode和removeAll方法，都是通过迭代器进行操作。

1.ArrayList
ArrayList是AbstractList的子类，并实现了List、Cloneable、Serializable、RandomAccess。
ArrayList中维护一个Object类型的数组，list的大小指该数组的大小。ArrayList的构造方法可以初始化大小，如果不设置大小的话默认为10，但是使用了懒加载，最初是空数组，在add元素的时候才会到10。
get方法直接返回数组下标处元素；
set方法将指定下标处元素替换并返回旧元素；
add方法首先确定容量大小，然后在数组末尾size++处追加元素，同名add方法可以在指定下标处设置元素，大于下标的整体移后一位，用的是System.arraycopy方法；
addAll方法先确定容量，然后将传入集合复制到本数组
remove方法移除指定下标元素，大于下标的前移一位，同样是System.arraycopy方法，remove可以指定元素，for循序遍历数组到该元素，然后移除掉；
clear方法将所有元素设置为null，size设置为0
subList方法截取数组的一段，SubList是一个内部类，使用SubList需要注意，SubList继承自AbstractList而不是ArrayList，所以不可以强转，SubList构造方法传入了parent，操作的也都是parent的方法和元素，和parent互相影响。
ArrayList扩容：添加元素的时候检查容量是否够用，不够用就启用扩容，grow方法为核心源代码，每次扩容规则为，先用[int newCapacity = oldCapacity + (oldCapacity >> 1)]计算新容量为旧容量的1.5倍，然后比较新容量和所需容量，如果新容量不够用，就把所需容量作为新容量。
迭代器有iterator和listIterator两种，其实AbstractList中也都实现了，ArrayList中的注释表示有优化，但是看代码。。。没什么优化。
迭代器的modCount作用为在迭代过程中不允许修改list，实现原理为创建迭代器的时候expectedModCount=modCount，迭代器自己的remove方法中也会设置expectedModCount=modCount，而ArrayList的add、remove方法会让modCount增加一位，迭代器迭代的时候发现modCount被修改和预期expectedModCount不一样，就直接抛出异常

2.Vector
Vector同样是AbstractList的子类，并实现了List、Cloneable、Serializable、RandomAccess。和ArrayList作用类似，而又区别于ArrayList
维护的一样是一个Object类型的数组，但是构造时没有ArrayList的懒加载，默认数组大小就创建为10。构造的时候可以传递一个参数capacityIncrement作用为每次扩容大小，不传的话默认是0
扩容：流程和ArrayList类似，只是扩容大小有区别，[int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);]，新容量为旧容量+扩容值或者两倍旧容量
操作方法和ArrayList基本一样，但是基本每个操作就增加synchronized作为锁，保证多线程安全

3.LinkedList
继承自AbstractSequentialList，间接继承自AbstractList，实现List接口、Deque、Cloneable、Serializable
维护两个Node节点，first和last。Node节点是LinkedList的内部类，有三个属性，item值，Node next和prev，prev和next实现链表的功能
add方法会添加到链表最后，对之前最后的元素进行prev和next双向绑定
remove方法传入object，从头遍历链表，找到item相同时，在链表中进行unlink移除，所有属性设置为null，object所在节点的前后节点连接在一起
get方法传入index，说明要查询第index个Node的值，对list的大小除以2决定从头遍历还是从尾遍历，for循环遍历链表即可
其他所有操作都是对first和last节点之间的链表做操作，流程类似
迭代器重写了父类AbstractSequentialList的抽象方法listIterator(int index)，返回的是ListItr，它实现了ListIterator。迭代顺序为链表从头到尾

4.HashSet
HashSet继承自AbstractSet，同时实现了Set、Cloneable、Serializable。
HashSet中维护了一个HashMap，初始化的时候set大小、负载系数都是此HashMap的属性。添加元素的时候add方法将key和value存入map，value是类中定义的一个静态final的Object对象。返回的迭代器也是HashMap的keySet的迭代器KeyIterator。
HashSet的特征就是HashMap的key的特征！

5.TreeSet
TreeSet继承自AbstractSet同时实现了NavigableSet、Cloneable、Serializable，NavigableSet继承自SortedSet，SortedSet又继承自Set
维护一个NavigableMap对象，其实构造函数创建的时候默认是TreeMap，所以类似于HashSet和HashMap的关系，TreeSet也依赖于TreeMap，初始化的时候参数都是在给TreeSet进行设置
add元素的时候，调用的是TreeMap的put方法，key为要放入的值，value是类中定义的final类型Object对象
TreeSet的特征就是TreeMap的key的特征！

二、Map
Map接口中写了很多default方法，比如remove、replace、forEach等
Map中定义了子接口Entry<K,V>，定义了getKey、getValue、setValue等方法
AbstractMap抽象类实现了Map，定义了一些get、remove、ccontainsKey等方法，基本都是通过迭代器实现的。put方法只是抛出异常，需要子类重写
AbstractMap中，entrySet方法是一个抽象方法，要子类实现，需要返回一个Set集合。keySet和values属性分别是key和value的集合，也提供了方法去获取

1.HashMap
HashMap继承自AbstractMap，实现了Map、Cloneable、Serializable
构造函数可以传入初始化大小和加载因子，如果不设置的话默认加载因子为0.75，不设置map大小的情况下Node数组为空，在put元素的时候进行resize，数组大小为16
定义了Node<K,V>，实现自Map.Entry<K,V>，有hash、key、value、next参数。HashMap维护着一个Node数组，我们通常说HashMap由数组、链表和红黑树组成，Node数组就是这个数组，Node有next属性，所以可以作为链表，TreeNode继承自Node，是一个红黑树结构，所以node节点可以转换为红黑树结构。
为什么用hash实现Map，如果采用纯数组循序存储，每次取值都需要遍历，而HashMap根据键的hashcode值存储到数组对应位置，可以直接定位到它的值。可能出现的hash碰撞使用链表的方式去解决
为什么数组大小为2的次幂：因为要进行哈希运算，2的n次方长度可以让数据散列地更均匀，减少hash碰撞；HashMap地扩容有迁移数据地操作，如果是2的n次方，不需要重新hash定位位置，新位置要么在原位置，要么在原位置+旧数组长度位置

put方法的流程和源码解读：

1.判断Node数组是否为空，为空的话初始化数组
2.如果hash值对应数组处为空，则将新数据Node节点插入数组中
3.如果hash值数组处不为空，说明数组此处有数据，判断旧数据和新数据key是否相同，相同则找到了位置，需要替换其value
4.数组中旧数据和新数据key不同，说明旧数据node连接在此node上
5.判断当前Node是否为TreeNode，如果是，按TreeNode的方式添加位置
6.不是TreeNode，则为链表，遍历并寻找是否有相同的key，有的话找到位置，直到最后还没找到，则连接在最后
7.判断链表长度大于8，则转换结构为TreeNode
8.如果有旧数据，替换value，返回旧数据
9.modCount++，如需扩容的话，进行扩容

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value，如果存在key，是否要覆盖原数据，true表示不覆盖，false表示覆盖
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	// tab为当前node数组
	Node<K,V>[] tab; 
	// p为将要插入的位置的node
	Node<K,V> p; 
	// n是当前node数组的长度，i是(n - 1) & hash算出来p的下标
	int n, i;
	// 当前node数组是空，对数组进行resize初始化
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	// 要插入的位置为空的话，此位置创建新node
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	// 要插入的位置不为空，node数组此位置已经存在数据p
	else 
		// e为旧的node
		Node<K,V> e; K k;
		// 已存在的node的hash、key和新的数据完全一样，设置e等于当前node p，最后统一处理e。此处是数组结构
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		// p处有东西，并且和将要插入的数据key不同。判断当前p结构是否为红黑树，如果是树，插入到树中
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		// p现在还不是树，那么它是链表结构
		else {
			// 遍历链表
			for (int binCount = 0; ; ++binCount) {
				// 链表中next节点为空时，将新数据连接在p的next上
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					// 如果链表长度大于8，转换hash处结构为树，treeifyBin方法中会判断数组长度是否大于64，大于64的话才会转换结构，否则的话先对数组进行扩容
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				// p的next（也就是e）不为空并且key和新数据的key相同，break掉
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
					
				// 当前节点赋值给p，进行下一次循环
				p = e;
			}
		}
		// 旧的node e不为null，要返回旧value。e等于null的时候在前面已经newNode或newTreeNode插入过了，所以可以不处理
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			// 覆盖 或者 旧数据为空，设置e的value为新value
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			// HashMap的此方法没有做任何操作，LinkedHashMap继承HashMap并做了处理
			afterNodeAccess(e);
			return oldValue;
		}
	}
	
	// 迭代器modCount修改
	++modCount;
	// map大小大于容量，进行分配
	if (++size > threshold)
		resize();
	// HashMap的此方法没有做任何操作，LinkedHashMap继承HashMap并做了处理
	afterNodeInsertion(evict);
	return null;
}

get方法的源码解读：

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; 
	Node<K,V> first, e; 
	int n; K k;
	// 当前node数组为空、长度不大于0、hash处为空（数组下标处），要直接返回null，不为空则查找
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		// 这个first是数组中的node，如果此node的key和要查询的key相同，返回此node
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		// 如果first的next为空的话，元素不存在，不为空的话要继续查询
		if ((e = first.next) != null) {
			// 判断当前node是否TreeNode，TreeNode要用树的方式或者
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			
			// 不是treeNode，那么是链表，循环获取
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

remove方法流程：

1.判断数组是否为空、数组hash处Node是否为空，为空的话不需要下一步了，直接返回null
2.判断数组中Node是否为要删除的数据，如果是，就找到了目标node
3.数组中Node不是，判断Node结构是否是TreeNode，如果是的话按TreeNode方式寻找到目标node
4.Node为链表，遍历寻找到目标
5.根据Node结构具体处理，如果是TreeNode，在TreeNode中处理；如果是数组，将目标node的next放在数组中；如果是链表，node的next连接在前一个节点
6.modCount++，数组大小--

扩容：
当元素个数超过threshold临界值时，会对数组进行扩容，每次扩容为原来数组长度的两倍
临界值 = 数组大小 * 负载因子
如果我们的数据量为1000，那么我们要设置数组长度为1000/0.75=1334，实际大小会是2048
代码中用resize方法，先计算出新数组容量、新临界值，建立新Node数组。对旧数组进行遍历，重新计算位置填入新数组
计算位置的方式大致为将新数组分为原数组长度的前半部分和后半部分，对每个数组下标处的链表内元素hash值与运算旧数组长度，得到结果为0或者旧数组长度两种元素，分别连成两个新链表插入到原位置和原位置+旧数组长度位置处（连接方法为head为开始元素，tail不断赋值和移动直到最末端，最后把head放入数组，tail的next置为null）

当元素数量为下面数量时，发生扩容：
元素数量 1 13 25 * * 385
数组大小 16 32 64 * 512 1024
临界值 12 24 48 * 384 768
负载因子 0.75

2.LinkedHashMap
LinkedHashMap继承自HashMap，实现Map接口，所以它拥有HashMap的特性
创建内部类Entry继承自HashMap的Node，但是在Node的基础上增加了Entry<K,V> before, after两个属性实现双向链表连接
所以LinkedHashMap是在HashMap的结构上增加了一个双向链表结构，HashMap的结构仍然存在，只是LinkedHashMap重写了插入和获取方法实现了顺序存取，对于数据要变化时重写对应方法实现双向链表的相应变化
put数据时，重写了newNode方法，实现了插入链表最后和链表前后的连接
get数据时，用HashMap的方式获取到，判断accessOrder是否为true，是的话移动该Node到双向链表的最后tail处，可实现LRU缓存的场景
迭代器重写，具有的是双向链表的特征，使用after往后进行遍历

3.HashTable
继承自Dictionary抽象类，实现了Map、Cloneable、Serializable接口
HashTable常用来和HashMap比较，因为它是线程安全的Map，它的操作方法都会加上对象锁synchronized，而HashMap不安全。
实现上比HashMap简单，只用到数组和链表而没有用到红黑树，用链表解决了hash冲突。HashTable数组大小没有按2的n次方设计，扩容也只是重新hash，没有HashMap的扩容巧妙。
HashTable默认初始值为11，加载因子为0.75，扩容规则为2n+1
负载因子、临界值、数组大小的关系和HashMap是一样的，临界值=数组大小*负载因子，当map元素数量大于临界值时发生扩容，扩容规则为2倍旧数量+1
扩容流程：计算新的数组大小和临界值，建立相应大小的新Entry数组，遍历旧数组，将数据重新填入新数组。详细解释填新数组流程，遍历旧数组及其链表，链表上的元素重新进行hash计算得到新的位置，放入数组中，后续的同样位置元素next为当前数组已存在元素，然后将新元素放入当前数组位置
put方法首先hash计算到数组位置，遍历数组及链表查询该数组位置有无元素，如果已经有的话就替换value并返回旧元素value；如果不存在的话，创建新Entry节点，其next为数组处已有节点，最后将新Entry放在数组的该位置

4.TreeMap
继承抽象AbstractMap，实现NavigableMap、Cloneable、Serializable
NavigableMap接口继承自SortedMap接口，SortedMap继承自Map接口
TreeMap维护一个root节点Entry，Entry是实现了Map中Entry的，有key、value、left、right、parent、color参数，可以看出构建的是一个树结构，而不是Hash类map中的数组+链表结构
构造的时候可以指定顺序比较器，不指定的话就是比较器comparator为null，自然排序
put元素的时候，先判断比较器是否为空，不指定的话用元素的自然排序，新元素从root开始比较，寻找要放置的位置，小于是左边，大于是右边，直到有原节点的左或右为null，创建新Entry，其parent节点为上述原节点，此时新元素已经连接到了原来的树上，但是树还不是最终状态，需要进行修复（。。。旋转着色）
get的时候，从头到尾比较，获取到值