简介
在jdk中提供了很多工具包，方便开发人员在实际工作中使用，就比如集合工具类。最开始接触Java时，经常会被问道常见的集合有哪些，原理是什么，优缺点之类的问题，所有很早之前看了一些常用的Java集合源码，通过简单的分析源码，对比各自的优缺点，以及分析网上的面试题上常问的一些问题。
集合介绍
Java中的集合主要分为两大类：
- 双列集合。
- 单列集合。
双列集合就包含我们常用的HashMap，LinkedHashMap，ConCurrentHashMap等等，其顶层接口为Map。单列集合包含我们常用的ArrayList，LinkedList,Vector,HashSet等，其顶层接口为Collection。以这两个顶层接口为拓展，集合的实现类远不止以上举例这些。以这两类接口为主，对比以下集合的优缺点（Java中的集合远不止这些）。
体系结构图
集合的优缺点对比
以Map接口的实现类集合：
- HashMap：使用数组+单向链表+红黑树存储元素，可以存储null值，线程不安全，性能相对较高，无序不可重复
- HashTable：主要和hashmap作比较，线程安全，不能存放null
- LinkedHashMap：HashMap的子类，能够保证元素的访问顺序，线程不安全，基于LRU实习的顺序访问。有两种顺序（插入顺序，访问顺序）。
- Properties：一个和流技术相结合的类。是一个可以持久化的属性集，既可以存储在集合中，也可以持久化到设备中，也可以从设备中读取属性集。
- TreeMap：：无序（插入和遍历顺序不一致），不重复，如果指定了自定义比较器（key自身实现的不算）key和value可以为null，没有指定比较器则key不能为null并且可能不能存放不同类型的key（一般自带的比较器都不能比较不同类型key），可以指向元素的迭代顺序，
- ConCurrentHashMap：同hashmap一样，在HashMap的基础上增加了线程安全，k，v不能为null（线程安全最常用的双列集合）
- IdentityHashMap：表示存储的key是否为唯一的值，是通过key是否为同一个对象。即：只通过==来判断，而不通过equals，也就是说，如果两个key相同，那么这两个key必须是同一个对象。
- WeakHashMap：当除了自身有对key的引用外，此key没有其他引用，那么WeakHashMap会在下次进行增删改查操作时及时丢弃该键值对，节约内存使用。
以Collection接口的实现类集合：
- ArrayList：底层数据结构是数组,查询快,增删慢线程不安全,效率高。有序,可重复
- Vector：底层数据结构是数组,查询快,增删慢，线程安全,效率低。有序,可重复
- LinkedList：底层数据结构是链表,查询慢,增删快，线程不安全,效率相对较高。有序,可重复
- HashSet：底层数据结构是数组+链表+红黑树，性能相对较高，线程不安全，无序,不可重复
- TreeSet：底层数据结构是树形链表，自动排序,线程不安全，不可重复
- LinkedHashSet：底层数据结构是链表，有序,线程不安全，不可重复
结合源码分析
ArrayList源码分析
创建一个ArrayList时做了些什么？
无参构造：
ArrayList<String> list = new ArrayList<>();
有参构造-指定初始化容器大小：
ArrayList<String> list1 = new ArrayList<>(1);
可以从上述源码中看到，无论是通过有参还是无参构造，以及其他为列举的构造函数创建ArrayList对象，目的都是在对elementData这个字段进行赋值。通过下面代码可以看到elementData实际上就是一个数组，也对应了‘底层的数据结构是数组’这个特性。后续所有的对ArrayList的操作实际上都是围绕这个字段进行的，当然还有一些其他的辅助字段，后续会进行说明。
使用ArrayList的增删改查操作
获取操作
因为get()方法获取元素都是直接从数组中获取的（数组在内存中是一块连续的空间，至少在逻辑上是，虚拟机知道这块连续的空间，那么根据下标查找元素也就不在话下），也就是对应着查询快这个特性，‘查询快’也是相对的，这个需要对比其他不是数组的集合才会更能体现他的‘查询快’。
添加元素
再查看添加操作前，需要先了解几个ArrayList的内部字段，在添加操作时会用到。
- private int size; //记录实际集合内部的实际元素个数，同时也是最后一个元素的索引位置
- protected transient int modCount = 0; //父类中的字段，用于记录增删改的次数，每次增删改都会+1
在添加时按照索引位置依次添加，获取时还是根据相同的索引位置获取元素，所以是有序的。每个元素都在对应的索引位置，互不影响，所以可重复。
扩容操作
在创建对象时，元素的长度一开始就固定了，如果在后续不断向集合中添加元素，那么势必会导致索引越界。所以在上述添加操作中，一定会对elementData元素进行扩容检查。
扩容方法：
这里调用elementData = Arrays.copyOf(elementData, newCapacity);对数组进行扩容，实际上会调用 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); ，这里就是重新创建数组，在添加元素时，容器长度不够就会触发扩容。创建数组时虚拟机会向操作系统申请内存，开辟空间，将原来的数据放进去，数组长度越大，占用内存空间越大，这是一项非常耗时的操作，所以说他的增删慢。
线程不安全？
在多个线程对同一个ArrayList对象进行操纵时，可能会引发线程安全问题。那么何时会引发线程安全问题？
在添加操作中：add()方法中代码
ensureCapacityInternal(size + 1); elementData[size++] = e;线程A,B同时添加元素，size+1或者size++不能保证原子性，可能会加两次一，再走下一段代码，就可能索引越界，可能覆盖元素，也可能跳过一个索引下标直接添加到了第三索引，导致中间元素为null使用迭代器遍历元素当有一个迭代器中删除元素时，其他迭代器可能出现ConcurrentModificationException
使用普通for遍历时如果有一个for删除元素，其他for可能出现IndexOutOfBoundsException多线程中可以使用CopyOnWriteArrayList代替。
- 单线程中，使用增强for（迭代器）遍历元素却使用list中的remove方法则会抛出ConcurrentModificationException
ArrayList的内部结构
接口继承关系：
从上图中可以看到ArrayList继承了AbstractList类，实现了RandomAccess接口，实现了Cloneable接口，实现了Serializable接口。那么继承和实现这些类有什么用？Java中实现和继承某些特定的接口和类就必须实现其抽象方法，这类方法抽象的表示该方法的作用，由具体的子类去实现逻辑
继承AbstractList类，表示ArrayList具有常用的集合操作功能，如增删改查，get(),add()
实现了RandomAccess接口，该接口并没有任何抽象方法，表示该接口的实现类应该具备随机快速访问元素功能
实现了Cloneable接口，具有克隆功能
实现了Serializable，可以通过序列化传输
内部维护了迭代器
Java当中的语法糖，可以通过for循环进行快速遍历。通过成员内部类实现Iterator接口，操作对象内部的几个元素，以实现对元素的快速遍历，本质是调用此接口。
LinkedList源码分析
LinkedList和ArrayList的原理基本一样，最大的区别就是LinkedList底层用的不是数组而是链表，那么它是如何通过链表存储元素的？还是从构造方法说起。
LinkedList构造方法
可以看到LinkedList()创建对象时并没有做一些额外的操作，有参构造也是调用了addAll(),重点还是在添加元素上。先看下它的单个添加元素方法add().
添加元素
可以看到add()方法在添加元素的时候直接调用linkLast(E e)方法，本意表示是将元素添加到链表的末尾。 再看linkLast()方法，每次添加元素时都会创建一个node对象（表示链表中的一个节点），这个node对象在创建时记录三个信息，分别是：上一个node对象，当前创建的node对象，下一个node对象（下一个节点不知道所以是null），用内部的三个字段表示。这样一来，只要我们获取到其中一个node对象，那么就能根据这个node对象的内部字段依次获取到上一个或下一个node对象，这样就能获取所有的元素信息了，像这种一个一个node对象通过内部字段记录上下游元素的形式就形成了一条链表，所有说他的底层结构是链表，并且这种上下游的node都记录了彼此的信息，不论是从上往下还是从下往上都是能找到对方，称为双向链表。
然后再回到linkLast方法，这个方法的大概意思是：每次添加新的元素时，都会创建一个node，并且会把链表的最后一个node当成新node的上一个节点，然后把新node挂到最后一个node的下一个节点，那么新node就是当前的最后一个元素。在这还维护了两个字段first，last分别表示第一个和最后一个元素，这样在遍历的时候只需要知道这两个元素就能找到所有的元素。
获取元素
再看看get()方法是现实：
主要看node()方法查找元素，判断index的位置，如果在链表的前半部分，那么就从第一个元素从前往后找，如果在链表的后半部分那么就从最后一个元素往前找，找到就返回。
特性分析
再来看看LinkedList这个特性： 查询慢,增删快，线程不安全,效率相对较高。有序,可重复。
查询慢,增删快：这个相对与ArrayList来说，查询慢的原因是因为链表不像数组，就在连续的内存空间内，需要jvm先找到第一个node对象，在找node对象的记录下一个的元素的字段，通过字段找下一个node，每查找一个就需要重复一次这个操作，所以说相对较慢。增删快是因为在增加时已经知道last的位置，只需要把新元素挂在后面，删除也只需要把中间元素移除，再将上下元素互相引用，不需要像数组需要重新创建新的数组来维护内部元素。
线程不安全：
- 没有加锁，同时添加会存在覆盖元素的情况，
- 跟arraylist一样都是通过内部类实现了iterator，集合中modCount记录了集合内部修改的次数，任何迭代器中的修改方法都会修改modCount并使之与迭代器expectedModCount相等，如果不等则抛出了ConcurrentModificationException，通过LinedList修改元素，只会改变modcount的值，当使用linkedList修改元素，用iterator遍历就会抛出ConcurrentModificationException；
- 可以用线程安全的ConcurrentLinkedQueue代替。
有序，可重复：链表本身就是有序的，并且没有去重。
在一些增加或删除的方法，会遍历链表，如果size过大，遍历所需时间增加，也影响增删速度，当然如addFirst,addLast,removeFirst,removeLst直接操作头尾元素没有中间层不影响增删速度
扩容机制
基于链表，没有初始化大小，也没有扩容机制；
HashMap源码分析
HashMap的源码在Java集合中属于相对复杂的，在看源码之前先了解下它的成员变量，它的每个成员变量具体作用
成员变量
/**
* 默认的初始容量,必须是2的幂 << 左移运算符 1左移4位 16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，如果两个带参数的构造函数中的任何一个隐式指定了更高的值，则使用该值.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的负载因子.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 当桶(bucket)上的结点数大于这个值时会转成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 当桶(bucket)上的结点数小于这个值时树转链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶中结构转化为红黑树对应的table的最小大小
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 存储元素的数组，总是2的幂次倍
*/
transient Node<K, V>[] table;
/**
* 存放具体元素的集
*/
transient Set<Entry<K, V>> entrySet;
/**
* 此映射中包含的键-值映射的数量,存放元素的个数，注意这个不等于数组的长度。
*/
transient int size;
/**
* 每次扩容和更改map结构的计数器
*/
transient int modCount;
/**
* 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
* The next size value at which to resize (capacity * load factor).
*/
int threshold;
/**
* 哈希表的加载因子
*/
final float loadFactor;
构造方法
/**
* 无惨构造方法,将默认的加载因子0.75赋值给loadFactor
*/
public HashMap() {
// 将默认的加载因子0.75赋值给loadFactor，并没有创建数组
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 指定容量大小的构造函数
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
*构造一个与指定Map具有相同映射的新HashMap。
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 指定的初始容量和负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//边界值检查
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
//table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算
this.threshold = tableSizeFor(initialCapacity);
}
4个构造。都给负载因子赋值。1.默认构造，默认负载因子赋值。2.可以传入容器大小和负载因子大小，并没有给容器赋值，通过两值计算出扩容阈值大小。3.HashMap(Map<? extends K, ? extends V> m) 使用默认的负载因子，调用putMapEntries，判断当前容器是否为空，为空：通过m重新计算当前阈值，不为空：判断m长度是否大于当前阈值，超过就扩容，最后都会遍历m调用putval()放入元素；
阈值计算：除了默认构造函数（第一次调用put方法时计算出阈值），其余4个构造函数都计算出了阈值大小。
tableSizeFor()找到大于或等于 cap 的最小2的幂
/**
* 把输入值cap 变成最小的2的n次幂
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
在构造HashMap时tableSizeFor()方法相对重要，它是保证HashMap的容量始终是2的整数次幂的关键。这个方法用于找到大于等于initialCapacity(假设是10,那么返回的是16)的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）。
下面分析这个算法：
首先，为什么要对cap做减1操作。int n = cap - 1;
这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是 1（最后有个(n < 0) ? 1的操作）。
这里只讨论n不等于0的情况。|（按位或运算）运算规则：相同的二进制数位上，都是0的时候，结果为0，否则为1。
如何添加元素
put()方法解析
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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
* @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) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
// 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//定位数组下标,如果不包含键值对节点引用，则将新键值对节点的引用存入桶中
//这里就是我们平时所说的hash冲突，如果冲突就会对比hashcode()和equals()
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e;
K k;
// 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
//在这里，也就是常常被问道的面试题，为什么要重写对象的hashcode()和equals()，不重写这里就当成了一个对象
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) //key不同；判断p是否为红黑树结点
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else { // else 如果key不相同，只是hash冲突，并且不是树，则是链表
// 循环，直到链表中的某个节点为null，或者某个节点hash值和给定的hash值一致且key也相同，则停止循环。
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
// 如果此链表长度超过8那么调用treeifyBin（），此方法会判断当前容器大小是否达到了形成红黑树的
//值（即 tab.length >= MIN_TREEIFY_CAPACITY） 未达到则继续扩容（一般会扩容两次就会达到）
treeifyBin(tab, hash);
break;
}
//next的hash值和hash相同(key也相同)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//结束循环
break;
// 如果给定的hash值不同或者key不同。
// 将next 值赋给 p，为下次循环做铺垫
p = e;
}
}
//如果e不等于null(表明该元素存在且他们的key相同)
if (e != null) { // existing mapping for key
//取出旧值
V oldValue = e.value;
//onlyIfAbsent如果为true同时 oldValue不等于null 则不覆盖现有值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//如果e== null，需要增加 modeCount 变量，为迭代器服务。
++modCount;
// 存放元素的个数大于临界值(容量*填充因子) 进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal 方法主要做了这么几件事情：
- 当桶数组 table 为空时，resize()初始化 table
- 查找要插入的键值对是否已经存在，onlyIfAbsent如果为false且oldValue等于null 则覆盖旧值
- 如果不存在，则将键值对链入链表中,如果链表长度达到了8，且数组长度小于64，那么就重新散列，如果大于64，则创建红黑树
- 判断键值对数量是否大于阈值，大于的话则进行扩容操作
- 判断容器是否为空，为空则调用resize()扩容。此时是阈值和容器第一次被赋值.根据容器长度-1 和当前元素的hash值计算出当前容器下标是否为null （平时我们所说的hash冲突） ，为null则放入，不为null（hash冲突）则比较当前下标元素和当前元素 hash值和equals（） 是否都相等，如果都相等则覆盖掉value，
不相等，判断当前下标元素是否是红黑树或者链表。- 链表：遍历链表直到最后一个元素并将当前元素挂在此链表下，如果此链表长度超过8那么调用treeifyBin（），此方法会判断当前容器大小是否达到了形成红黑树的值（即 tab.length >= MIN_TREEIFY_CAPACITY） 未达到则继续扩容（一般会扩容两次），达到则拿出链表中的每个元素创建新的TreeNode先是形成双向链表(红黑树)，
- 继续调用treeify（），该方法中，遍历该链表，将第一个元素设为树的根节点，接着拿到每个节点下一个元素与父元素比较hash大小计算出变量dir的大小，如果hash一样则继续判断元素是否实现了comparable接口，实现则用comparable比较，如果没有实现或者还是不能比较出大小，那么最后调用tieBreakOrder（）（此方法中调用了System.identityHashCode（）根据内存中的地址值计算出的hash）计算出两k值的大小（也就是dir的值）如果dir为 -1或0则把当前元素放在父元素的左孩子，为1则是右孩子，如果父元素已经存在左孩子或者右孩子那么将元素放在左或右孩子的下面，如果还是有则继续无边界的循环，直至找到左或右孩子为空时放下，每次放下一个左或者右孩子时都会调用balanceInsertion（）重新平衡红黑树，当遍历完所有元素此时已经形成了红黑树并且保留了链表结构，调用moveRootToFront（）将根节点放在链表的头部，最后断言树是否正常。。形成红黑树。树：则调用putTreeVal（）。
扩容：resize()方法解析
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
//旧的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 临界值
int oldThr = threshold;
int newCap, newThr = 0;
//如果老的容量大于0
if (oldCap > 0) {
//如果老的容量大于最大值
if (oldCap >= MAXIMUM_CAPACITY) {
//阈值设置未最大值
threshold = Integer.MAX_VALUE;
//反追老值
return oldTab;
// oldCap << 1 左移1位 相当于*2
//老的容量*2 小于最大容量并且老的容量大于等于默认容量
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的阀值也再老的阀值基础上*2
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
//初始容量设为阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 0初始阈值表示使用默认的容量16和默认的阀值12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阀值是0，重新计算阀值
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//新的阈值
threshold = newThr;
//创建新的哈希表
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
//判断旧数组是否等于空
if (oldTab != null) {//原来有值则复制到新Node数组里
// 把每个bucket都移动到新的buckets中
//遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
//原来的数据赋值为null 便于GC回收
oldTab[j] = null;
//如果数组当前位置只有一个元素
if (e.next == null)
//没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入
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;
//判断如果等于true e这个节点在resize之后不需要移动位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
//原索引+oldCap (e.hash & oldCap) !=0 最高位对位为1
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
//e.next不等于null 将e.next值赋给e，为下次循环做铺垫
} while ((e = next) != null);
// 原索引放到索引为j的bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到索引为j+oldCap的bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize方法主要做了这么几件事情：
计算新桶数组的容量 newCap 和新阈值 newThr
根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
- 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组
第一步：计算出新的容器大小和阈值。判断当前容器是否为空，如果为空 ，则采用默认的容器大小16，阈值大小 默认负载因子*默认容器大小12=0.75*16， 如果不为空，判断当前容器大小是否达到HashMap设定的最大容器值，达到则将阈值设为Integer.max_value。没有达到则将容器扩容两倍后，新的容器如果小于设定容器最大值并且大于等于默认容器，则阈值扩增2倍，始终判断阈值是否为0，如果为零计算根据容器大小和负载因子计算，考虑容器大小和负载因子是否大于HashMap设定的最大值 第二步；1. 将老容器元素放入新容器，根据新的容器大小创建Node对象赋值给table，遍历老容器，根据老容器的下标判断当前下标元素是否形成链表或形成红黑树，未形成链表或红黑树：那么根据当前元素的hash计算新的容器下标放入。2. 形成链表：根据 if ((e.hash & oldCap) == 0) 做hash计算分成两条链表，节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。3. 形成红黑树：则调用split()方法
这里的TreeNode是Node的子类，表示红黑树的节点，Node表示普通的链表或者数组节点，这也是说为什么hashMap是数组+链表+红黑树的数据结构
红黑树形成及结构
hashmap的核心成员：【 TreeNode 】 继承了LinkedHashMap.Entry treeifyBin()方法 treeify() 树化 ：双向链表转成红黑树 重新平衡红黑树 balanceInsertion(root, x) 为什么要重新平衡树，首先要了解红黑树的5个特点： 根节点只能是黑色 每个叶子节点是黑色的null值。 如果不去平衡树可能会形成线形树，二分查找法就不能提高效率就失去了树的意义， 方法解读： 该方法传入了根节点和插入的节点，第一步是将新插入节点设为红色，判断是否有父节点没有则是root节点设为黑色直接返回，或者有父节点并且为黑色（不影响树）直接返回root 为什么无序不可重复： 为什么hashmap线程不安全： 为什么hashmap的容量要设置成2的幂次方？ 见链接： 见链接 以下集合可能在我们日常开发过程中不是那么常用，在特定的场景下可能也会用到，就不在一一列举源码，简单分析特性 扩容机制： 遍历方式：5种—> 普通for，增强for，foreach（jdk1.8），itorater，枚举 Vector和ArrayList都是基于动态数组实现，基本相同最大的区别就是： Vector线程安全，绝大多数public方法都是加了synchronized ，扩容机制小区别 HashSet的底层实际上是调用HashMap，用key存储hashset的值，value是定义的一个空bject对象，固定值起到占位的作用。add，remove，iterator，也都是调用HashMap的方法 特点：主要和hashmap作比较，线程安全，不能存放null。 实现方式：数组+单向链表 构造方式：4个构造： 核心成员 ： Entry 实现 Map.Entry 与hashmap的核心成员相同 put方法： rehash() 扩容方法： get(): 成员Enumerator ： 与hashmap区别： 为什么hashtable线程安全： 结构：继承hashmap，实现map 特点： 能够保证元素的访问顺序，线程不安全，基于LRU实习的顺序访问。有两种顺序，accessOrder为false（默认）表示插入顺序，为true则为访问顺序 。LinkedHashMap是对Hashmap功能的扩展，采用了双向链表保证元素的访问顺序，用成员accessOrder 来区别采用哪种访问顺序 插入访问：默认访问顺序，即按照元素插入顺序读取 hashmap有的特点，它都有。 成员：仅仅三个成员变量，head（双向链表的头），tail（尾），accessOrder（决定哪种迭代顺序） 构造方法：5种构造都调用父类构造（HashMap）： 空参构造，指定容器值构造，指定容器值和负载因子值构造，参数为map实现类构造。这四种构造都默认调用了父类（hashmap）的对应的构造方法传递参数不做其他处理，仅仅将accessOrder设为false（即默认的插入顺序）。另外一种可以指定容器，负载因子，访问顺序。 核心成员：Entry 继承自hashmap.Node 。 唯二的两个成员 EntryK linkedHahsmap存放元素： get（）方法读取元素： 删除元素： 遍历方式： 从遍历方式中，我们可以知道linkedhashmap怎么保证顺序的 LinkedHashIterator 公共的抽象父类 核心迭代器 通过new子类对象的方式调用父类构造器给父类元素赋值 当我们开始遍历集合时就会创建取迭代器，在创建迭代器的同时将成员head（双向链表的头）作为当前元素，每次调用next()的时候都会沿着双向链表的头部开始向下遍历，所以我们迭代出来的元素是能保证顺序的， 在此需要我们注意的是：如果集合为访问顺序，那么我们在调用读取元素的方法时，如get(),getOrDefault()等，会将读取到的元素放在双向链表的尾部，此时modcount++ ，但是迭代器在迭代时不允许modcount改变，此时便会抛出ConcurrentModificationException异常，所以在linkedhasmap中，如果顺序为访问顺序，那么不要读取元素 到这里我们会发现linkedHahsmap并没有做太多的实现，其核心都是借助父类hashmap实现的，所以说他是对hashmao的扩展，存储元素的方式和hashmap一致（数组+单向链表+红黑树），同时采用双向链表保证元素的前后顺序（这条链表采用尾插法） Java中集合的实现方式大同小异，只需要弄清楚其中两三个重点集合的源码，再看其他的集合就相当简单。都是在固定的框架上加一些额外的功能，也不得不佩服这些大佬的编码能力，有很强的扩展性。/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
替换指定哈希表的索引处桶中的所有链接节点，除非表太小，否则将修改大小。
Node<K,V>[] tab = tab 数组名
int hash = hash表示哈希值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//长度大于64才会树化，如果小于 64只会进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//只是扩容tab[]
else if ((e = tab[index = (n - 1) & hash]) != null) {
/*
1）执行到这里说明哈希表中的数组长度大于阈值64，开始进行树形化
2）e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e
*/
//hd：红黑树的头结点head tl :红黑树的尾结点tail
TreeNode<K,V> hd = null, tl = null;
do {
//把链表的当前结点转成一个树结点。
TreeNode<K,V> p = replacementTreeNode(e, null);//如何转成红黑树：首先根据原来Node结点的顺序转成一个双向链表，即增加一个pre指针，然后再根据这个双向链表从上到下依次插入到一颗红黑树中，转成一棵树
if (tl == null)
//将新创键的p节点赋值给红黑树的头结点
hd = p;
else {
p.prev = tl;//将上一个节点p赋值给现在的p的前一个节点
tl.next = p;//将现在节点p作为树的尾结点的下一个节点
}
tl = p;
} while ((e = e.next) != null);//更新结点 且 判断是否继续查找
/*
让桶中的第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树
而不是链表数据结构了
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);//在这里把双线链表转成红黑树
}
}
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {//第一个结点直接作为红黑树根节点
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;//key的class类型
for (TreeNode<K,V> p = root;;) {//遍历现有红黑树
int dir, ph;
K pk = p.key;//p是红黑树里的当前结点，x是我们要插入的结点
//要插入得先比较，但先比较的是哈希值，
if ((ph = p.hash) > h)//如果红黑树里当前结点p的哈希值大于要插入的结点x哈希值
dir = -1;//direction，往左子树查
else if (ph < h)//p的哈希值小于x的哈希值
dir = 1;//往右子树查
//等于
else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
//如果kc为空就先赋值kc//如果该key实现了Comparable<C>可进行比较，就返回Class对象。没实现就返回null //这里应该这是插入根节点的时候或的前半部分才为true，从第二个开始或语句的前半句就不满足了，直接执行或的后半句
(dir = compareComparables(kc, k, pk)) == 0)//前面只是比较哈希值，哈希值相对未必就key相等，所以进一步比较p的key和x的key，并且把结果给dir
//如果上面的dir==0满足，就进行插入，否则继续进行再查找
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {//看向左还是向右查找，更新红黑树的当前结点 //如果进入if，代表没有x对应的这个key值，要进行插入了
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;//先连接上，再调整
root = balanceInsertion(root, x);//当前结点插入到红黑树中
break;
}
}
}
}
moveRootToFront(tab, root);//把根节点赋值给HashMap的table[i]//树结点同时也是以链表形式存在的
//红黑树生成的过程中只是改变了left和right，而原来的next和prev还在，所以还是可以拿双线链表查出来原来后红黑树前的顺序的。我们的结点同时是链表里的一个结点，同时也是红黑树里的一个节点。
//但这里还是做了一些变化的，他让红黑树里根节点那个结点移动到了双向链表的头部，即单独单出来放到头部，其他结点再双向链表中的相对顺序不变，包括因拿出来根节点断掉的那个地方，也自动粘合拼接了。
}
真正的形成红黑树的方法，该方法为核心成员TreeNode中的方法。
通过实例对象调用treeify()，将实例对象（即双向链表的表头）设为根节点，颜色染黑。遍历双向链表依次拿到下一个节点next（即当前节点），通过比较当前节点和父节点的hash值大小来判断当前节点放在 左节点(dir小于等于) 还是右节点。
如果通过key的值和hash值都不能比较出来两者大小，那么判断当前节点的key是否实现comparable接口并且两者的class相同，相同则通过comparable比较出两者的dir，如果还是不行则最后通过tieBreakOrder()再比较一次，直到得出dir的值
当计算出dir的值便确定了当前节点为父节点的左还是右孩子，如果父节点存在了左右孩子，那么继续向下寻找，在无边界的循环中遍历树的分叉，直至找到正确的末梢并存放该节点
该方法中两层循环嵌套：外层遍历双向链表，内层遍历树的分叉，为了找到外层循环中当前节点存放在树的位置。每次存放完节点都会调用balanceInsertion()方法重写平衡红黑树
该方法结束之前调用moveRootToFront(): 因为每次插入新节点都会调整红黑树，所以根节点可能已经不在桶table[i]的第一个位置。那么砍断root的前后元素的引用，将root提出来并将前后元素相连，将桶的第一个元素放在root后面，此时root便是桶中第一个元素table[i]
获取方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 定位键值对所在桶（数组）的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 2. 如果是红黑树，调用树查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 3. 查找链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
特性分析
根实现方式有关，基于数组加链表实现，每次存放和读取元素都是以key的hash值计算出元素所在数组中的位置，再根据key的equal方法比较key的是否相同，来取出或覆盖元素
foreach在两层循环之后检查modcount的值是否改变，迭代器是nextNode()方法中检查
TreeMap源码解析
ConCurrentHashMap源码解析
不常用集合
集合Vector特性
集合HashSet特性
集合TreeSet特性
集合Hashtable特性
集合LinkedHashMap特性
顺序访问：最近使用的排在最后位置，即读取顺序为最不常用的到最常用的。LinkedHashMap实现的LRU（末位淘汰）算法。先访问的迭代的时候放在最后面
1.还是调用hashmap取元素方法：如果集合为访问顺序，那么则将当前读取到的元素放在双向链表的最后面
1.同样调用hashmap的removeNode方法，对afterNodeRemoval（）方法重写，重写此方法是为双向链表中剔除元素
总结
