2023年超实用的Java集合相关面试题！！
2023年超实用的Java集合相关面试题！！！
3.1：有⽤过ArrayList吗？它是做什么用的？
ArrayList就是数组列表，底层是数组 Object[] elementData。ArrayList在装载基本数据类型时，实际装载的是对应的包装类。与ArrayList类似的还有LinkedList，他们俩相比：
• ArrayList：查找和访问元素的速度快，新增、删除的速度慢。线程不安全，使⽤频率⾼。
• LinkedList：查找和访问元素的速度慢，新增、删除的速度快。
3.2：ArrayList线程不安全，为什么还要去⽤？
实际开发中有以下⼏种场景：
• 频繁增删：使⽤LinkedList，但是涉及到频繁增删的场景不多
• 追求线程安全：使⽤Vector。
• 普通的⽤来查询：使⽤ArrayList，使⽤的场景最多。
根据数据结构的特性，三者难以全包含，只能在相互之间做取舍。
3.3：ArrayList底层是数组，那是怎么实现不断扩容的？
• 使用无参构造创建ArrayList
/**
* Default initial capacity.
* 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
这个是创建的默认⼤⼩的空数组。EMPTY_ELEMENTDATA⽤于表⽰当第⼀个数据被添加时该空数
组初始化的⼤⼩。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
* 构造⼀个空的List，该List具有10个容量
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}使⽤ArrayList空参的构造器创建集合时，数组并没有创建。当集合中添加第⼀个元素时，数组被创建，初始化容量为4.
• 使⽤有参构造创建ArrayList
有参构造创建时，如果指定了容量则会创建出指定容量⼤⼩的数组。如果指定容量为0，则⽆参构造⼀样。
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}3.4：ArrayList(int initialCapacity)会不会初始化数组⼤⼩？
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}会初始化⼤⼩，但如果通过ArrayList的size()⽅法进⾏判断时结果依然为0，因为只有在添加元素时才会对ArrayList的size属性+1
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;3.5：ArrayList底层是⽤数组实现，但数组⻓度是有限的，如何实现扩容？
当新增元素，ArrayList放不下该元素时，触发扩容。
扩容的容量将会是原容量的1/2，也就是新容量是旧容量的1.5倍。
确定新容量确定的源码：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量=旧容量+1/2旧容量
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);
}执⾏扩容时使⽤系统类System的数组复制⽅法arraycopy()进⾏扩容。
扩容的源码：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends
T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}3.6：ArrayList1.7之前和1.7及以后的区别？
1.7之前ArrayList在初始化的时候直接调⽤this(10)，初始化容量为10的数组。在1.7及以后，只有第⼀次执⾏add⽅法向集合添加元素时才会创建容量为10的数组。
3.7：为什么ArrayList增删⽐较慢，增删是如何做的？
• 没有指定index添加元素
直接添加到最后，如果容量不够则需要扩容
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}• 如果指定了index添加元素
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}从源码⾥看到，是将要添加的元素位置index之后的已有元素全部拷⻉到添加到原数组index+1处，然后再把新的数据加⼊。
3.8：ArrayList插⼊和删除数据⼀定慢吗？
不⼀定，取决于删除的数据离数组末端有多远，如果离末端较近，则性能不⼀定差。
3.9：ArrayList如何删除数据？
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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
}ArrayList删除数据时同样使⽤拷⻉数组的⽅式，将要删除的位置之后的所有元素拷到当前位置，最后再对最后⼀个位置的数据设置为null，交给gc来回收。这种删除，其实就是覆盖，如果数据量⼤，那么效率很低。
3.10：ArrayList适合做队列吗？
队列需要遵循先进先出的原则，如果从ArrayList的数组头部⼊队列，数组尾部出队列，那么对于⼊队列时的操作，会涉及⼤数据量的数组拷⻉，⼗分耗性能。队头队尾反⼀反也是⼀样，因此ArrayList不适合做队列。
3.11：数组适合做队列吗？
ArrayBlockingQueue环形队列就是⽤数组来实现的。ArrayBlockingQueue的存和取操作的索引是在当索引值等于容量值时，将索引值设置为0实现环形队列的效果，因此在这种情况下，数组适合做队列。
/**
* Inserts element at current put position, advances, and signals.
* Call only when holding lock.
*/
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x;
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal();
}
/**
* Extracts element at current take position, advances, and signals.
* Call only when holding lock.
*/
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
return x;
}3.12：ArrayList和LinkedList两者的遍历性能孰优孰劣？
ArrayList的遍历性能明显要⽐LinkedList好，因为ArrayList存储的数据在内存中时连续的，CPU内部缓存结构会缓存连续的内存⽚段，可以⼤幅降低读取内存的性能开销。
3.13：了解数据结构中的HashMap吗？介绍下他的结构和底层原理
HashMap是由数组+链表组成的数据结构（jdk1.8中是数组+链表+红⿊树的数据结构）
1.7 版本：根据hash(key)确定存储位置后，以链表的形式在该位置处存数据。此时数组该位置的
链表存了多个数据，因此也称为桶‘
存放的数据是⽤Entry描述
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}• 1.8 版本：
存放的数据是⽤Node描述
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}...
链表有可能过⻓，所以在满⾜以下条件时，链表会转换成红⿊树：
• 链表⻓度>8
• 数组⼤⼩>=64
• 1.8版本：当红⿊树节点个数<6时转换为链表
3.14：那你清楚HashMap的插⼊数据的过程吗？
3.15：刚才你提到HashMap的初始化，那HashMap怎么设定初始容量大小的？
• 如果没有指定容量：则使⽤默认的容量为16，负载因⼦0.75
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}如果指定了容量，则会初始化容量为：⼤于指定容量的，最近的2的整数次⽅的数。⽐如传入是10，则会初始化容量为16（2的4次⽅）。
具体实现：
/**
* Returns a power of two size for the given target capacity.
*/
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;
}该算法的逻辑是让⾼位1的之后所有位上的数都为1，再做+1的操作，实现初始化容量为：⼤于指定容量的，最近的2的整数次⽅的数。
3.16：你提到hash函数，你知道HashMap的hash函数是如何设计的？
// jdk1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//jdk1.7 相⽐jdk1.8, jdk1.7做了四次移位和四次异或运算，效率⽐1.8要低
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);⽤key的hashCode()与其低16位做异或运算。这个扰动函数的设计有两个原因：
• 计算出来的hash值尽量分散，降级hash碰撞的概率
• ⽤位运算做算法，更加⾼效
这样答只是答了表象的东西，深层的内容是这样的：
⾸先我们要知道hash运算的⽬的是⽤来定位该数据要存放在数组的哪个位置，如何计算？
// jdk 1.8
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// jdk 1.7
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power o
f 2";
return h & (length-1);
}是通过n-1的操作与原hash值做“与”运算，其中n是数组的⻓度。相当于是更⾼效的%取模运算。而n-1恰好是⼀个低位掩码。⽐如初始化⻓度是16，那n-1是15，即⼆进制的0000 1111。此时得到了另⼀个问题的答案：那么为什么不能直接⽤key的hashCode()作为hash值，⽽⼀定要^ (h>>> 16)？
因为如果直接⽤key的hashCode()作为hash值，很容易发⽣hash碰撞。
使⽤扰动函数^ (h >>> 16)，就是为了混淆原始哈希码的⾼位和低位，以此来加⼤低位的随机性。且低位中参杂了⾼位的信息，这样⾼位的信息也作为扰动函数的关键信息。
3.17：1.8相⽐1.7，做了哪些优化
1.8除了引⼊了红⿊树，将时间复杂度由O(n)降为O(log n)以外，还将1.7的头插法改为1.8的尾插法。
• 头插法：
作者认为，后插⼊的数据，被访问的概率更⾼，所以使⽤了头插法，但头插法会存在遍历时死循环的情况。
扩容之前：
源码：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; //此处如果发⽣并发，线程1执⾏反转过程中线程2执⾏
newTable[i] = e;
e = next;
}
}
}当线程1执⾏反转过程中线程2执⾏，就可能会出现如下情况，造成链表成环的死循环问题
• 尾插法
在扩容时会保持链表元素原先的顺序，因此不会出现链表成环的死循环问题。
3.18：HashMap怎么实现扩容的
HashMap执⾏扩容关系到两个参数：
• Capacity：HashMap当前容量
• loadFactor：负载因⼦（默认是0.75）
当HashMap容量达到Capacity*loadFactor时，进⾏扩容。
1.7和1.8版本的扩容区别：
• 1.7版本
先扩容，再插⼊数据。扩容时会创建⼀个为原数组的2倍⼤⼩的数组，然后将原数组的元素重新hash，存进新数组。
• 1.8版本
先插⼊数据，再执⾏扩容。扩容时会创建⼀个为原数组的2倍⼤⼩的数组，然后将原数组的元素存进新数组。不同的是1.8使⽤位移操作创建2倍⼤⼩的新数组
1 newThr = oldThr << 1;3.19：插⼊数据时扩容的重新hash是怎么做的？
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}1.8：不需要做hash，通过原⽅式获取存储位置
newTab[e.hash & (newCap - 1)] = e;
由于newCap为新数组的⼤⼩，因此在做与操作时，在没有改变key的hash的情况下，改变了与数的
值来获取新的存储位置，效率更⾼。⽽且位预算的newCap-1 实际上由于2的幂的关系，-1的操作实
际上就是在⾼位补1，效率更⾼。
3.20：为什么重写equals⽅法后还要重写hashCode方法
因为在put的时候，如果数据已经存在，就需要把⽼的数据return，存⼊新的数据。那如何判断数据已存在呢？是通过先⽐较hash值，如果hash值相同，再⽤equals判断。
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;重写equals和hashCode⽅法的⽬的就是根据对象的属性来进⾏判断对象是否相同，⽽⾮根据对象的 内存地址来判断。
public class User {
private int id;
private String name;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return id == user.id && Objects.equals(name, user.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name);
}
}3.21：HashMap在多线程使⽤场景下会存在线程安全问题，怎么处理？
处理⽅案有以下三种：
• 使⽤Collections.synchronizedMap()创建线程安全的map集合
• 使⽤Hashtable
• 使⽤ConcurrentHashMap
鉴于效率考虑，推荐使⽤ConcurrentHashMap。
3.22：Collections.synchronizedMap()如何实现线程安全
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this; //设置当前对象互斥量
}Collections.synchronizedMap(map)创建出的SynchronizedMap对象，把当前对象作为互斥量（也可以指定互斥量）。
之后操作该SynchronizedMap，其操作Map的⽅法都被加上了synchronized。
public int size() {
synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
synchronized (mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized (mutex) {return m.remove(key);}
}
public void putAll(Map<? extends K, ? extends V> map) {
synchronized (mutex) {m.putAll(map);}
}
public void clear() {
synchronized (mutex) {m.clear();}
}3.23：Hashtable的性能为什么不好？
Hashtable的每个操作都使⽤了synchronized上了锁，甚⾄读的操作也上锁
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}3.24：Hashtable和HashMap有什么区别？
Hashtable的键值不能为null，但HashMap可以为null。
HashMap在存放null的键时做了处理
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}为什么要Hashtable设计成不能为null？
因为Hashtable如果可以存null，那么有可能导致判断数据是否已存在时，没办法判断是否是null还
是不存在。
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}除此之外，Hashtable的初始化容量是11，扩容时是当前容量*2+1。
int newCapacity = (oldCapacity << 1) + 1;
3.25：什么是fail-safe和fail-fast
fail-safe：安全失败。java.util.concurrent并发包下的容器都是遵循安全失败机制。即可以在多线程下并发修改。不会抛出并发修改的异常Concurrent Modification Exception
Fail-fast: 快速失败。Java集合在使⽤迭代器遍历时，如果遍历过程中对集合中的内容进⾏了增删改的操作时，则会抛出并发修改的异常Concurrent Modification Exception。即使不存在并发，也会抛出该异常，所以称之为快速失败。
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}3.26：ConcurrentHashMap的数据结构是怎么样？
从类关系图上来看HashMap和ConcurrentHashMap都来⾃于Map，因此ConcurrentHashMap数据
结构遵循HashMap的1.7和1.8的特征。
• 1.7版本使⽤的是数组+链表结构
• 1.8版本使⽤的是数组+链表+红⿊树结构
但是ConcurrentHashMap在数组中存的元素不同。
• 1.7版本：
存⼊的数据⽤Segment类型来封装。
/**
* Segments are specialized versions of hash tables. This
* subclasses from ReentrantLock opportunistically, just to
* simplify some locking and avoid separate construction.
*/
static final class Segment<K,V> extends ReentrantLock implements Serializab
le {
...
}⼀个ConcurrentHashMap包含⼀个Segment数组，Segment⾥包含⼀个HashEntry数组，每个HashEntry数组中是⼀个链表结构的元素，每个Segment守护着⼀个HashEntry数组⾥的元素，当对HashEntry数组的数据进⾏修改时，必须⾸先获得与它对应的Segment锁。每个Segment元素相当于⼀个⼩的HashMap。
⼀个ConcurrentHashMap中只有⼀个Segment
<K,V>类型的segments数组，每个segment中只有⼀个HashEntry
<K,V>类型的table数组，table数组中存放⼀个HashEntry节点。
HashEntry的内部结构：
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value; //加了volatile修饰，保存内存可⻅性及防⽌指令重排
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}很显然，1.7版本的ConcurrentHashMap采⽤了分段锁（Segment）技术，其中Segment继承了ReentrantLock。
在插⼊ConcurrentHashMap元素时，先尝试获得Segment锁，先是⾃旋获锁，如果⾃旋次数超过阈值，则转为ReentrantLock上锁。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value); //⾃旋获锁
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;//算出插⼊位置
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {//判断插⼊的元素是否已存在
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
//创建节点
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);//扩容
else
setEntryAt(tab, index, node);//存⼊节点
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();//释放锁
}
return oldValue;
}
e = e.next;//不存在则遍历下⼀个3.27：Segment如何实现扩容？
/**
* Doubles size of table and repacks entries, also adding the
* given node to new table
*/
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
int sizeMask = newCapacity - 1;
for (int i = 0; i < oldCapacity ; i++) {
qHashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
int idx = e.hash & sizeMask;
if (next == null) // Single node on list
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {//如果找到不相同的hash索引位置，则继续找下⼀个，直到找到最后⼀个相同的索引位置。
lastIdx = k;
lastRun = last;
}
}//找到第⼀个后续节点新的index不变的节点。
newTable[lastIdx] = lastRun;
// Clone remaining nodes 第⼀个后续节点新index不变节点前所有节点均需要重新创建分配。——⽤以提升效率
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}ConcurrentHashMap 的扩容是仅仅和每个Segment元素中HashEntry数组的⻓度有关，但需要扩容
时，只扩容当前Segment中HashEntry数组即可。也就是说ConcurrentHashMap中Segment[]数组
的⻓度是在初始化的时候就确定了，后⾯扩容不会改变这个⻓度。
3.28：ConcurrentHashMap在JDK1.8版本的数据结构是什么样的？
1.8版本放弃了Segment，跟HashMap⼀样，⽤Node描述插⼊集合中的元素。但是Node中的val和
next使⽤了volatile来修饰，保存了内存可⻅性。与HashMap相同的是，ConcurrentHashMap1.8版
本使⽤了数组+链表+红⿊树的结构。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}同时，ConcurrentHashMap使⽤了CAS+Synchronized保证了并发的安全性。
下⾯介绍ConcurrentHashMap的put过程：
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());//更为分散的hash值
int binCount = 0;//统计节点个数
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();//初始化数组
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//该位置没有
元素，则⽤cas⾃旋获锁，存⼊节点
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);//如果ConcurrentHashMap正在扩容，则协助
其转移
else {
V oldVal = null;
synchronized (f) {//对根节点上锁
if (tabAt(tab, i) == f) {
if (fh >= 0) {//fh>=0 说明是链表，否则是红⿊树
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);//尾
插法插⼊
break;
}
}
}
else if (f instanceof TreeBin) {//红⿊树
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {//判断链表的值是否⼤于等于8，如果⼤于等于8就升级
为红⿊树。
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}3.29： CAS是什么？
CAS是英⽂单词Compare and Swap的缩写，翻译过来就是⽐较并替换。CAS属于乐观锁⸺没有上
任何锁，所以线程不会阻塞，但依然会有上锁的效果。
CAS机制中使⽤了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
更新⼀个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对
应的值修改为B。
举个例⼦：
• 在内存地址V当中，存储着值为10的变量。
• 线程1开始提交更新，⾸先进⾏A和地址V的实际值⽐较，发现A不等于V的实际值，提交失败。
线程1 重新获取内存地址V的当前值，并重新计算想要修改的值。此时对线程1来说，A=11，B=12。这个重新尝试的过程被称为⾃旋。
这⼀次⽐较幸运，没有其他线程改变地址V的值。线程1进⾏⽐较，发现A和地址V的实际值是相等的。
线程1进⾏交换，把地址V的值替换为B，也就是12。
CAS的缺点：
• CPU开销过⼤
在并发量⽐较⾼的情况下，如果许多线程反复尝试更新某⼀个变量，却⼜⼀直更新不成功，循环往
复，会给CPU带来很到的压⼒。
• 不能保证代码块的原⼦性
CAS机制所保证的只是⼀个变量的原⼦性操作，⽽不能保证整个代码块的原⼦性。⽐如需要保证3个
变量共同进⾏原⼦性的更新，就不得不使⽤synchronized了。
• ABA问题
这是CAS机制最⼤的问题所在。
• 假设内存中有⼀个值为A的变量，存储在地址V中。
接下来，线程1先⼀步执⾏成功，把当前值成功从A更新为B；同时线程2因为某种原因被阻塞住，
没有做更新操作；线程3在线程1更新之后，获取了当前值B。
在之后，线程2仍然处于阻塞状态，线程3继续执⾏，成功把当前值从B更新成了A。
最后，线程2终于恢复了运⾏状态，由于阻塞之前已经获得了“当前值A”，并且经过compare检测，内存地址V中的实际值也是A，所以成功把变量值A更新成了B。
看起来这个例⼦没啥问题，但如果结合实际，就可以发现它的问题所在。
我们假设⼀个提款机的例⼦。假设有⼀个遵循CAS原理的提款机，⼩灰有100元存款，要⽤这个提
款机来提款50元。
由于提款机硬件出了点问题，⼩灰的提款操作被同时提交了两次，开启了两个线程，两个线程都
是获取当前值100元，要更新成50元。理想情况下，应该⼀个线程更新成功，⼀个线程更新失败，
⼩灰的存款值被扣⼀次。
线程1⾸先执⾏成功，把余额从100改成50。线程2因为某种原因阻塞。这时，⼩灰的妈妈刚好给⼩灰汇款50元。
线程2仍然是阻塞状态，线程3执⾏成功，把余额从50改成了100。
线程2恢复运⾏，由于阻塞之前获得了“当前值”100，并且经过compare检测，此时存款实际值
也是100，所以会成功把变量值100更新成50。
原本线程2应当提交失败，⼩灰的正确余额应该保持100元，结果由于ABA问题提交成功了。
怎么解决呢？加个版本号就可以了。
真正要做到严谨的CAS机制，在compare阶段不仅要⽐较期望值A和地址V中的实际值，还要⽐较变量的版本号是否⼀致。假设地址V中存储着变量值A，当前版本号是01。线程1获取了当前值A和版本号01，想要更新为B，但是被阻塞了。
这时候，内存地址V中变量发⽣了多次改变，版本号提升为03，但是变量值仍然是A。
随后线程1恢复运⾏，进⾏compare操作。经过⽐较，线程1所获得的值和地址的实际值都是A，但是
版本号不相等，所以这⼀次更新失败。
在数据库层⾯操作版本号：判断原来的值和版本号是否匹配，中间有别的线程修改，值可能相等，但
是版本号100%不⼀样
update a set value = newValue, vision = vision + 1 where value = #{oldValue} an
d vision = #{vision}3.30：ConcurrentHashMap效率为什么高
因为ConcurrentHashMap的get⽅法并没有上锁。get时通过hash(key)定位到Segment上，再通过⼀次Hash定位到具体的HashEntry上。HashEntry的get⽅法如下：
public V get(Object key) {// key由equals()确定唯⼀性
Segment<K, V> s; //
HashEntry<K, V>[] tab;
int h = hash(key);//h是key的hashcode⼆次散列值。 根据key的hashcode再做散列
函数运算
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;//散列算法定位segement,u就是Segement数组的索引,Segment的散列运算,为了将不同key分散在不同segement.根据h获取segement的index
if ((s = (Segment<K, V>) UNSAFE.getObjectVolatile(segments, u)) != null&& (tab = s.table) != null) {// 如果u对应的segement存在，且segement中的table也存在,则获取table中的value
for (HashEntry<K, V> e = (HashEntry<K, V>) UNSAFE.getObjectVolatile(tab,((long) (((tab.length - 1) & h)) << TSHIFT) + TBASE); e !=null; e = e.next) {K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))// 查询到对象相同或者equals相等的key则返回对应的value
return e.value;
}
}
return null;
}由于HashEntry的value属性使⽤了volatile修饰，保证了内存可⻅性，每次获取都是最新值。因此整个过程不需要加锁。
