主要是Java常用集合介绍

0. 概述

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。

在 java.util 包中的线程安全的类主要 2 个，其他都是非线程安全的。

Vector
Hashtable

此外，java.util.concurrent 包提供的都是线程安全的集合：

1.List

1.ArrayList和LinkedList的区别

底层数据结构：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
操作效率不同：多数情况下，ArrayList更利于查找，LinkedList更利于增删，LinkedList只有在首尾的增删效率是O(1)，如果是中间的元素也是O(n)
占用空间：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
是否支持随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口）支持。

2.ArrayList的扩容机制

ArrayList底层采用的是Object[] 动态数组实现，当我们向ArrayList中添加元素时，它会自动调整数组的大小以适应新的元素。当数组的容量不足以容纳新元素时，ArrayList会创建一个更大的数组，并将原数组中的元素复制到新数组中。

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。

ArrayList的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

扩容完成后更新引用到新的数组上

之所以扩容是 1.5 倍，是因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

核心源码：

1
2
3

transient Object[] elementData; // 实际存储元素的数组
private int size; // 当前元素数量（非数组长度）
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 关键扩容检查
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 并发修改标记
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); // 真正扩容
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity); // 数据拷贝
}

3. 为什么ArrayList不是线程安全的

在高并发添加数据下，ArrayList会暴露三个问题; （主要理解前两个即可）

部分值为null（我们并没有add null进去）
索引越界异常
size与我们add的数量不符

如何产生的：

部分值为null：当线程1走到了扩容那里发现当前size是9，而数组容量是10，所以不用扩容，这时候cpu让出执行权，线程2也进来了，发现size是9，而数组容量是10，所以不用扩容，这时候线程1继续执行，将数组下标索引为9的位置set值了，还没有来得及执行size++，这时候线程2也来执行了，又把数组下标索引为9的位置set了一遍，这时候两个先后进行size++，导致下标索引10的地方就为null了。
索引越界异常：线程1走到扩容那里发现当前size是9，数组容量是10不用扩容，cpu让出执行权，线程2也发现不用扩容，这时候数组的容量就是10，而线程1set完之后size++，这时候线程2再进来size就是10，数组的大小只有10，而你要设置下标索引为10的就会越界(数组的下标索引从0开始);
size与我们add的数量不符：这个基本上每次都会发生，这个理解起来也很简单，因为size++本身就不是原子操作，可以分为三步:获取size的值，将size的值加1，将新的size值覆盖掉原来的，线程1和线程2拿到一样的size值加完了同时覆盖，就会导致一次没有加上，所以肯定不会与我们add的数量保持一致的;

4.CopyOnWriteArrayList为什么线程安全

CopyOnWriteArrayList就是线程安全版本的ArrayList。它可以保证读读不互斥、读写不互斥、只有写写互斥

CopyOnWriteArrayList底层也是通过一个数组保存数据，使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到。

add方法内部用到了 ReentrantLock 加锁，保证了同步，避免了多线程写的时候会复制出多个副本出来。

CopyOnWriteArrayList采用了一种读写分离的并发策略。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

5.Copy-On-Write思想

这个是一种思想，在Redis的RDB持久化那里也用到了这种技术——来应对在持久化的过程中数据发生了改变。

维基百科对 Copy-On-Write 的介绍，介绍的挺不错：

写入时复制（英语：Copy-on-write，简称 COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源

这里再以 CopyOnWriteArrayList为例介绍：当需要修改（ add，set、remove 等操作） CopyOnWriteArrayList 的内容时，不会直接修改原数组，而是会先创建底层数组的副本，对副本数组进行修改，修改完之后再将修改后的数组赋值回去，这样就可以保证写操作不会影响读操作了。

可以看出，写时复制机制非常适合读多写少的并发场景，能够极大地提高系统的并发性能。

不过，写时复制机制并不是银弹，其依然存在一些缺点，下面列举几点：

内存占用：每次写操作都需要复制一份原始数据，会占用额外的内存空间，在数据量比较大的情况下，可能会导致内存资源不足。
写操作开销：每一次写操作都需要复制一份原始数据，然后再进行修改和替换，所以写操作的开销相对较大，在写入比较频繁的场景下，性能可能会受到影响。
数据一致性问题：修改操作不会立即反映到最终结果中，还需要等待复制完成，这可能会导致一定的数据一致性问题。

2.Set

1.List和Set的区别？

List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。 List 支持for循环，也就是通过下标来遍历，也可以用迭代器
Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。set只能用迭代器，因为他无序，无法用下标来取得想要的值。

2.HashSet怎么判断有没有重复的值的

HashSet 是由 HashMap 实现的，只不过值由一个固定的 Object 对象填充，而键用于操作。

HashSet：无序，底层基于哈希表

TreeSet：有序，底层基于红黑树

LinkedHashSet：有序，底层基于链表（双向）和哈希表

3.Map

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个

1.HashMap怎么处理Hash冲突

链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
再哈希法(Rehashing)：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空位来存储键值对。

2.HasMap的底层数据结构及实现原理

数组（Node[] table）用来存储键值对。数组中的每个元素被称为“桶”（Bucket）

计算每个桶的索引流程：通过 key 的 hashcode() 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash得到实际索引。详见5.hashmap的寻址算法

扰动函数hash() 的目标是尽量减少哈希冲突，保证元素能够均匀地分布在数组的每个位置上。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的放入链表或红黑树中

不过，链表过长时，查询效率会比较低，于是当链表的长度超过 8 时（且数组的长度大于 64），链表就会转换为红黑树。红黑树的查询效率是 **O(logn)**，比链表的 O(n) 要快。如果仅仅只是链表长度超过8，但数组长度并没有>=64，那么仅仅对数组进行扩容。

当从 HashMap 中读取元素时，也会使用 hash() 计算键的位置【HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度）】，然后根据位置在数组查找元素。

HashMap 的初始容量是 16，随着元素的不断添加，HashMap 的容量可能不足，于是就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。

3.HashMap的put流程

根据key的哈希码计算它要插入的索引
判断数组是否为空或者长度为0，如果是则进行扩容操作。
否则就判断该索引处是否为空，如果为空就直接插入
如果不为空，判断key是否相同，如果相同直接覆盖value
否则，判断是否为树节点，如果是树节点就直接插入红黑树
否则，说明就是链表，遍历链表是否存在key，如果存在就覆盖，否则就插入链表，同时还要注意链表长度，超过8且数组长度超过64就将链表转为红黑树
插入成功后，判断此时数组键值对数量是否超过了阈值threshold(数组长度*0.75【负载因子】)，如果超过，进行扩容

4.HashMap的扩容机制

第1步是对哈希表长度的扩展（2倍）
第2步是将旧哈希表中的数据放到新的哈希表中。

因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成 “原索引+旧容量（oldCapacity）” 。既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，可以均匀的把之前的冲突的节点分散到新的bucket了

为什么负载因子设为0.75？

答：这是从时间成本和空间成本综合考虑的结果

负载因子决定元素个数达到多少时候扩容

如果设的太大，等要扩容的时候基本没多少空位了，发生哈希冲突的概率非常大，会增加我们查找的时间成本

如果设的太小，有点浪费，我们就需要更多的空间去存储元素，增加了空间成本

5.HashMap的寻址算法

1.获取键的哈希码

当你向HashMap中插入一个键值对时，首先会计算键（key）的哈希值。哈希值是通过键的hashCode()方法得到的。hashCode()是Java中Object类提供的一个方法，返回一个32位的整数，表示对象的哈希码。如果键是null，则哈希值直接返回0。

2.扰动处理

单纯使用hashCode()得到的哈希值可能会导致分布不均匀，尤其当HashMap的容量较小时。为了解决这个问题，HashMap会对原始的hashCode()进行一次扰动处理。具体实现是在hash()方法中完成的，代码如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里，h是键的hashCode()。
h >>> 16表示将h无符号右移16位，提取高16位。
然后通过h ^ (h >>> 16)进行异或操作，将高16位和低16位混合。
这样做的目的是让哈希值分布更均匀，避免冲突。

简单说，为啥需要扰动处理呢？因为索引的计算公式是（n - 1）& hash，如果hash仅在低位有变化，容易产生哈希冲突

3.计算索引

在扰动处理后，得到的哈希值需要映射到HashMap的数组索引上。 index = (n - 1) & hash

6.HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标

哈希值与数组大小范围不匹配；hashCode()方法返回的是int整数类型，int 的范围是 -2147483648~2147483647，加起来大概 40 亿上下的浮动。范围远超HashMap的容量范围
解决方法：

HashMap 的长度（容量capacity）为什么是2的幂次方？（TODO 了解）

不用重新计算hash，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+旧容量（oldCapacity）”，省去了重新计算hash值的时间
由于新增的1bit是0还是1可以认为是随机的，可以均匀的把之前的冲突的节点分散到新的bucket了

7.HashMap在多线程下可能会出现的问题

问题：在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。
解决：为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题，多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。并发环境下，推荐使用concurrentHashMap

8.ConcurrentHashMap的底层原理

jdk1.7

底层数据结构：数组＋链表。一个ConcurrentHashMap有一个Segment的数组，每个Segment又有一个HashEntry数组，然后每个HashEntry又是一个链表结构的，HashEntry 则用于存储键值对数据。Segment（分段锁）是一种可重入的锁 ReentrantLock

将数据分段，对每个Segment分配一把锁。当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

同一Segment可以并发读，不能并发写，可以有一个写其它的读；不同Segment可以并发读写，前提是获得锁

这里是Javaguide那里的一个图示，我觉得更好理解一点

每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

get：

通过 hash(key) 定位到 segment
再遍历链表定位到具体的元素上。

需要注意的是 value 是 volatile 的，所以 get 是不需要加锁的。

put：

计算 hash，定位到 segment，segment 如果是空就先初始化；
使用 ReentrantLock 加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定能获取到锁；
遍历 HashEntry，key 相同就直接替换，不存在就插入。
释放锁。

jdk1.8

和1.7的变化：

数据结构改为Node节点数组+链表+红黑树，Node存储键值对
和Hash Map一样，链表长度达到8的时候会转化成红黑树
放弃了Segment分段锁来保证安全，改为使用volatile + CAS 或者 synchronized 只对（链表或红黑树的）头节点来加锁，从而实现的线程安全的。

再贴一个Javaguide的图示

可以发现 Java8 的 ConcurrentHashMap 相对于 Java7 来说变化比较大，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树。

get：

通过计算哈希值快速定位桶，在桶中查找目标节点，多个 key 值时链表遍历和红黑树查找。读操作是无锁的，依赖 volatile 保证线程可见性。

put流程：

根据存储的元素计算该位置是否为空。
如果根据存储的元素计算结果为空，则利用 CAS 设置该节点，写入数据；
如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树

总的来说，相比前代，舍弃了Segment分段锁臃肿的设计，改为只用锁头节点的方式，锁粒度更细，发生冲突和加锁的频率降低，提高并发性能。另一方面，链表转为红黑树的操作也会使增加查找效率

9.HashTable的底层原理

Hashtable的底层数据结构是数组+链表

HashTable是线程安全的，它采用的是全表锁。它使用 synchronized 来保证线程安全，效率非常低下。

10.ConcurrentHashMap 和 Hashtable 的区别

底层数据结构
- jdk7之前的ConcurrentHashMap底层采用的是分段的数组+链表实现，jdk8之后采用的是数组+链表/红黑树;
- HashTable采用的是数组+链表，数组是主体，链表是解决hash冲突存在的。
实现线程安全的方式
- idk8以前，ConcurrentHashMap采用分段锁，对整个数组进行了分段分割，每一把锁只锁容器里的一部分数据，多线程访问不同数据段里的数据，就不会存在锁竞争，提高了并发访问;idk8以后，直接采用数组+链表/红黑树，并发控制使用CAS和synchronized操作，更加提高了速度。
- HashTable:使用 synchronized 来保证线程安全，效率非常低下，当一个线程访问同步方法另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。