集合浅原理篇

​ 集合的概念：对象的容器，定义了对多个对象进行操作的常用方法。可实现数组的功能。
和数组的区别：

1. 数组长度固定，集合长度不固定。
2. 数组可以存储基本数据类型、引用数据类型，集合只能存储引用数据类型。所以看到的 Map都是 Map<Integer,Integer>，而不是 Map<int,int> 。
3. 相比于集合，数组没有删除方法，开辟连续空间。

Collection体系下两个接口

List接口

List 特点：有序、有下标、元素可重复。
List 实现类： ArrayList、LinkedList、Vector。

1. ArrayList：是一个古老的实现类，底层是 Object[] ，vector 底层也是一样，线程不安全，容量是动态的、但是牺牲效率，DEFAULT_CAPACITY = 10; 默认容量为10；若未添加元素，容量 0；扩容每次是原来的1.5倍，下文详解。ArrayList.add() 不带索引则默认从 0 开始。
2. Vector、ArrayList：都是数组结构实现，但是 Vector 是线程安全的，ArrayList 线程不安全，而 LinkedList 是链表结构实现。笼统来说，ArrayList 查询快、插入慢， LinkedList 查询慢、插入快，因为 ArrayList 要把插入位后面的值全都后移一位，但是有特殊情况，下文详解。
3. LinkedList ：存储结构为双向链表。 无需开辟连续空间，查询慢，增删快。具体下文再比较效率 。

• 注意：ArrayList 是并发不安全的，vector 是线程安全的。
  解决 ArrayList 线程安全问题的方法有：Collections.synchronizedList、CopyOnWriteArrayList。

ArrayList、LinkedList 比较

ArrayList 底层基于数组实现，LinkedList 底层基于链表实现，确切的说是循环双向链表（JDK 1.7 之前是双向循环链表、JDK 1.7 开始取消了循环），LinkedList 链表由一系列表项连接而成， 一个表项包含 3 个部分：元素内容、前驱表、后驱表。LinkedList 链表内部还有一个 header 表项，既是链表的开始也是链表的结尾。header 的后继表项是链表中的第一个元素，header 的前驱表项是链表中的最后一个元素。
ArrayList 的增删未必比 LinkedList 慢：
1. 如果增删都是在末尾来操作【每次调用的都是 remove() 和 add()】，此时 ArrayList 就不需要移动和复制数组来进行操作了。 数据量达到百万级的时，速度是会比 LinkedList 要快的。
2. 删除操作的位置是在中间。由于 LinkedList 的消耗主要是在遍历上， ArrayList 的消耗主要是在移动和复制上（底层调用的是 arrayCopy() 方法，是本地方法）。LinkedList 的遍历速度是要慢于 ArrayList 的复制移动速度， 数据量达到百万级的时，还是 ArrayList 要快。

ArrayList 扩容

起初 empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当使用 add 方法的时候首先调用 ensureCapacityInternal 方法， 源码中的 Capacity 是容量，size 是当前the number of elements it contains（当前包含的元素数）， 传入 size+1 进去，检查是否需要扩充 elementData 数组的大小，再传入值；具体扩容过程如下（不拿 add（） 的重载举例）：

1
2
3
4
5

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

若 add() 第一个元素，则传入 DEFAULT_CAPACITY = 10，默认容量为10，注意很多博主讲到扩容，minCapacity 、newCapacity、oldCapacity、size 名词组合拳就把人整晕了，其实传入的 size+1 就是 ensureCapacityInternal 方法中的 minCapacity。

1
2
3

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

可以看到判断扩容的方法里调用了ensureExplicitCapacity和 calculateCapacity ，方法体如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

calculateCapacity 方法传入 elementData （即当前存 “元素数据引用” 的地址）, minCapacity（即size+1），意思当第一次调用add(E e)方法的时候， 判断是不是无参构造函数创建的对象，如果是， 将 DEFAULT_CAPACITY 即 10 作为 ArrayList 的容量，此时 minCapacity = 1。返回的容量作为ensureExplicitCapacity的参数传入， 此时 modCount++；是fail-fast iterators 相关，先不用管，而 DataElement 是现在用于存储的数组，当 size+1 大于这个值，意味着要扩容了，然后调用grow（）方法扩容 ：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

其中 oldCapacity 是原来的容量大小，oldCapacity » 1 为位运算的右移操作，右移一位相当于除以 2，所以这句代码就等于 int newCapacity = oldCapacity + oldCapacity / 2；
newCapacity = 扩充数组为原来的 1.5 倍(不能自定义)，然后判断 minCapacity 是否大于MAX_ARRAY_SIZE(Integer.MAX_VALUE – 8) ，如果大于数组最大容量，就取 Integer.MAX_VALUE；后回到 grow（）方法，调用 Arrays.copyof 方法， 即复制原数组内容到一个新容量的大数组里。这里Arrays.copyof 方法实际是调用 System.arraycopy方法。
与 Vector 不同的是，Vector 每次扩容容量是翻倍，即为原来的 2倍，而 ArrayList 是 1.5倍。看似 1.5倍增长的很慢，那经常增加大量元素会不会导致经常扩容，数组重新分配导致效率低下呢？ 其实不然，每次增长为原来的 1.5倍实际增长的量会越来越大的。当然，如果一开始知道数据量很大的话，可以在初始化时预先指定容量。

为什么扩容因子是 1.5
因为1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。
为什么不取固定长度
扩容固定容量，很难决定到底取多少值合适，取任何具体值都不太合适，因为所需数据量往往由数组的客户端在具体应用场景决定。

Set接口

Set 特点：无序、无下标、元素不能重复
Set 实现类：HashSet、SortedSet 接口（TreeSet 实现类）

1. TreeSet：基于排列顺序实现元素不重复。实现了 SortedSet 接口，对集合元素自动排序。元素对象的类型必须实现 Comparable 接口，指定排序规则方法的返回值为 0，则认为是重复元素。
2. HashSet：储存结构为哈希表（数组+链表+红黑树）。

• 注意：HashSet 是线程不安全的，解决方法是使用 CopyOnWriteHashSet。

HashSet 存储过程：

1. 根据 hashcode 计算保存的位置，如果此位置为空，则直接保存，如果不为空执行第二步。
2. 再执行 equals 方法，如果 equals 方法为 true ，则认为是重复，否则，形成链表。

HashSet、TreeSet的实现原理:

HashSet 的实现是依赖于 HashMap 的，HashSet 的值都是存储在 HashMap 中的。在 HashSet 的构造法中会初始化一个 HashMap 对象，HashSet 不允许值重复。因此，HashSet 的值是作为 HashMap 的 key 存储在 HashMap 中的，当存储的值已经存在时返回 false。

TreeSet 的实现基于 TreeMap。

Map 集合体系

Map 父接口特点：存储一对一数据，无序、无下标，键不可重复，值可以重复。

HashMap ：存储结构（哈希表：数组+链表+红黑树）允许 null key、value。
HashTable：不允许 null key、value。线程安全。
TreeMap：实现了 SortedMap 接口（Map 的子接口），可以对 key 自动排序。

• 注意：HashMap 是线程不安全的，解决方法是使用 ConcurrentHashMap 。

HashMap底层原理

jdk 1.7 的数据结构是 “ Entry数组+链表 ”，jdk 1.8 的数据结构是 ” Node 数组+链表/红黑树 “。当链表的深度达到 8 并且 HashMap 容量 >= 64 时自动转化成红黑树，节点变成树节点， 以提高搜索效率和插入效率到 O(logN)。Entry 和 Node 都包含 key、value、hash、next 属性。
HashMap 默认容量为 16（数组长度），通过 hashcode 查询的时候是要先 ” hashcode % 数组长度 “ 进行运算才能找到数组对应位置下的链表。该数组只存引用的地址，其对象存在堆里。
在 jdk 1.7 时插入元素是头插法，jdk 1.8 时是尾插法，头插法的插入很快（插完要移动一下，让该结点在原来头节点在数组中的槽位），尾插法要遍历再插入（jdk1.8）。
put 时先会判断是否空数组，是空就会先初始化，put 一对 key-value 时，系统会根据 key 的hashcode 来确认其在 “数组” 的存储位置，若没有元素则直接插入，否则会遍历该处的链表并依次比较其 key 的 hashcode，如果两个 key 的 hashcode 相同且 key 值相同，新的 value 会覆盖旧的 value 并返回旧的 value（不覆盖返回的是 NULLl）。如果 hashcode 相同但 key 值不同，则会进行插入操作，并且该链表的 size++。
那么 key 值如何比较呢？ equals 方法。这里涉及 哈希碰撞：
输入数据长度不固定，而输出的哈希值却是固定长度的，这意味着哈希值是一个有限集合，而输入数据则可以是无穷多个，那么建立一对一关系明显是不现实的。所以“碰撞”是必然会发生的。
HashMap 解决 hash冲突用的是拉链法，就是在对应的数组元素存链表头节点。还有开放寻址法、再哈希法，开放寻址是往数组索引++找空位置，再hash法就是再次用其他hash方法得到hashcode。 那既然 equals 方法这么有效，为什么还要用 hashcode ？
因为 hashcode 快！
如果现在有大量的对象需要比较，每个都用 equals() 效率是很低的，但 hashCode() 效率很高。
所以有这种设计：先用 hashCode() 判断，如果 hashCode() 不同，则对象不等，如果 hashCode() 相同，再比较 equals() ，大大提高了效率。

key 可以等于 null，源码对 Entry 的两个约束：

1. 数组每个槽位下都不为空。
2. 所有结点平均分布在每一个槽位下的链表。

也正因如此，HashMap 的长度必须为 2 的次幂。讲到长度，就跑不掉 HashMap扩容了：

HashMap 扩容条件

HashMap 扩容的加载因子默认为 0.75 ，阈值为 ” 0.75 * 数组长度 “，意思是每当 ”HashMap当前元素数“ 到达 ”当前容量 * 0.75“ 时 且 “插入位置不为 NULL” 就判断是否符合 “ 数组长度是否最大 ”。最大就不扩容，否则就是扩容到原容量的 2倍。

0.75的负载因子的意义
通常，默认负载因子（0.75）在时间和空间成本之间提供了一个很好的折中方案，负载因子控制存放数据的疏密程度。
较高的值会减少空间开销，但会增加查找成本（在HashMap类的大多数操作中都得到体现，包括get和put），而且容易引发哈希冲突。
16 * 0.75 = 12 除0.5与1以外唯一一个能得到整数的负载因子就是0.75。
负载因子的大小决定了HashMap的数据密度，因子越大，越容易发生发生哈希碰撞，数组中的链表越容易长，造成查询或插入时比较次数增多，性能会下降。
越小就越容易触发扩容，既影响性能又浪费空间。

HashMap 扩容原理

new 一个两倍长度的 Entry/Node 数组，然后内容转移新的数组，扩容后链表会倒序。因此，多线程同时 put（）时，如果同时触发了 rehash（） 操作会导致 HashMap 中的链表中出现循环节点，进而使得后面 get（） 的时候，会死循环。
另外，扩容之后链表可能减短，提高 get（） 时的效率。

为什么HashMap扩容每次是2倍

1. 找到 hash索引的方式是hashcode%length 取模操作，但设计得到 hash索引的 hash函数是：hashcode无符号右移16位再异或hashcode再按位与（length-1），为什么这么做?
   因为2进制操作远远快于取模，length 为 2次幂时，又恰好 (length - 1) & hash ≈ hash % length。而且我们可以看到它求hash的过程，将32位的hashCode值向右移动16位，高位补0，也就是只要了高16位，这是为什么呢？
   因为hashcode的计算方法导致哈希值的差异主要在高位，而 (n - 1) & hash是忽略了容量以上的高位的，所以 使用h »>16就是为了避免类似情况的哈希冲突
2. 在扩容迁移的时候不需要再重新通过哈希定位新的位置了。扩容后，元素新的位置，要么在原脚标位，要么在原脚标位+扩容长度这么一个位置.是否移位，由扩容后表示的最高位是否1为所决定，由于移动的方向只有一个，即向高位移动。 因此，可以根据对最高位进行检测的结果来决定是否移位，从而可以优化性能，不用每一个元素都进行移位，因为为0说明刚好在移位完之后的位置，为1说明需要移动 oldCap.

哈希表底层怎样计算hash值

1. Object的hashcode方法算出h1。
2. h1无符号右移16位得到h2。
3. h1与h2异或运算得到最终的hash值h3。
4. h3与（length-1）按位与（&）运算得到hash表索引。 hashmap理论上是用取模得出在哪个hash桶，但是位运算会更快，在hashmap容量为2次幂时，取模结果会近似于以上四个步骤的结果。

HashMap死循环、ConcurrentHashMap

HashMap
在 JDK1.7 是采用的头插法，所以扩容过程转移到新的 HashMap 会逆置链表顺序，而当在并发环境下两个线程同时插入会导致死循环，原因就是顺序 A-B-C 变成了 C-B-A ，一个线程扩容完了之后另一个线程并不知道，因为此时两个线程都指向该槽位第一个节点， next 都是指向 B，而非扩容的线程的 B.next 还是 C，没有察觉到变化。在 JDK1.8 HashMap 采用的尾插法很好的规避了这个问题。

ConcurrentHashMap
在 JDK1.7 下，ConcurrentHashMap 采用的是 segment 锁分段解决的并发问题，相比较 HashTable 降低了锁粒度。
在 JDK1.8 下，ConcurrentHashMap 采用的是 CAS + synchronized + LockSupport 等阻塞手段实现的高效并发，和 JDK1.7 最大的区别在于 JDK1.8 的锁粒度更细，理想情况下 table 数组元素的大小就是其支持并发的最大个数，在 JDK7 里面最大并发 个数就是Segment的个数，默认值是16，可以通过构造函数改变一经创建不可更改，这个值就是并发的粒度，每一个segment下面管理一个table数组，加锁的时候其实锁住的是整个segment，这样设计的好处在于数组的扩容是不会影响其他的segment的， 简化了并发设计，不足之处在于并发的粒度稍粗，所以在 JDK1.8 里面，去掉了分段锁，将锁的级别控制在了更细粒度的table元素级别，也就是说只需要锁住这个链表的head节点，并不会影响其他的 table 元素的读写，好处在于并发的粒度更细， 影响更小，从而并发效率更好，但不足之处在于并发扩容的时候，由于操作的table都是同一个，不像 JDK1.7 中分段控制，所以这里需要等扩容完之后，所有的读写操作才能进行，所以扩容的效率就成为了整个并发的一个瓶颈点，好在Doug lea大神对扩容 做了优化，本来在一个线程扩容的时候，如果影响了其他线程的数据，那么其他的线程的读写操作都应该阻塞，但Doug lea说你们闲着也是闲着，不如来一起参与扩容任务，这样人多力量大，办完事你们该干啥干啥，别浪费时间，于是在 JDK1.8 的源码 里面就引入了一个 ForwardingNode 类，在一个线程发起扩容的时候，就会改变 sizeCtl 这个值。

1. 对于get读操作，如果当前节点有数据，还没迁移完成，此时不影响读，能够正常进行。
   如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时get线程会帮助扩容。

2. 对于put/remove写操作，如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时写线程会帮助扩容，如果扩容没有完成，当前链表的头节点会被锁住，所以写线程会被阻塞，直到扩容完成。

HashTable 和 HashMap 的区别

1. HashTable 不允许 key 和 value 为 null；HashMap 遇到 key 为 null 的时候，调用 putForNullKey（）进行处理，而对 value 没有处理；Hashtable 遇到 null，直接返回 NullPointerException。
2. HashTable 线程安全，但是 HashTable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只 能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

ConcurrentHashMap 实现原理

JDK 1.7 中的实现：
就是对HashMap加上个分段式锁，put和HashMap类似，先通过hashCode找到位置如果该处为null就new一个segment对象，segment 对象中有个 hashEntry 构成的链表，而每个 HashEntry 元素都是一个链表结构的节点，HashEntry 和 HashMap 非常类似，唯一的区别就是其中的核心数据 value 以及 next 都被 volatile 修饰，以此保证了多线程读写过程中对应变量的可见性。
HashMap 不是线程安全的，而 ConcurrentHashMap 是线程安全的。ConcurrentHashMap 采用锁分段技术，将整个Hash桶进行了分段segment ，也就是将这个大的数组分成了几个小的片段 segment，而且每个小的片段 segment 上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段 segment，然后再在这个片段上面进行插入，而且这里还需要获取 segment 锁，这样做明显减小了锁的粒度.比HashTable效率高。
put过程：先根据 key 找到 segment 中对应的 HashEntry，遍历该 HashEntry ，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等就覆盖旧的 value，为空则需要新建一个 HashEntry 并加入到 segment 中，在加入之前会先判断是否需要扩容，最后解除 segment 锁。

JDK 1.8 中的实现：
将 JDK 1.7 中存放数据的 HashEntry 改为了 Node JDK 1.8 的 ConcurrentHashMap 取消了 Segment 分段锁，采取 CAS 和 synchronized 来保证并发的安全性。synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发问题。

ConcurrentMap的put过程
首先，根据传入的key，通过哈希函数确定key应该被放置在哪个段（Segment）中。 然后，获取该段的锁，保证在该段中进行操作时是线程安全的。 在获取到段的锁之后，检查是否需要进行扩容操作，如果需要，则进行扩容。扩容过程会重新计算每个元素的哈希值，重新分配到新的段中。 接着，在当前段中，查找是否已经存在相同的key。如果存在相同的key，则用新的value替换旧的value，并返回旧的value。 如果当前段中不存在相同的key，则将key-value对插入到当前段中。 最后，释放段的锁。

ConcurrentMap扩容
是挨个把所有 segment 扩容，而不是整个 hashMap。所以扩容期间不耽误其它 segment 的 put、get。

Hashtable 扩容时将容量翻倍，而 ConcurrentHashMap 扩容时将只扩大一个 Segment，这样可以减少扩容时的并发冲突，提高性能。

LinkedHashMap实现原理：
LinkedHashMap 也是基于 HashMap 实现的，不同的是它定义了一个 Entry header，这个 header 不是放在 Table 里，它是额外独立出来的。LinkedHashMap 通过继承 hashMap 中的 Entry，并添加两个属性 Entry<K,V> before，Entry<K,V> after 和 header 结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。

迭代

Iterator 可用来遍历 Set 和 List 集合，但是 ListIterator 只能用来遍历 List。Iterator 对集合只能是前向遍历，ListIterator 可以双向遍历。ListIterator 实现了 Iterator 接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引等等。
与 Enumeration 相比，Iterator 更加安全，因为当一个集合正在被遍历的时候，它会阻止其它线程去修改集合。否则会抛出 ConcurrentModificationException 异常。这其实就是 fail-fast 机制。具体区别有三点：

1. Iterator 的方法名比 Enumeration 更科学；
2. Iterator 有 fail-fast 机制，比 Enumeration 更安全；
3. Iterator 能够删除元素，Enumeration 并不能删除元素。

持续更新中…… 如有错误，敬请斧正…..