集合概述

常见的集合有哪些？重要

Java 集合类主要由两个接口 Collection 和 Map 派生出来的，Collection 有三个子接口：List、Set、Queue。

List 代表了有序可重复集合，可直接根据元素的索引来访问；
Set 代表无序不可重复集合，只能根据元素本身来访问；
Queue 是队列集合；
Map 代表的是存储 key-value 对的集合，可根据元素的 key 来访问 value。

集合体系中常用的实现类有 ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap 等实现类。

Arraylist 与 LinkedList 区别? 重要

ArrayList 基于 动态数组 实现；LinkedList 基于链表实现。
对于随机 index 访问的 get 和 set 方法，ArrayList 要比 LinkedList 快得多，ArrayList 遍历最大的优势在于 内存的连续性，CPU 的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
- 因为 ArrayList 直接通过数组下标直接找到元素；LinkedList 要移动指针遍历每个元素直到找到为止。
新增和删除元素，LinkedList 的速度要优于 ArrayList。因为 ArrayList 在新增和删除元素时，可能扩容和复制数组 ；LinkedList 实例化对象需要时间外，只需要修改指针即可。

# 为什么数组Arraylist查找时间复杂度是O（1）？

ArrayList是由数组支持的，数组按顺序放在内存中。这意味着，如果它是一个整数数组，每个使用4个字节，并从内存地址1000开始，则下一个元素将是1004。用于元素的确切地址，RAM内存的名称叫随机访问内存。在知道地址的情况下，它可以在恒定的时间里访问任何存储的存储单元。

也就是O（1）；

那就有人问了我的Array List存的是String对象

ArrayList<String> list = new ArrayList<>();

由于String是不定长的，那我如何得到准确位置呢？

对这个问题来说，其实ArrayList存的是String对象的地址，都是8个字节。所以从内存地址1000开始找第三个

1000+（3-1）*8=1016

本质是数组结构，连续存放内存，可以通过物理逻辑地址换算得到，而链表本质是不连续存放的，所以需要一个个找

Arraylist 和 Vector 的区别？ArrayList 的遍历和 LinkedList 遍历性能⽐较如何？

ArrayList 在内存不够时默认是扩展 50% + 1 个，Vector 是默认扩展 1 倍。
Vector 属于线程安全级别的，但是大多数情况下不使用 Vector，因为操作 Vector 效率比较低。

Map 和 Set 的区别？

Map 和 Set 查找速度都非常快，时间复杂度为 O(1)，而数组查找的时间复杂度为 O(n)。
Map 对象初始化的值为一个二维数组，Set 对象初始化的值为一维数组。
Map 对象和 Set 对象都不允许键重复（可以将 Set 对象的键想象成值）。
Map 对象的键是不能改的，但是值能改，Set 对象只能通过迭代器来更改值。

HashSet 是如何去重的？

HashSet 中的 add() 方法实际上是在调用 HashMap 的 put() 方法，正是因为 HashSet 的底层实现逻辑是基于 HashMap 实现的，并且 HashMap 的键也不会重复的原因是 HashMap 的 put() 方法内部实现的。

HashMap 中是如何判断两个 Key 是否相同？
- p.hash == hash ：比较两个hash值是否相等。
- (k = p.key) == key ：比较两个key的地址值是否相等。
- key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等。
```
if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
```
hashCode() 和 equals() 的区别？
- 如果两个对象的 hashcode() 返回值一样，其 equals() 返回结果不一定一样。
- 如果两个对象的 hashcode() 返回值不一样，其 equals() 返回结果一定不一样。
- 如果两个对象的 equals() 返回值一样，其 hashcode() 返回结果一定一样。
- 如果两个对象的 equals() 返回值不一样，其 hashcode() 返回结果不一定不一样。

说一下 Hashtable 的锁机制 ?

Hashtable 是使用 Synchronized 来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差！

ConcurrentHashMap 和 Hashtable 的效率哪个更高？

ConcurrentHashMap 的效率要高于 Hashtable
因为 Hashtable 给整个哈希表加了一把大锁从而实现线程安全。
而 ConcurrentHashMap 的锁粒度更低，在 JDK1.7 中采用分段锁实现线程安全，在 JDK1.8 中采用 CAS+Synchronized 实现线程安全。

讲一下 TreeMap？

TreeMap 是一个能比较元素大小的 Map 集合，会对传入的 key 进行了大小排序。可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
}

TreeMap 的继承结构：

TreeMap 的特点：

TreeMap 是有序的 key-value 集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的 Comparator 进行排序。
TreeMap 继承了 AbstractMap，实现了 NavigableMap 接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。

CopyOnWrite 是什么？

CopyOnWrite 的核心思想就是当我们对集合进行读取时，不做任何锁的控制，可以多线程并发读取，但是我们任何对集合进行修改的操作，都要加锁控制，保证同一时间只有一个线程，进行下面三个操作：(注意这里说的)

先用老集合 copy 出一份新集合；
然后在新集合上做修改；
最后用新集合直接替换老集合；

从 JDK1.5 开始 Java 并发包里提供了两个使用 CopyOnWrite 机制实现的并发容器，它们是 CopyOnWriteArrayList 和 CopyOnWriteArraySet。

CopyOnWriteArrayList & CopyOnWriteArraySet

CopyOnWriteArrayList 和 CopyOnWriteArraySet 的内部实现

CopyOnWriteArrayList 集合可以解决多线程操作集合的并发问题，读取的方法没有加同步锁，因此它的读取操作非常快，而修改操作使用 lock 来进行加锁，因此修改操作将对较慢。同一时间只有一个线程，能够进行修改操作，其他线程必须等待。

它唯一的缺点就是，一个线程对 CopyOnWriteArrayList 集合进行修改，另一线程并不能立即读取到。当然对同一线程来说，就没有这个问题的。

另外还有一个 CopyOnWriteArraySet 集合，它的内部就是使用 CopyOnWriteArrayList 集合实现的。

当进行修改集合的时候，我们要保证三个操作是多线程同步的，即使用老数组创建新数组，修改新数组，将新数组替换老数组。这个三个操作必须同一时间只有一个线程操作。

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 使用lock锁，保证修改共享变量array的线程安全。
    lock.lock();
    try {
        // 获取老数组elements
        Object[] elements = getArray();
        // 得到原来的值
        E oldValue = get(elements, index);
 
        // 有改变才修改
        if (oldValue != element) {
            int len = elements.length;
            // 用老的数组创建一个新数组
            Object[] newElements = Arrays.copyOf(elements, len);
            // 更新index位置的值
            newElements[index] = element;
            // 设置新数组
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            // 这个并不是无用语句，确保volatile变量的重新写入
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

CopyOnWriteArrayList 的缺点

内存占用问题。由于 CopyOnWrite 的写时复制机制，在进行写操作的时候，内存里会同时驻扎两个对象的内存。
CopyOnWrite 容器不能保证数据的实时一致性，可能读取到旧数据。

哪些集合类是线程安全的？哪些不安全？

线性安全的集合类：

Vector：比 ArrayList 多了同步机制。
Hashtable。
ConcurrentHashMap：是一种高效并且线程安全的集合。
Stack：栈，也是线程安全的，继承于 Vector。

线性不安全的集合类：

Hashmap
Arraylist
LinkedList
HashSet
TreeSet
TreeMap

迭代器 Iterator 是什么？

Iterator 模式使用同样的逻辑来遍历集合。它可以把访问逻辑从不同类型的集合类中抽象出来，不需要了解集合内部实现便可以遍历集合元素，统一使用 Iterator 提供的接口去遍历。它的特点是更加安全，因为它可以保证，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。

主要有三个方法：hasNext()、next() 和 remove()。

Iterator 和 ListIterator 有什么区别？

ListIterator 是 Iterator 的增强版。

ListIterator 遍历可以是逆向的，因为有 previous() 和 hasPrevious() 方法，而 Iterator 不可以。
ListIterator 有 add() 方法，可以向 List 添加对象，而 Iterator 却不能。
ListIterator 可以定位当前的索引位置，因为有 nextIndex() 和 previousIndex() 方法，而 Iterator 不可以。
ListIterator 可以实现对象的修改，set() 方法可以实现。Iierator 仅能遍历，不能修改。
ListIterator 只能用于遍历 List 及其子类，Iterator 可用来遍历所有集合。

ArrayList

ArrayList 了解吗？

ArrayList 的底层是 动态数组 ，它的容量能动态增长。在添加大量元素前，应用可以使用 ensureCapacity 操作增加 ArrayList 实例的容量。ArrayList 继承了 AbstractList ，并实现了 List 接口。

成员变量 & 构造函数

成员变量

ArrayList 底层是基于数组来实现容量大小动态变化的。

/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;  // 实际元素个数
transient Object[] elementData; 
// 默认初始容量大小为 10;
private static final int DEFAULT_CAPACITY = 10;

注意：上面的 size 是指 elementData 中实际有多少个元素，而 elementData.length 为集合容量，表示最多可以容纳多少个元素。

这个变量是定义在 AbstractList 中的。记录对 List 操作的次数。主要使用是在 Iterator，是防止在迭代的过程中集合被修改。

protected transient int modCount = 0;

private static final Object[] EMPTY_ELEMENTDATA = {};
 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

两个空的数组有什么区别呢？简单来讲就是第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。

ArrayList 构造函数

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

// 初始化值为 10
private static final int DEFAULT_CAPACITY = 10;
//定义一个空数组以供使用
private static final Object[] EMPTY_ELEMENTDATA = {};
//也是一个空数组，跟上边的空数组不同之处在于，这个是在默认构造器时返回的，扩容时需要用到这个作判断，后面会讲到
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存放数组中的元素，注意此变量是transient修饰的，不参与序列化
transient Object[] elementData;
//数组的长度，此参数是数组中实际的参数，区别于elementData.length，后边会说到
private int size;

调用无参构造函数，返回了一个空的数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此数组长度为 0.

// 调用此构造函数，返回了一个空的数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
// 此数组长度为0.
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

调用有参构造，就是构造一个具有指定长度的空数组，当 initialCapacity 为 0 时，返回 EMPTY_ELEMENTDATA

//带初始容量参数的构造函数。（用户自己指定容量）
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

包含特定集合元素的构造函数，把传入的集合转换为数组，然后通过 Arrays.copyOf 方法把集合中的元素拷贝到 elementData 中。同样，若传入的集合长度为 0，返回 EMPTY_ELEMENTDATA

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

说说 ArrayList 的扩容机制？（重要）

ArrayList 扩容的本质就是计算出新的扩容数组的 size 后实例化，并将原有数组内容复制到新数组中去。 默认情况下，新的容量会是原容量的 1.5 倍。

add() 方法在添加一个元素时，会调用 ensureCapacityInternal(size + 1) 方法，把数组实际容量加 1 判断是否能存下下一个数据 ，如果能装下才进行元素的添加，否则进行扩容；

首先计算所需的最小容量
- 如果传入的是个空数组则最小容量取默认容量 10 与 minCapacity 之间的最大值
- 否则直接返回 minCapacity，minCapacity 就是 size + 1
如果 minCapacity < elementData.length，直接将元素添加到数组最后
否则调用 grow(minCapacity); 进行扩容（minCapacity - elementData.length > 0）
- 计算新容量（原来的 1.5 倍，旧容量 + 旧容量右移一位），int newCapacity = oldCapacity + (oldCapacity>> 1);
- 校验容量是否够，if (newCapacity - minCapacity < 0)
- 若预设值大于默认的最大值，检查是否溢出，if (newCapacity - MAX_ARRAY_SIZE> 0)
- 最后，调用 Arrays.copyOf 方法将 elementData 数组指向新的内存空间，并将 elementData 的数据复制到新的内存空间。
```
elementData = Arrays.copyOf(elementData, newCapacity);
```

说说删除操作流程？

当我们调用 remove(int index) 时，首先会检查 index 是否合法（是否超出边界），然后再判断要删除的元素是否位于数组的最后一个位置。
- 如果 index 不是最后一个，就再次调用 System.arraycopy() 方法拷贝数组，将从 index + 1 开始向后所有的元素都向前挪一个位置。然后将数组的最后一个位置空，size - 1。
- 如果 index 是最后一个，那么就直接将数组的最后一个位置空，size - 1 即可。
当我们调用 remove(Object o) 时，会把 o 分为是否为空来分别处理。然后对数组做遍历，找到第一个与 o 对应的下标 index，然后调用 fastRemove 方法，删除下标为 index 的元素。其实仔细观察 fastRemove(int index) 方法和 remove(int index) 方法基本全部相同。

public E remove(int index) {
    rangeCheck(index);
 
    modCount++;
    E oldValue = elementData(index);
 
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
 
    return oldValue;
}
public boolean remove(Object o) {
	if (o == null) {
		for (int index = 0; index < size; index++)
			if (elementData[index] == null) {
				fastRemove(index);
				return true;
			}
	} else {
		for (int index = 0; index < size; index++)
			if (o.equals(elementData[index])) {
				fastRemove(index);
				return true;
			}
	}
	return false;
}
 
private void fastRemove(int index) {
	modCount++;
	int numMoved = size - index - 1;
	if (numMoved > 0)
		System.arraycopy(elementData, index+1, elementData, index,numMoved);
	elementData[--size] = null; // clear to let GC do its work
}

什么是 fail fast？（重要）

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出 Concurrent Modification Exception。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改 modCount 值刚好又设置为了 expectedmodCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。
场景：java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 HashMap、ArrayList 这些集合类。

解决方法

使用 Colletions.synchronizedList() 方法或在修改集合内容的地方加上 synchronized。这样的话，增删集合内容的同步锁会阻塞遍历操作，影响性能。
使用 CopyOnWriteArrayList 来替换 ArrayList。在对 CopyOnWriteArrayList 进行修改操作的时候，会拷贝一个新的数组，对新的数组进行操作，操作完成后再把引用移到新的数组。

什么是 fail safe？（重要）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了 Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

怎么在遍历 ArrayList 时移除一个元素？

foreach 删除会导致快速失败问题，可以使用迭代器的 remove() 方法。

Iterator itr = list.iterator();
while(itr.hasNext()) {
      if(itr.next().equals("jay") {
        itr.remove();
      }
}

HashMap

HashMap 是怎么实现的？

HashMap 是线程不安全的，key、value 均可以为 null。
jdk1.8 之前 HashMap 由数组 + 链表组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突
jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（转为红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时（必须同时满足两个条件），此时此索引位置上的所有数据改为使用红黑树存储。
补充：将链表转换成红黑树前会判断，即便阈值大于 8，但是数组长度小于 64，此时并不会将链表变为红黑树，而是选择逬行数组扩容。

你对红黑树了解多少？为什么不用二叉树 / 平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

每个节点要么是红色，要么是黑色；
根节点永远是黑色的；
所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
每个红色节点的两个子节点一定都是黑色；
从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的 O(n) 时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

红黑树怎么保持平衡的知道吗？TODO

红黑树有两种方式保持平衡：旋转和染色。

旋转：旋转分为两种，左旋和右旋

HashMap 的 put 流程知道吗？（重要）

首先进行哈希值的计算，获取一个新的哈希值。

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

1. 如果 table 没有初始化就先进行初始化过程；
1. 根据哈希值计算数组下标，如果对应下标正好没有存放数据，则直接构建节点插入，否则就是出现碰撞冲突了，则需要处理冲突。
```
tab[i = (n - 1) & hash])
```
- 判断 tab[i] 是否为树节点，否则向链表中插入数据，是则向树中插入节点；
- 否则采用传统的链式方法插入。如果链表中插入节点的时候，链表长度大于等于 8，会调用 treeifyBin() 方法处理。在该方法中会判断数组长度是否小于 64，如果大于 64 才转换为红黑树，否则依旧进行扩容。
```
treeifyBin(tab, hash);
```
1. 最后所有元素处理完成后，判断是否超过阈值；threshold ，超过则扩容。

HashMap 中是如何判断 key 是否相等的呢？（重要重要重要）

通俗来说，Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。即在散列集合包括 HashSet、HashMap 以及 HashTable 里，对每一个存储的桶元素都有一个唯一的 “块编号”，即它在集合里面的存储地址；当你调用 contains 方法的时候，它会根据 hashcode 找到块的存储地址从而定位到该桶元素。
那为什么还需要 equals()? 该方法是用来判断两个对象内存地址是否相同的方法，如果该方法被重写了，则依据其具体重写的内容来判断其具体功能，一般重写之后变成判断两个对象的值是否相同。
HashMap 中是如何判断两个 Key 是否相同？
- p.hash == hash：比较两个 hash 值是否相等。
- (k = p.key) == key：比较两个 key 的地址值是否相等。
- key != null && key.equals(k)：能够执行到这里说明两个 key 的地址值不相等，那么先判断后添加的 key 是否等于 null，如果不等于 null 再调用 equals 方法判断两个 key 的内容是否相等。
```
if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
```
hashCode() 和 equals() 的区别？
- 如果两个对象的 hashcode() 返回值一样，其 equals() 返回结果不一定一样。
- 如果两个对象的 hashcode() 返回值不一样，其 equals() 返回结果一定不一样。
- 如果两个对象的 equals() 返回值一样，其 hashcode() 返回结果一定一样。
- 如果两个对象的 equals() 返回值不一样，其 hashcode() 返回结果不一定不一样。

为什么 HashMap 的容量是 2 的幂次方呢？

Hash 值的范围值比较大，使用之前需要先对数组的长度取模运算，得到的余数才是元素存放的位置也就是对应的数组下标。这个数组下标的计算方法是 (n - 1) & hash。

将 HashMap 的长度定为 2 的幂次方，这样就可以使用 (n - 1)&hash 位运算代替 % 取余的操作，提高性能。

(n - 1) & hash：根据 hash 值计算索引值，在 n 为 2 的整次幂的时候相当于取模。

如果初始化 HashMap，传一个 17 的值（不是 2 的整次幂）new HashMap<>，它会怎么处理？

传的不是 2 的倍数时，HashMap 会向上寻找离得最近的 2 的倍数，所以传入 17，但 HashMap 的实际容量是 32。

源码中是通过一系列右移 + 按位或实现的。

HashMap 的哈希 / 扰动函数是怎么计算的? 如何计算数组（索引）下标？为什么这样设计？

hash() 函数实现

hash() 函数是先拿到 key 的 hashcode，是一个 32 位的 int 类型的数值，然后让 hashcode 的高 16 位和低 16 位进行异或操作。

static final int hash(Object key) {
    int h;
    // key的hashCode和key的hashCode右移16位做异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计思路

如果当 n 即数组长度很小，假设是 16 的话，那么 n - 1 即为 1111 ，这样的值和 hashCode 直接做按位与操作，实际上只使用了哈希值的后 4 位。 如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

为什么 HashMap 链表转红黑树的阈值为 8 呢？为什么 HashMap 红黑树转链表阈值为 6 呢?

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。（空间换时间）

阈值为什么要选 8 呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布**，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为 0.00000006。**

至于红黑树转回链表的阈值为什么是 6，而不是 8？是因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

HashMap 怎么查找元素的呢？

HashMap 的查找就简单很多：

使用 hash() 函数计算 key 的哈希值；
计算数组下标，获取节点；
当前节点和 key 匹配，直接返回；
否则，当前节点是否为树节点，查找红黑树；
否则，遍历链表查找

HashMap 在什么时候需要会扩容？

当 HashMap 中的元素个数超过临界值（threshold ）= 数组大小 (数组长度) * loadFactor(负载因子) 时，就会进行数组扩容，loadFactor 的默认值是 0.75。默认为 16 * 0.75 = 12。
当链表长度大于 8，且数组长度小于 64 时会进行扩容。

为什么扩容因子是 0.75？

假如设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。
假如设的比较小，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

详细说说 HashMap 的扩容机制为什么是扩容 2 倍？它是如何计算新下标的？

以 JDK1.8 为例，当往 HashMap 放入元素时，如果元素个数 > threshold 时，会进行扩容，使用 2 倍容量的数组代替原有数组。表现在二进制上就是多了一个高位参与数组下标计算。

也就是说，在元素拷贝过程不需要重新计算元素在数组中的位置，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0，是 0 的话索引没变，是 1 的话索引变成 “原索引 + oldCap”（根据 e.hash & oldCap == 0 判断）。

因此，我们在扩充 HashMap 的时候，不需要重新计算 hash 值，只需要用原来的 hash 值和原数组扩容前长度进行与操作（&），然后看高位的那个 bit 是 1 还是 0 就可以了，是 0 的话索引没变，是 1 的话索引变成 “原位置 + 旧容量” 。

if ((e.hash & oldCap) == 0) {
	// 在 原位置
} else {
	// 在 原位置 + oldCap 的位置
}

优点：

省去了重新计算 hash 值的时间。
由于新增的 1bit 是 0 还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的结点数一定小于等于原来桶上的结点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的结点分散到新的桶中了。

在解决 hash 冲突的时候，为什么选择先用链表，再转红黑树?

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
当元素小于 8 个的时候，链表结构可以保证查询性能。
当元素大于 8 个的时候，红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来 加快查询速度，但是插入和删除节点的效率变慢了。

HashMap 是线程安全的吗？多线程下会有什么问题？

HashMap 不是线程安全的，可能会发生这些问题：

多线程下扩容死循环 。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程的 put 可能导致元素的丢失 。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
put 和 get 并发时，可能导致 get 为 null。 线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

有什么办法能解决 HashMap 线程不安全的问题呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个 table 数组 ，粒度比较大；
Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
ConcurrentHashMap 在 jdk1.7 中使用分段锁 ，在 jdk1.8 中使用 CAS+synchronized 。

jdk1.8 对 HashMap 主要做了哪些优化呢？为什么？（总结，不仅仅局限于数据结构）

数据结构：数组 + 链表改成了数组 + 链表或红黑树
- 原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n) 降为 O(logn)
链表插入方式：链表的插入方式从头插法改成了尾插法
- 原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
扩容 rehash
- 扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
- 原因：提高扩容的效率，更快地扩容。
扩容时机：在插入时，1.7 先判断是否需要扩容，再插入；1.8 先进行插入，插入完成再判断是否需要扩容；

ConcurrentHashMap

说说 ConcurrentHashMap 怎么实现的？

jdk1.7 版本是基于分段锁实现。
jdk1.8 是基于 CAS + synchronized 实现。

jdk1.7 ConcurrentHashMap

jdk1.7 中的分段锁

从结构上说，1.7 版本的 ConcurrentHashMap 采用分段锁机制， 里面包含一个Segment数组 ，Segment 继承于 ReentrantLock ，Segment 则包含 HashEntry的数组 ， HashEntry本身就是一个链表的结构 ，具有保存 key、value 的能力，能指向下一个节点的指针。

实际上就是相当于每个Segment都是一个HashMap，默认的Segment长度是16，也就是支持16个线程的并发写，Segment之间相互不会受到影响。

jdk1.7 的 put 流程

计算 hash，定位到 segment，segment 如果是空就先初始化
使用 ReentrantLock 加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功
遍历 HashEntry，就是和 HashMap 一样，数组中 key 和 hash 一样就直接替换，不存在就再插入链表，链表同样操作

jdk1.7 的 get 流程

get 也很简单，key 通过 hash 定位到 segment，再遍历链表定位到具体的元素上，需要注意的是 value 是 volatile 的，所以 get 是不需要加锁的。

jdk1.8 ConcurrentHashMap

jdk1.8 CAS+synchronized

jdk1.8 实现线程安全不是在数据结构上下功夫，它的数据结构和 HashMap 是一样的，数组 + 链表 + 红黑树。它实现线程安全的 关键点在于 put 流程。

jdk1.8 的 put 流程（重要）

首先根据 key 计算 hash 值；
如果 node 数组为空，先进行初始化；
遍历 node 数组，拿到首节点 f，判断首节点：
- 如果为 null ，则通过 cas 的方式尝试添加。
- 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。
- 如果都不满足，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。
当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。

ConcurrentHashMap 的 get 方法是否要加锁，为什么？重要

get 方法不需要加锁。
因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程 A 修改结点的 val 或者新增节点的时候是对线程 B 可见的。
这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap() 包装的 HashMap 安全效率高的原因之一。

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	//可以看到这些都用了volatile修饰
	volatile V val;
	volatile Node<K,V> next;
}

get 方法不需要加锁与 volatile 修饰的哈希桶有关吗？

没有关系。哈希桶 table 用 volatile 修饰主要是保证在数组扩容的时候保证可见性。

ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？

我们先来说 value 为什么不能为 null ，因为 ConcurrentHashMap 是用于多线程的，如果 map.get(key) 得到了 null ，无法判断，是映射的 value 是 null ，还是没有找到对应的 key 而为 null ，这就有了二义性。
而用于单线程状态的 HashMap 却可以用 containsKey(key) 去判断到底是否包含了这个 null 。

我们用反证法来推理：

假设 ConcurrentHashMap 允许存放值为 null 的 value，这时有 A、B 两个线程，线程 A 调用 ConcurrentHashMap.get(key) 方法，返回为 null ，我们不知道这个 null 是没有映射的 null ，还是存的值就是 null 。
假设此时，返回为 null 的真实情况是没有找到对应的 key。那么，我们可以用 ConcurrentHashMap
.containsKey(key) 来验证我们的假设是否成立，我们期望的结果是返回 false。
但是在我们调用 ConcurrentHashMap.get(key) 方法之后，containsKey 方法之前，线程 B 执行了
ConcurrentHashMap.put(key, null) 的操作。那么我们调用 containsKey 方法返回的就是 true 了，这就与我们的假设的真实情况不符合了，这就有了二义性。

ConcurrentHashMap 的并发度是多少？

在 JDK1.7 中，并发度默认是 16，这个值可以在构造函数中设置。
如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的 2 的幂指数作为实际并发度，也就是比如你设置的值是 17，那么实际并发度是 32。

ConcurrentHashMap 和 Hashtable 的效率哪个更高？为什么？

ConcurrentHashMap 的效率要高于 Hashtable，因为 Hashtable 给整个哈希表加了一把大锁从而实现线程安全。而 ConcurrentHashMap 的锁粒度更低，在 JDK1.7 中采用分段锁实现线程安全，在 JDK1.8 中采用 CAS+Synchronized 实现线程安全。

HL🌱数字花园

探索

Java 集合总结