温故而知新-源码篇【面试复习】
前言
2023-7-25 08:10:40
以下内容源自《【面试复习】》
仅供学习交流使用
版权
禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话
推荐
温故而知新-基础篇【面试】
温故而知新-源码篇
ArrayList
get查找
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
set修改
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
add添加
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++;
}
remove删除
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;
}
elementData 下标获取
E elementData(int index) {
return (E) elementData[index];
}
grow扩容
计算所需的最小长度
例如：add()，minCapacity=size+1
grow():
得到旧容量：oldCapacity=elementData.length;
计算新容量：newCapacity=oldCapacity + (oldCapacity >> 1);
如果新容量<所需最小长度
新容量=最小长度
如果minCapacity大于MAX_ARRAY_SIZE，
则新容量则为Interger.MAX_VALUE，
否则，新容量大小则为 MAX_ARRAY_SIZE。
elementData=Arrays.copyof(elementData,newCapacity)
测试代码：
测试1：默认构造器
private static void extracted1() throws NoSuchFieldException {
//测试默认构造器第一次add，扩容机制
ArrayList<Integer> arrayList=new ArrayList<>();
//this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
//第一次强制进入Integer.valueOf()
//第二次强制进入ArrayList.add()
// arrayList.add(1);
//直接进入add()
arrayList.add(new Integer(1));
/*
add(E e){
ensureCapacityInternal(size + 1); // Increments modCount!!{
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//10
}
ensureExplicitCapacity(minCapacity=10);{
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity=10);{
int oldCapacity = elementData.length;//0
int newCapacity = oldCapacity + (oldCapacity >> 1);//0
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;//10
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);//10
}
}
}
elementData[size++] = e;
}
*/
}
测试2：传入initialCapacity=0
private static void extracted2() {
// ArrayList<Integer> arrayList0=new ArrayList<>(-1);
// throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
ArrayList<Integer> arrayList = new ArrayList<>(0);
// this.elementData = EMPTY_ELEMENTDATA;
arrayList.add(new Integer(1));
/*
add(E e){
ensureCapacityInternal(minCapacity=size+1){
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);{
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);{
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);
}
}
}
elementData[size++] = e;
}
*/
}
测试3：传入initialCapacity=1
private static void extracted3() {
ArrayList<Integer> arrayList1=new ArrayList<>(1);
// this.elementData = new Object[initialCapacity];
arrayList1.add(new Integer(1));
arrayList1.add(new Integer(2));
// elementData = Arrays.copyOf(elementData, newCapacity);//传入newCapacity=2
}
LinkedList
get查找
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
set修改
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
node通过下标获取结点
Node<E> node(int index) {
// assert isElementIndex(index);
//如果小于一半，使用next
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果大于一半，使用prev
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
add添加
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
remove删除
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
linkBefore前插
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
unlink移除
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//更改next指针
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//更改prev指针
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
ArrayList和LinkedList对比
数组和链表的区别
数组：查找更新快（下标获取），插入删除慢（复制数组）
链表：查找更新慢（从前往后，或从后往前），插入删除快（两个指针前驱和后继的操作）
//ArrayList
查找更新---下标获取
get---elementData[index]
set---elementData[index]
插入删除（复制数组）
add---arraycopy
remove---arraycopy
//LinkedList
查找更新----从前到后或从后到前来查
get---node
set---node
插入删除----两个指针前驱和后继操作
add---linkBefore
remove--unlink
HashMap
get查找
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;
//先检查数组是否为空
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) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//-----------------------------------------------------------------------------------
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//判断数组是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//先找到，放到node
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//删除node
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
put插入|修改
put
putVal
如果table为空或长度为0 resize()扩容
根据hash&len-1找到槽位
如果为空，直接插入
否则，hash冲突
判断第一个元素是否相等，更新
否则，得到node结点
判断是否是红黑树TreeNode，红黑树插入
遍历链表，相等更新，否则插入到最后
1.7的put
- 我们的put方法会去判断这个hashmap是否为null或者长度是否为0，如果是则调用inflateTable()方法对该hashmap数组初始化;
- 判断key是否为null,为null则遍历以table[0]为首的链表，寻找是否存在key==null对应的键值对,若存在，则覆盖旧value;同时返回旧的value值，否则调用addEntry()完成插入;
- key不为null.根据key计算数组索引值,循环链表，判断该key是否存在,存在，则覆盖旧value,并返回旧value;
- addEntry()先判断是否需要扩容，如果要扩容就进行扩容，如果不用扩容就生成Entry对象，并使用头插法添加到当前位置的链表中;
1.8的put
- 我们的put方法会去判断这个hashmap是否为null或者长度是否为0，如果是则对该hashmap数组进行resize()扩容;
- put方法根据key通过hash算法与运算得到数组下标;
- 如果数组下标元素为空，则将key和value封装成Node<K,V>并放入该位置
- 如果数组下标元素不为空:
- a.判断数组上该位置key是否相同，相同则执行覆盖操作，返回老的value值
- b.不相同，则判断该节点上Node的类型，判断是是红黑树或者是链表.
- i.如果是红黑树Node,则将key和value封装为一个红黑树节点并添加到红黑树中去，在这个过程中会判断红黑树中是否存在当前key,如果存在则更新value
- ii.如果是链表节点，则将key和value封装为一个链表Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否存在当前key,如果存在则更新value,当遍历完链表后，将新链表Node插入到链表中，插入到链表后，会看当前链表的节点个数，如果大于等于8，（数组长度大于64）那么则会将该链表转成红黑树
resize扩容
resize()
两个作用
初始化数组，扩容
/**
* resize() 有两个模式，1.初始化数组，2.扩容。
* 整体氛围两大步骤：
* 1）计算新数组大小，然后创建新数组
* 初始化 指定容量构造，newCap=threshold
* 未指定容量构造，newCap=16 扩容：newCap=oldCap * 2
*
* 2） 执行扩容策略：逐个遍历所有槽点，根据具体情况进行迁移
* 情况一：当前槽点只有一个node，直接重新分配到新数组即可newTab[e.hash & (newCap - 1)]
* 情况二：当前槽点下是红黑树
* 情况三：当前槽点下是链表：因为链表中所有node的hash和key相同，而现在数组扩容了两倍，所以现在的想法是将当前链等分成两部分
* 怎么等分成两部分？分成high链与low链，两链关系可近似理解为单双数节点 (e.hash & oldCap) == 0
* 怎么实现？hiHead、loHead 用来标识高低链，hiTail、loTail用来尾插新节点
* 两链放在新数组哪里？：low 链置于newTab[ j ]，high 链置于newTab[ j + oldCap ]（ j 表示在原来数组位置）
*/
当size大于threshold
执行模式有三种：初始化 扩容
扩容策略有三种：单点 红黑树 链表
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// threshold > 0 有两种情况
// 1.指定容量的初始化值，此时 oldCap = 0
// 2.扩容阈值，此时 oldCap != 0
int oldThr = threshold;
int newCap, newThr = 0;
// 模式一：oldCap>0表示要扩容
if (oldCap > 0) {
// 当老数组容量已达最大值时无法再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// Cap * 2 ， Thr * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 模式二：初始化，且已指定初始化容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 模式三：初始化，未指定初始化容量
else {
// 以默认初始化容量16进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
// 16 * 0.75 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 用指定容量初始化后，更新其扩容阈值
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
table = newTab;
//-------------------------------扩容策略-----------------------------------------------
// 若是执行的初始化，old=null，就不用走这里的扩容策略了，而是直接返回赋值去了
if (oldTab != null) {
// 遍历原数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 当原数组的当前槽点有值时,将其赋给e
if ((e = oldTab[j]) != 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);//当做链表处理，最后判断是否退化链表 小于6 否则树化
// 情况三：当前节点下是链表
else { // preserve order
// 将该链表分成两条链，low低位链 和 high高位链
// Head标识链头，Tail用来连接
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// do while((e = next) != null)
do {
next = e.next;
// 低位链连接
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 高位链连接
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将低位链放置于老链同一下标
// eg.原来当前节点位于oldTab[2],则现在低位链还置于newTab[2]
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将高位链放置于老链下标+oldCap
// eg.原来当前节点位于oldTab[2],则现在高位链置于newTab[2+8=10]
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Vector
默认构造器
public Vector() {
this(10);
}
get
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
add
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
remove
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
Hashtable
默认构造器
public Hashtable() {
this(11, 0.75f);
}
get
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;
}
put
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
remove
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}
Hashtable和HashMap的区别
HashMap是在JDK1.2中引入的Map的实现类。
Hashtable是JDK1.0就有的线程安全的类
两者的不同：
1.继承的父类不同
HashMap继承自AbstractMap类。但二者都实现了Map接口。
Hashtable继承自Dictionary类，Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。
2.HashMap线程不安全,HashTable线程安全
javadoc中关于hashmap的一段描述如下：此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
Hashtable 中的方法大多是Synchronize的，而HashMap中的方法在一般情况下是非Synchronize的。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步，但使用HashMap时就必须要自己增加同步处理。HashTable实现线程安全的代价就是效率变低，因为会锁住整个HashTable,而ConcurrentHashMap做了相关优化,因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定,效率比HashTable高很多。
HashMap底层是一个Entry数组，当发生hash冲突的时候，hashmap是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。
HashMap的put方法：
void addEntry(int hash, K key, V value, int bucketIndex) { //新增Entry,将“key-value”插入指定位置，bucketIndex是位置索引。
Entry<K,V> e = table[bucketIndex]; 保存“bucketIndex”位置的值到“e”中
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold) // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小2倍
resize(2 * table.length);
}
在hashmap的put方法调用addEntry()方法，假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。
故解决方法就是使用 使用ConcurrentHashMap。
这里要说一下 就是HashMap的迭代器(Iterator)是fail-fast迭代器，故当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException异常，而Hashtable的enumerator迭代器不是fail-fast的。但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
3.包含的contains方法不同
HashMap是没有contains方法的，而包括containsValue和containsKey方法；hashtable则保留了contains方法，效果同containsValue,还包括containsValue和containsKey方法。
4.是否允许null值
Hashmap是允许key和value为null值的，用containsValue和containsKey方法判断是否包含对应键值对；HashTable键值对都不能为空，否则包空指针异常。
5.计算hash值方式不同
为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。
①：HashMap有个hash方法重新计算了key的hash值,因为hash冲突变高，所以通过一种方法重算hash值的方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
注意这里计算hash值，先调用hashCode方法计算出来一个hash值，再将hash与右移16位后相异或，从而得到新的hash值。
②：Hashtable通过计算key的hashCode()来得到hash值就为最终hash值。
它们计算索引位置方法不同：
HashMap在求hash值对应的位置索引时，index = (n - 1) & hash。将哈希表的大小固定为了2的幂，因为是取模得到索引值，故这样取模时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。
HashTable在求hash值位置索引时计算index的方法：
int index = (hash & 0x7FFFFFFF) % tab.length;
&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号位改变，而后面的位都不变。
6.扩容方式不同（容量不够）
当容量不足时要进行resize方法，而resize的两个步骤：
①扩容；
②rehash:这里HashMap和HashTable都会会重新计算hash值而这里的计算方式就不同了（看5）；
HashMap 哈希扩容必须要求为原容量的2倍，而且一定是2的幂次倍扩容结果，而且每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入；
而Hashtable扩容为原容量2倍加1（在rehash中可以看到）；
7.解决hash冲突方式不同（地址冲突）
先看jdk8之前：
查找时间复杂度慢慢变高；
Java8，HashMap中，当出现冲突时可以：
1.如果冲突数量小于8，则是以链表方式解决冲突。
2.而当冲突大于等于8时，就会将冲突的Entry转换为**红黑树进行存储。**
3.而又当数量小于6时，则又转化为链表存储。
而在HashTable中， 都是以链表方式存储。
CopyOnWriteArrayList
读读
读写使用COW
写写使用锁
读不加锁
写加锁，并且CopyOnWrite进行复制到新数组，替换引用，
底层数组是volatile修饰，触发volatile语义，使得其他多的线程立即可见
高频面试题-Java 集合【java面试】:01 / CopyOnWriteArrayList
对于CopyOnWriteArrayList集合，正如它的名字所暗示的，它采用复制底层数组的方式来实现写操作。当线程对CopyOnWriteArrayList集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。**当线程对CopyOnWriteArrayList集合执行写入操作时，该集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。**由于对CopyOnWriteArrayList集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。
需要指出的是，由于CopyOnWriteArrayList执行写入操作时需要频繁地复制数组，性能比较差，但由于读操作与写操作不是操作同一个数组，而且读操作也不需要加锁，因此读操作就很快、很安全。由此可见，CopyOnWriteArrayList适合用在读取操作远远大于写入操作的场景中，例如缓存等。
COW技术的举例：
Redis的hash，渐进式rehash
Redis的RDB持久化：bgsave
子进程在写RDB文件时，父进程COW修改数据页
写时复制技术
改数据在复制数组中
读数据在旧数组中
读多写少场景：避免老是复制数组
读写是通过COW规避
读快照，写新数组
写写是通过加锁规避
package java.util.concurrent;
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//可重入锁
final transient ReentrantLock lock = new ReentrantLock();
//底层是[]
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));//复制的数组
}
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
//--------------------------------------------------------------------------------
//读的时候不加锁
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
return array;
}
//--------------------------------------------------------------------------------
//写的时候加锁
//加锁为了拷贝数组
//之后添加数据
//最后修改引用 触发volatile
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
//--------------------------------------------------------------------------------
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;//快照 迭代时
/** Index of element to be returned by subsequent call to next. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code remove}
* is not supported by this iterator.
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code set}
* is not supported by this iterator.
*/
public void set(E e) {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code add}
* is not supported by this iterator.
*/
public void add(E e) {
throw new UnsupportedOperationException();
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
Object[] elements = snapshot;
final int size = elements.length;
for (int i = cursor; i < size; i++) {
@SuppressWarnings("unchecked") E e = (E) elements[i];
action.accept(e);
}
cursor = size;
}
}
}
ConcurrentHashMap
1.7是一个HashMap拆为几个子HashMap，称为一个段
并发的就是初始的段的数量
1.8引入红黑树
每一个数组槽位是一个单位
高频面试题-Java 集合【java面试】:02 / ConcurrentHashMap
JDK 7中的实现方式：
为了提高并发度，在JDK7中，一个HashMap被拆分为多个子HashMap。每一个子HashMap称作一个Segment，多个线程操作多个Segment相互独立。在JDK 7中的分段锁，有三个好处：
- 减少Hash冲突，避免一个槽里有太多元素。
- 提高读和写的并发度，段与段之间相互独立。
- 提高了扩容的并发度，它不是整个ConcurrentHashMap一起扩容，而是每个Segment独立扩容。
分而治之思想
- 使用红黑树，当一个槽里有很多元素时，其查询和更新速度会比链表快很多，Hash冲突的问题由此得到较好的解决。
- 加锁的粒度，并非整个ConcurrentHashMap，而是对每个头节点分别加锁，即并发度，就是Node数组的长度，初始长度为16，和在JDK 7中初始Segment的个数相同。
- 并发扩容，这是难度最大的。在JDK 7中，一旦Segment的个数在初始化的时候确立，不能再更改，并发度被固定。之后只是在每个Segment内部扩容，这意味着每个Segment独立扩容，互不影响，不存在并发扩容的问题。但在JDK 8中，相当于只有1个Segment，当一个线程要扩容Node数组的时候，其他线程还要读写，因此处理过程很复杂。
初始化时
容量 cap=tableSizeFor(传入参数的1.5倍+1)
sizeCtl = cap;
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));//1.5倍 2的n次方
this.sizeCtl = cap;
}
sizeCtl的两个作用
调整控件
扩容的阈值：sizeCtl = (n << 1) - (n >>> 1)
//控制信号量
//阈值
/**
*表初始化和调整大小控件。
当为负值时表正在初始化或调整大小：
-1用于初始化，
else-(1+活动的调整大小线程的数量)。
否则
* 当table为null时，保留要使用的初始表大小创建，或默认为0。
初始化后，保持用于调整表大小的下一个元素计数值。
*/
private transient volatile int sizeCtl;
//transfer() 中
//sizeCtl = (n << 1) - (n >>> 1);
ConcurrentHashMap机制小结：
- 初始操作：以CAS方式初始化数组和头节点；
- 插入节点：在某位置插入节点时做加锁处理；
- 扩容操作：每个线程负责扩容一部分数据，扩容时做加锁处理。并且扩容时依然支持读写操作，若该位置的节点不是fwd则直接读写，否则就访问访问新数组进行读写。
AQS
说说你对AQS的理解
它是抽象的队列同步器，
AQS 核心思想是，如果被请求的共享资源空闲，则将当前请求资源的线程设置为有效的工作线程，并且将共享资源设置为锁定状态。如果被请求的共享资源被占用，那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制 AQS 是用 CLH 队列锁实现的，即将暂时获取不到锁的线程加入到队列中。
CLH(Craig,Landin,and Hagersten)队列是一个虚拟的双向队列（虚拟的双向队列即不存在队列实例，仅存在结点之间的关联关系）。AQS 是将每条请求共享资源的线程封装成一个 CLH 锁队列的一个结点（Node）来实现锁的分配
AQS 使用一个 int 成员变量来表示同步状态，通过内置的 FIFO 队列来完成获取资源线程的排队工作。
AQS 使用 CAS 对该同步状态进行原子操作实现对其值的修改。
private volatile int state;//共享变量，使用volatile修饰保证线程可见性
状态信息通过 protected 类型的 getState ， setState ， compareAndSetState 进行操作
模板方法模式实现架构
isHeldExclusively()//该线程是否正在独占资源。只有用到condition才需要去实现它。
tryAcquire(int)//独占方式。尝试获取资源，成功则返回true，失败则返回false。
tryRelease(int)//独占方式。尝试释放资源，成功则返回true，失败则返回false。
tryAcquireShared(int)//共享方式。尝试获取资源。负数表示失败；0表示成功，但没有剩余可用资源；
正数表示成功，且有剩余资源。
tryReleaseShared(int)//共享方式。尝试释放资源，成功则返回true，失败则返回false。
以 ReentrantLock 为例，state 初始化为 0，表示未锁定状态。A 线程 lock()时，会调用 tryAcquire()独
占该锁并将 state+1。此后，其他线程再 tryAcquire()时就会失败，直到 A 线程 unlock()到 state=0（即
释放锁）为止，其它线程才有机会获取该锁。当然，释放锁之前，A 线程自己是可以重复获取此锁的
（state 会累加），这就是可重入的概念。但要注意，获取多少次就要释放多么次，这样才能保证 state
是能回到零态的。
再以 CountDownLatch 以例，任务分为 N 个子线程去执行，state 也初始化为 N（注意 N 要与线程个
数一致）。这 N 个子线程是并行执行的，每个子线程执行完后 countDown()一次，state 会
CAS(Compare and Swap)减 1。等到所有子线程都执行完后(即 state=0)，会 unpark()主调用线程，然
后主调用线程就会从 await()函数返回，继续后余动作。
一般来说，自定义同步器要么是独占方法，要么是共享方式，他们也只需实现 tryAcquiretryRelease 、 tryAcquireShared-tryReleaseShared 中的一种即可。但 AQS 也支持自定义同步器同
时实现独占和共享两种方式，如 ReentrantReadWriteLock 。
Semaphore与CountDownLatch一样，也是共享锁的一种实现。它默认构造AQS的state为
permits。当执行任务的线程数量超出permits,那么多余的线程将会被放入阻塞队列Park,并自旋判断
state是否大于0。只有当state大于0的时候，阻塞的线程才能继续执行,此时先前执行任务的线程继续执
行release方法，release方法使得state的变量会加1，那么自旋的线程便会判断成功。
如此，每次只有最多不超过permits数量的线程能自旋成功，便限制了执行任务线程的数量。
CyclicBarrier 的字面意思是可循环使用（Cyclic）的屏障（Barrier）。它要做的事情是，让一组线程到
达一个屏障（也可以叫同步点）时被阻塞，直到最后一个线程到达屏障时，屏障才会开门，所有被屏障
拦截的线程才会继续干活。CyclicBarrier 默认的构造方法是 CyclicBarrier(int parties) ，其参数
表示屏障拦截的线程数量，每个线程调用 await 方法告诉 CyclicBarrier 我已经到达了屏障，然后当前
线程被阻塞。
再来看一下它的构造函数：
其中，parties 就代表了有拦截的线程的数量，当拦截的线程数量达到这个值的时候就打开栅栏，让所
有线程通过。
总结：CyclicBarrier 内部通过一个 count 变量作为计数器，cout 的初始值为 parties 属性的初始化
值，每当一个线程到了栅栏这里了，那么就将计数器减一。如果 count 值为 0 了，表示这是这一代最后
一个线程到达栅栏，就尝试执行我们构造方法中输入的任务。
ReentrantReadWtiteLock
实现
state使用高低位区分读锁 写锁的状态
//因为读锁和写锁使用的是同一个Sync，但是只有一个state，所以应该如何区分
//高16位存读锁 低16位存写锁
//统计读锁的个数 无符号右移16位 取出state高16位
static int sharedCount(int c) { return c >>> SHARED_SHIFT; }
//统计写锁的个数 按位与16个1 取出state低16位
static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
static final int SHARED_SHIFT = 16; //16位划分读锁和写锁的状态
static final int SHARED_UNIT = (1 << SHARED_SHIFT); //读锁的单位 状态+-
static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1;//锁最大的数量
static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;//取写锁的数量
ReentrantLock的特性：
绑定多个条件：newCondition
举例：ArrayBlockingQueue源码
目标：生产者通知消费者，消费者通知生产者。
避免：生产者通知生产者，消费者通知消费者。
//两个队列 两个Condition
private final Condition notEmpty;
private final Condition notFull;
如果是传统的synchronize，必须signalAll()
2023-7-26 09:27:15
最后
我们都有光明的未来
祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦