八股文之jdk源码分析
JDK源码分析
String
通过加号拼接字符串分析
string字符串我们一般都是字面量赋值形式，声明的变量值放在常量池，一般字符串拼接，通过+形式，其实这是jdk做了优化，并不是表面看到连接符，比如说现在字符串a,字符串b,通过反编译对应字节码文件，加号变成 new stringbuilder,append方法,String 是不可变的对象（final）, 因此在每次对 String 类型进行改变的时候其实都等同于在堆中生成了一个新的 String 对象，然后将指针指向新的 String 对象，这样不仅效率低下，而且大量浪费有限的内存空间，所以经常改变内容的字符串最好不要用 String 。因为每次生成对象都会对系统性能产生影响，特别是当内存中的无引用对象过多了以后， JVM 的 GC 开始工作，那速度是一定会相当慢的。另外当GC清理速度跟不上new String的速度时，还会导致内存溢出Error
list
ArrayList
初始化
重要属性
/**
* Default initial capacity. 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 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 = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* 数组列表的元素存储在数组缓冲区中。ArrayList的容量就是这个数组缓冲区的长度
* 任何带elementData的空数组列表== DEFAULTCAPACITY_EMPTY_ELEMENTDATA将在添加第一个元素时扩展为DEFAULT_CAPACITY。
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* 数组列表的大小
* @serial
*/
private int size;
构造方法
/**
* 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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
* 创建一个list初始容量10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
add方法
/**
* Appends the specified element to the end of this list.
* 追加元素在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!!增量 modCount
elementData[size++] = e;
return true;
}
/**
* 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++;
}
/**
* 确保是否是第一次添加元素，如果是list初始化容量
* 否则判断是否需要扩容
**/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 判断是否需要扩容
**/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 1.5倍扩容
* @param minCapacity the desired minimum capacity
*/
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);
}
详细说明
当容器ArrayList第一次添加元素，调用add(E)方法，首先是判断是否是第一次添加元素，如果是初始化数组容量10
如果不是第一次元素，则判断添加该元素之后，是否容量是否够用；
如果不够用的话，进行扩容操作，原来数组元素+原来数组右移一位，调用arrays.copyOf(elementData,newCapacity);
get方法
/**
* Returns the element at the specified position in this list.
* 返回数据指定位置的元素
* @param index index of the element to return 数组中索引位置
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
* 方法不检查索引是否为负数，它只检查索引是否大于或等于数组的长度。
* 如果索引是负数，则数组访问会抛出ArrayIndexOutOfBoundsException。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
详细说明
如果数组是个空数组，size 为 0 ，而你又去取第一个元素 get(0)，元素都没有，所以就会报错。
list根据指定位置获取元素，首先判断位置是否大于数组长度，如果大于抛出IndexOutOfBoundsException异常
否则返回指定位置的元素
remove方法
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
* 移除指定位置元素
* 将所有后续元素向左移动(从它们的元素中减去1)*指数)。
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
// 数组结构性变化 modCount++
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;
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
* 方法不检查索引是否为负数，它只检查索引是否大于或等于数组的长度。
* 如果索引是负数，则数组访问会抛出ArrayIndexOutOfBoundsException。
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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 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
}
详细说明
1、根据指定位置移除元素
首先判断指定位置是否合法，看它是否大于数组长度，如果大于抛出IndexOutOfBoundsException异常
否则，指定位置合适，之后modCount++,由于数组结构性变化，之后看一下移除元素之后是否需要
移动元素，计算数组长度-1-指定位置 如果大于0，通过
System.arraycopy(elementData, index+1, elementData, index, numMoved); 左移，否则最后一个元素，不需要移动位置，最后一个位置置为null,这样方便之后将整个数组不再使用时，会被GC，数组长度-1 2、根据元素删除 首先判断指定元素是否null,如果 不为null,遍历数组找到元素对应索引位置，指定位置合适，之后modCount++,由于数组结构性变化，之后看一下移除元素之后是否需要 移动元素，计算数组长度-1-指定位置 如果大于0，通过System.arraycopy方法左移，否则最后一个元素，不需要移动位置，最后一个位置置为null,这样方便之后将整个数组不再使用时，会被GC ，数组长度-1
set方法
/**
* Replaces the element at the specified position in this list with
* the specified element.
* 使用指定元素替换指定位置的内容
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
详细说明
首先判断指定位置是否合法，看它是否大于数组长度，如果大于抛出IndexOutOfBoundsException异常
否则，指定位置合适,直接赋值，返回老值
扩容grow方法
首先，对于ArrayList扩容，当调用无参构造new一个ArrayList时，此时size=0，数组为空。如果指定了数组大小的构造函数，或者是指定了collection元素的列表，这两个构造函数，初始值size就是自定义的了。
然后当执行add方法时，一定会先执行ensureCapacityInternal方法，参数叫做minCapacity(最小容量)=size+1。
/**
* Appends the specified element to the end of this list.
* 追加元素在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!!增量 modCount
elementData[size++] = e;
return true;
}
而ensureCapacityInternal（）函数里，还会计算一次最小容量，主要是给空参创建的加个默认容量，如果已经有容量了，不会进行更改。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
扩容核心方法grow
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 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;
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);
}
可以看到newCapacity=oldCapacity+(oldCapacity >> 1);也就是旧容量的1.5倍。奇数的话最后一位的1会被消去。但是，新容量大小还要经历两次判断，最后才会执行copyOf函数。
一是如果新容量小于最小所需容量，可以知道，这种情况旧容量太大导致数值溢出，newCapacity数值溢出，小于minCapacity了。
二是判断新容量是不是大于最大数组长度(默认是Integer.MAX_VALUE-8)，如果大于，就进到了这个函数
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
hugeCapacity的逻辑主要是判断最小所需容量是不是已经<0了，会报OOM异常，大概是minCapacity=size+1.size=Integer.MAX_VALUE才会出现这种情况。
然后判断minCapacity是不是大于最大数组长度，如果是，新容量=Interger.MAX_VALUE(如果再次扩容，就会跑到上面的判断逻辑了，再次扩容 size+1会成负数了)。
如果还没有大于最大数组长度，就会新容量=最大数组长度。
到此，新容量的计算就完成了，最后执行复制数组方法。扩容完成。
clear方法
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
遍历list,全部赋值null,不用的话让gc回收，最后数组长度变为0
modCount
问题复现
// 增强for循环 反编译之后发现是迭代器原型 ConcurrentModificationException
for (String item:list){
if("abc".equals(item)){
list.add("增强for循环添加元素");
}
}
// 增强型for循环反编译之后就是迭代器遍历的
System.out.println(list);
// 迭代器遍历添加元素 ConcurrentModificationException
Iterator<String> listIterator = list.iterator();
while (listIterator.hasNext()) {
if ("abc".equals(listIterator.next())) {
list.add("迭代器添加元素");
}
}
作用
Fail-Fast快速失败机制，遍历集合元素时候，如果集合结构发生了修改，立即抛出异常，以防止继续遍历。
记录了结构性改变的次数。结构性改变指的是那些修改了列表大小的操作，在迭代过程中可能会造成错误的结果。
解决方案
ListIterator<String> addListIterator = list.listIterator();
while (addListIterator.hasNext()){
if("胡一刀".equals(addListIterator.next())){
addListIterator.add("条小儿");
}
}
System.out.println("添加元素之后："+list);
// 方法二
for (int k = 0; k < list.size(); k++) {
if ("苗人凤".equals(list.get(k))) {
list.add( "10");
}
}
System.out.println(list);
线程安全问题
/**
* @Description 验证ArrayList多线程问题
*/
@Test
public void validListMultiThreads() throws InterruptedException {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 4; i++) {
new Thread(() -> {
for (int j = 0; j <= 10000; j++) {
list.add(new Random().nextInt(100));
}
}).start();
}
// 暂停线程的操作,精确到秒，线程暂停3秒，将其挂起
TimeUnit.SECONDS.sleep(3);
System.out.println("size = " + list.size());
for (int i = 0; i < list.size(); i++) {
if (null == list.get(i)) {
System.out.println("error==========");
}
}
System.out.println("over===========");
}
两个问题
数组越界?
前提条件: 当前size=2 数组长度为2.
1、线程1 判断数组是否越界.因为size=2 长度为2,没有越界.将进行赋值操作.但是因为时间片问题导致了中断.
2、线程2 判断数组是否越界.因为size=2 长度为2,没有越界.将进行赋值操作.但是因为时间片问题导致了中断.
3、线程1 重新获取到主动权.上文判断了长度刚刚好够用.进行赋值操作element[size]=1,并且size++
4、线程2 因为上文判断了数组没有越界.所以进行赋值操作.但是此时的size=3了.再执行element[3]=2. 导致了数组越界了.
数值为null?
线程1赋值操作element[0]=1,随后时间片用完了，中断，
线程2赋值操作element[0]=2,随后时间片用完了，中断
此处导致了之前所说的一个问题，后续线程将前面线程值覆盖了
线程1 自增 size++ size 2
线程2 自增 size size 3
此处导致了某些值为null的问题.因为原size=1, 但是因为线程1与线程2都将值赋值给了element[0],导致了element[1]内没有值,被跳过了.指针index指向了2.所以,导致了某些情况下值为null的情况.
解决方案一：同步
Collections.synchronizedList()方法其实底层也是在集合的所有方法之上加上了synchronized(默认使用的是同一个monitor对象，也可以自己指定)
public class UnsafeArrayList3 {
public static void main(String[] args) {
try {
notThreadSafe();
} catch (Exception e) {
e.printStackTrace();
}
}
public static void notThreadSafe() throws Exception{
final List<Integer> list = Collections.synchronizedList(new ArrayList<>());
for(int i=0;i<4;i++){
new Thread(()->{
for(int j=0;j<10000;j++){
list.add(new Random().nextInt(100));
}
}).start();
}
TimeUnit.SECONDS.sleep(3);
System.out.println("size = "+list.size());
for(int i=0;i<list.size();i++){
if(null == list.get(i)){
System.out.println("error==========");
}
}
System.out.println("over===========");
}
}
解决方案二：COW
Copy On Write 也是一种重要的思想，在写少读多的场景下，为了保证集合的线程安全性，我们完全可以在当前线程中得到原始数据的一份拷贝，然后进行操作。
JDK集合框架中为我们提供了 ArrayList 的这样一个实现：CopyOnWriteArrayList。但是如果不是写少读多的场景，使用 CopyOnWriteArrayList 开销比较大，因为每次对其更新操作（add/set/remove）都会做一次数组拷贝。
/**
* @Description 验证ArrayList多线程问题
*/
@Test
public void validListMultiThreads() throws InterruptedException {
List<Integer> list = new CopyOnWriteArrayList<>();
for (int i = 0; i < 4; i++) {
new Thread(() -> {
for (int j = 0; j <= 10000; j++) {
list.add(new Random().nextInt(100));
}
}).start();
}
// 暂停线程的操作,精确到秒，线程暂停3秒，将其挂起
TimeUnit.SECONDS.sleep(3);
System.out.println("size = " + list.size());
for (int i = 0; i < list.size(); i++) {
if (null == list.get(i)) {
System.out.println("error==========");
}
}
System.out.println("over===========");
}
CopyOnWriteArrayList
属性介绍
/** The lock protecting all mutators 保护所有变量的锁 */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray.
* 这个数组只能通过getArray和setArray访问设置
* 通过“volatile数组”来保存数据的。一个线程读取volatile数组时，总能看到其它线程对该volatile变量最后的写入；就这样，通过volatile提供了“读取到的数据总是最新的”这个机制的 保证
**/
private transient volatile Object[] array;
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return array;
}
/**
* Sets the array.
*/
final void setArray(Object[] a) {
array = a;
}
初始化，构造方法
/**
* @Description 无参构造
**/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
/**
* Creates a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection of initially held elements
* @throws NullPointerException if the specified collection is null
*/
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);
}
/**
* Creates a list holding a copy of the given array.
* 建一个包含给定数组副本的列表。
* @param toCopyIn the array (a copy of this array is used as the
* internal array)
* @throws NullPointerException if the specified array is null
*/
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
说明：setArray()的作用是给array赋值；其中，array是volatile transient
Object[]类型，即array是“volatile数组”。
关于volatile关键字，我们知道“volatile能让变量变得可见”，即对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入。正在由于这种特性，每次更新了“volatile数组”之后，其它线程都能看到对它所做的更新。
关于transient关键字，它是在序列化中才起作用，transient变量不会被自动序列化。
add
/**
* Appends the specified element to the end of this list.
* 将指定的元素追加到列表的末尾。
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
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();
}
}
1 加锁（synchronized ）。保证此时只有一个线程进入
2 获取原来的数组以及长度
3 复制新数据，并且长度+1
4 设置新数据（array使用volatile修饰，所以其他线程可见）
5 返回
get
//根据index直接获取数组元素
// 不加锁
public E get(int index) {
return elementAt(getArray(), index);
}
set
/**
* Replaces the element at the specified position in this list with the
* specified element.
* 将列表中指定位置的元素替换为指定元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
首先获取锁ReentrantLock，加锁，根据指定索引获取旧值，判断指定位置的新值与旧值是否相同，
不相同的话，数组拷贝，得到新数组新数组指定位置赋值操作，会通过将数据更新到volatile数组中
解锁
remove
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices). Returns the element that was removed from the list.
* 删除位于列表中指定位置的元素。
* 将所有后续元素向左平移(从它们的下标减去1)
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
首先获取同一把锁，看一下怎么移动元素，根据 numMoved = len - index -1 ,如果删除最后一个元素直接返回新数组，新数组包含
除了最后一个元素的所有，如果不是最后一个元素的话，分两步拷贝首先将指定元素之前的内容拷贝新数组，之后将指定元素之后
所有内容拷贝到新数组，新数组赋值，解锁
// 关于Arrays.copyOf 数组拷贝 int[] arr=new int[]{1,2,3,4,5}; int[] ints = Arrays.copyOf(arr, 3); for(int i=0;i<ints.length;i++){ System.out.println(ints[i]); } // 1 // 2 // 3 // System.arraycopy 数组拷贝 int[] newArr=new int[4]; // arr:源数组 srcPos:源数组开始位置0，newArr:目标数组，destPos:目标数组开始位置0，length:拷贝长度2 // 拷贝所删除元素前面的元素到新数组 System.arraycopy(arr,0,newArr,0,2); // newArr 1,2 // 拷贝所删除元素后面的元素到新数组 // arr:源数组 srcPos:源数组开始位置3，newArr:目标数组，destPos:目标数组开始位置2，length:拷贝长度2 System.arraycopy(arr,3,newArr,2,2); // for(int i=0;i<newArr.length;i++){ System.out.println(newArr[i]); }
遍历
/**
* Returns an iterator over the elements in this list in proper sequence.
* 返回一个迭代器，以正确的顺序遍历列表中的元素。
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
* {@code remove} method.
* 返回的迭代器提供了列表状态的快照 当迭代器被构造时。此时不需要同步
* 遍历迭代器。迭代器不支持remove方法
* {@code remove}方法。
* @return an iterator over the elements in this list in proper sequence
*/
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.
* 后续调用next返回的元素的索引
*/
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
public boolean hasNext() {
return cursor < snapshot.length;
}
}
对于遍历删除问题复现
System.out.println("遍历cowlist");
CopyOnWriteArrayList<Integer> cowList = new CopyOnWriteArrayList<Integer>() {{
add(1);
add(1);
add(1);
}};
Iterator<Integer> cowIterator = cowList.iterator();
while (cowIterator.hasNext()) {
if (1 == cowIterator.next()) {
cowIterator.remove();
}
}
对于remove方法
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code remove}
* is not supported by this iterator.
* 迭代器遍历同时不支持删除操作
*/
public void remove() {
throw new UnsupportedOperationException();
}
迭代器遍历同时修改，增加操作问题、
System.out.println("遍历cowlist");
CopyOnWriteArrayList<Integer> cowList = new CopyOnWriteArrayList<Integer>() {{
add(1);
add(1);
add(1);
}};
Iterator<Integer> cowIterator = cowList.iterator();
while (cowIterator.hasNext()) {
if (1 == cowIterator.next()) {
int j = cowList.indexOf(new Integer(1));
cowList.set(j,23);
// cowList.add(23);
// cowIterator.remove()
}
System.out.println(cowIterator.next());
}
基本原理
当向集合添加、移除元素时，并不是直接操作当前集合，而是首先对原集合进行拷贝、复制到一个新集合中。然后对该新集合进行添加、移除元素的操作。最后，再将对原集合的引用指向新集合即可。该机制的好处就在于当我们访问、读取集合是不需要加锁的，即COW机制是读写分离思想的具体体现。当然其弊端也是显而易见的，一方面由于写操作需要复制操作，所以对于较大规模的集合而言，其耗费的内存也是较为可观的；另一方面，由于读操作访问的是原集合，即使写操作在此期间已经完成。对于前者(读操作)而言也是不可见的，即其保证的是最终一致性
LinkedList
概述
（1）LinkedList底层维护了一个双向链表
（2）LinkedList中维护了两个属性first和last分别指向首节点和尾节点
（3）每个节点（Node对象）里又维护了prev（指向前一节点），next（指向后一节点），item（用于保存数据）三个属性，从而实现双链表
（4）因此元素的添加和删除效率较高
属性参数
transient int size = 0;//记录节点个数
transient Node<E> first;//first引用指向头节点
transient Node<E> last;//last引用指向尾节点
构造函数
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();//调用无参构造器
addAll(c);//批量插入方法
}
插入数据
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);//调用插入方法——addAll(int, Collection)
}
public boolean addAll(int index, Collection<? extends E> c) {//传入节点个数和初始化参数
checkPositionIndex(index);//检查下标合理性
Object[] a = c.toArray();//将c集合转换为Object数组a
int numNew = a.length;//记录数组长度
if (numNew == 0)//数组长度为0
return false;//返回false，初始化失败
Node<E> pred, succ;//声明该节点的前驱节点和后继节点
if (index == size) {//如果下标等于节点个数，即从尾部加入
succ = null;//后继节点置空
pred = last;//前驱节点指向老链表的last节点
} else {//从指定位置添加节点
succ = node(index);//后继节点指向原index处节点
pred = succ.prev;//前驱节点指向原index处节点的前驱节点
}
for (Object o : a) {//遍历存放c集合的数组a
@SuppressWarnings("unchecked") E e = (E) o;//向下转换
Node<E> newNode = new Node<>(pred, e, null);//新建节点存放元素
if (pred == null)//如果该节点的前驱节点为空，说明是头节点插入
first = newNode;//更新头节点
else
pred.next = newNode;//将前驱节点和新节点关联
pred = newNode;
}
if (succ == null) {//后继节点为空，说明尾部插入
last = pred;//尾节点更新
} else {//不为空
pred.next = succ;//newNode指向后继节点
succ.prev = pred;//后继节点指向newNode
}
size += numNew;//元素长度更新
modCount++;//操作次数++
return true;//插入成功
}
/**
* 判断下标合理性
**/
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))//若下标不合理，则抛出异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {//下标大于等于0且小于等于size返回true
return index >= 0 && index <= size;
}
获取元素 返回原链表中index的节点
Node<E> node(int index) {//二分法查找法
// assert isElementIndex(index);
if (index < (size >> 1)) {//index小于size的二分之一，从头节点开始查找
Node<E> x = first;//新建x指向first节点
for (int i = 0; i < index; i++)//找到原链表中下标为index的节点
x = x.next;
return x;//返回原链表中下标为index的节点
} else {//下标在后半部分，从尾节点开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
set
HashSet
变量以及参数
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
构造方法
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
* collection. The <tt>HashMap</tt> is created with default load factor
* (0.75) and an initial capacity sufficient to contain the elements in
* the specified collection.
*
* @param c the collection whose elements are to be placed into this set
* @throws NullPointerException if the specified collection is null
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* the specified initial capacity and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hash table
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
/**
* Constructs a new, empty linked hash set. (This package private
* constructor is only used by LinkedHashSet.) The backing
* HashMap instance is a LinkedHashMap with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy ignored (distinguishes this
* constructor from other int, float constructor.)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
add方法
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* this set contains no element <tt>e2</tt> such that
* <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 关键代码
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
...
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
* 如果指定的元素不存在，则将其添加到此集合
* 更正式一些,如果满足以下条件，则将指定的元素<tt>e</tt>添加到此集合。
* e == null ? e2 == null : e.equals(e2)
* 如果集合set包含该元素，返回false
contains方法
/**
* Returns <tt>true</tt> if this set contains the specified element.
* More formally, returns <tt>true</tt> if and only if this set
* contains an element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this set is to be tested
* @return <tt>true</tt> if this set contains the specified element
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
去重原理
1.Java中HashSet是用散列表实现的，散列表的大小默认为16，加载因子为0.75.
2.去重原理：当hashset add一个元素A的时候，首先获取这个元素的散列码（hashcode的方法），即获取元素的哈希值。
情况一：如果计算出的元素的存储位置目前没有任何元素存储，那么该元素可以直接存储在该位置上。
情况二：如果算出该元素的存储位置目前已经存在有其他元素了，那么会调用该元素的equals方法与该位置的元素再比较一次，如果equals返回的值是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素运行添加。
linkedhashset
/**
* Constructs a new, empty linked hash set with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity of the linked hash set
* @param loadFactor the load factor of the linked hash set
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
/**
* Constructs a new, empty linked hash set with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity of the LinkedHashSet
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
/**
* Constructs a new, empty linked hash set with the default initial
* capacity (16) and load factor (0.75).
*/
public LinkedHashSet() {
super(16, .75f, true);
}
/**
* Constructs a new linked hash set with the same elements as the
* specified collection. The linked hash set is created with an initial
* capacity sufficient to hold the elements in the specified collection
* and the default load factor (0.75).
*
* @param c the collection whose elements are to be placed into
* this set
* @throws NullPointerException if the specified collection is null
*/
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
map
HashMap
定位hash桶数组索引位置
&运算：按位与"&"功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1 ，否则为0
^运算：异或运算法则 如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0
初始化容量
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
* 将指定的值与映射中的指定键关联。如果映射之前包含一个键的映射，旧的值被替换。
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// hashCode() native修饰的底层c函数，最后返回hash值是hashcode与16高低异或操作
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化hash桶,table数组是延迟加载插入数据之后再进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
...省略
afterNodeInsertion(evict);
return null;
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// cap是capacity缩写，表示容量，如果容量不为空，说明已经开始初始化
if (oldCap > 0) {
// 如果容量达到最大 1<<30则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按照旧容量和阈值的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 { // zero initial threshold signifies using defaults
// 这一部分，源代码也有注释 初始阈值为零表示使用默认值
// 调用无参构造，数组table默认容量1<<4，左移4位16 1 * 2^4
newCap = DEFAULT_INITIAL_CAPACITY;
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 = newTab;
...省略
return newTab;
}
初始化过程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
putVal()方法
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断数组是否未初始化
if ((tab = table) == null || (n = tab.length) == 0)
//如果未初始化，调用resize方法 进行初始化
n = (tab = resize()).length;
//通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据
if ((p = tab[i = (n - 1) & hash]) == null)
//如果没有，直接将数据放在该下标位置
tab[i] = newNode(hash, key, value, null);
//该数组下标有数据的情况
else {
Node<K,V> e; K k;
//判断该位置数据的key和新来的数据是否一样
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到
e = p;
//判断是不是红黑树
else if (p instanceof TreeNode)
//如果是红黑树的话，进行红黑树的操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//新数据和当前数组既不相同，也不是红黑树节点，证明是链表
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//判断next节点，如果为空的话，证明遍历到链表尾部了
if ((e = p.next) == null) {
//把新值放入链表尾部
p.next = newNode(hash, key, value, null);
//因为新插入了一条数据，所以判断链表长度是不是大于等于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果是，进行转换红黑树操作
treeifyBin(tab, hash);
break;
}
//判断链表当中有数据相同的值，如果一样，证明为修改操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//把下一个节点赋值为当前节点
p = e;
}
}
//判断e是否为空（e值为修改操作存放原数据的变量）
if (e != null) { // existing mapping for key
//不为空的话证明是修改操作，取出老值
V oldValue = e.value;
//一定会执行 onlyIfAbsent传进来的是false
if (!onlyIfAbsent || oldValue == null)
//将新值赋值当前节点
e.value = value;
afterNodeAccess(e);
//返回老值
return oldValue;
}
}
//计数器，计算当前节点的修改次数
++modCount;
//当前数组中的数据数量如果大于扩容阈值
if (++size > threshold)
//进行扩容操作
resize();
//空方法
afterNodeInsertion(evict);
//添加操作时 返回空值
return null;
}
获取元素
(1)、先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。 (2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。
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;
//判断数组不为null并且长度大于0，并且通过hash算出来的数组下标的位置不为空，证明有数据
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断数组的位置的key的hash和内容是否等同与要查询的数据
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))))
//发现key的话就返回
return e;
} while ((e = e.next) != null);
}
}
//没有查询到返回null
return null;
}
扩容
向HashMap中添加数据时，有三个条件会触发它的扩容行为：
-
如果数组为空，则进行首次扩容。
-
将元素接入链表后，如果链表长度达到8，并且数组长度小于64，则扩容。
-
添加后，如果数组中元素超过阈值，即比例超出限制（默认为0.75），则扩容。
-
每次扩容时都是将容量翻倍，即创建一个2倍大的新数组，然后再将旧数组中的数组迁移到新数组里。由于HashMap中数组的容量为2^N，所以可以用位移运算计算新容量，效率很高。
5. 在数据迁移时，为了兼顾性能，不会重新计算一遍每个key的哈希值，而是根据位移运算后（左移翻倍）多出来的最高位来决定，如果高位为0则元素位置不变，如果高位为1则元素的位置是在原位置基础上加上旧的容量。
举个例子，来演示一下数据迁移时，元素在新数组里位置的判定。假设旧数组长度为16（00010000），则翻倍后新数组的长度为32（00100000）。我们从十进制数字上看不出什么，但是从二进制数字却可以看出二者的明显差别，即翻倍后新值的高位多了1。
如果我们把这两个值作为掩码，对key的哈希值做按位与运算，就能求出最高位那一位的差异。如果这一位是0则该元素的位置不变，否则该元素的位置就在原位置基础上加16。这个方式很巧妙，它省略了重新计算哈希值的时间，同时新增出来的一位是0或1是随机的，这样就把产生冲突的节点均匀的分散到新的槽里了。
//扩容、初始化数组
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//如果当前数组为null的时候，把oldCap老数组容量设置为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//老的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;
//判断数组容量是否大于0，大于0说明数组已经初始化
if (oldCap > 0) {
//判断当前数组长度是否大于最大数组长度
if (oldCap >= MAXIMUM_CAPACITY) {
//如果是，将扩容阈值直接设置为int类型的最大数值并直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果在最大长度范围内，则需要扩容 OldCap << 1等价于oldCap*2
//运算过后判断是不是最大值并且oldCap需要大于16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 等价于oldThr*2
}
//如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在， 如果是首次初始化，它的临界值则为0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//数组未初始化的情况，将阈值和扩容因子都设置为默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//初始化容量小于16的时候，扩容阈值是没有赋值的
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 = newTab;
//扩容操作，判断不为空证明不是初始化数组
if (oldTab != null) {
//遍历数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作
if ((e = oldTab[j]) != null) {
//将数组位置置空
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);
//有下个节点的情况，并且没有树化（链表形式）
else {
//比如老数组容量是16，那下标就为0-15
//扩容操作*2，容量就变为32，下标为0-31
//低位：0-15，高位16-31
//定义了四个变量
// 低位头 低位尾
Node<K,V> loHead = null, loTail = null;
// 高位头 高位尾
Node<K,V> hiHead = null, hiTail = null;
//下个节点
Node<K,V> next;
//循环遍历
do {
//取出next节点
next = e.next;
//通过 与操作 计算得出结果为0
if ((e.hash & oldCap) == 0) {
//如果低位尾为null，证明当前数组位置为空，没有任何数据
if (loTail == null)
//将e值放入低位头
loHead = e;
//低位尾不为null，证明已经有数据了
else
//将数据放入next节点
loTail.next = e;
//记录低位尾数据
loTail = e;
}
//通过 与操作 计算得出结果不为0
else {
//如果高位尾为null，证明当前数组位置为空，没有任何数据
if (hiTail == null)
//将e值放入高位头
hiHead = e;
//高位尾不为null，证明已经有数据了
else
//将数据放入next节点
hiTail.next = e;
//记录高位尾数据
hiTail = e;
}
//如果e不为空，证明没有到链表尾部，继续执行循环
} while ((e = next) != null);
//低位尾如果记录的有数据，是链表
if (loTail != null) {
//将下一个元素置空
loTail.next = null;
//将低位头放入新数组的原下标位置
newTab[j] = loHead;
}
//高位尾如果记录的有数据，是链表
if (hiTail != null) {
//将下一个元素置空
hiTail.next = null;
//将高位头放入新数组的(原下标+原数组容量)位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新的数组对象
return newTab;
}
链表树化
将单向链表转化为红黑树。树化操作主要发生在put操作中。
当链表长度超过8，且容量达到64时，触发树化
for (int binCount = 0; ; ++binCount) {
//这里是遍历到链表的最后一个
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/**
* 这里这个树化阈值的判断需要仔细琢磨一下
* 如果当前链表有八个节点，刚刚将newNode插入到了尾结点后面，也就是说
* 此时的newNode是链表中的第九个节点，此时才会进行树化
* 因为bitCount是从0开始的，也就是说bitCount为7的时候，才会树化，此时已经有了八个节点
* newNode再插进来，当然是第九个了
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/**
* 在遍历的过程中，如果找到相同的key，就退出遍历，进行覆盖
* 但是不是在这里覆盖， 在下面判断中进行的覆盖
* 可以整体看下这里的逻辑，如果进入到下面的if判断中，那此时就会中断for循环，这时 e != null
* 如果这里的if判断一直没有进去，那就会进入到上面 if((e = p.next) == null)的判断，也就是说，e == null
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
// 这是put方法中的部分代码，在当前插入的元素大于8个时，会进行树化
/**
* 链表转换红黑树，进行树化的目的是将链表中节点的查询效率提高
* 1.需要满足两个条件：数组不为空且hashmap数组的长度超过64，否则，只会进行扩容，不会进行树化
* 如果数组长度不超过64，就可以进行扩容，因为扩容之后，链表的长度就会变为一半
* 2.e表示的是数组中某个链表对应的头结点
* 2.1 do while循环，会把链表中每个node节点进行转换，转换成treeNode,然后将链表变成了双向链表，有prev和next，hd表示的是原链表的第一个节点，
* 2.2 然后根据hd进行真正的红黑树转换，hd就是红黑树初始化的根节点
*
* 所以：链表转红黑树，首先会把当前的单向链表，转换成双向链表，然后再拿着双向链表的头结点hd去进行红黑树的转换
*
* @param tab
* @param hash：待插入元素key值对应的hash
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
/**
* replacementTreeNode:把e这个node节点变为双向链表中的节点 treeNode
*
* e:是未转变红黑树之前链表的第一个节点
* hd:是e对应的treeNode
* tl:是一个动态变量，永远表示的是最后一个节点
*
* 所以下面的代码，是把原本的链表转换成了treeNode，我们姑且可以认为是双向链表
*/
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
/**
* 这里的treeify是将双向链表转换为红黑树，这里只需要入参双向链表的头节点就可以了
*/
hd.treeify(tab);
}
}
// 在treeifyBin方法中，会先把当前链表中的元素替换成双向链表，然后从tab[0]位置，依次向红黑树中添加元素
/**
* Forms tree of the nodes linked from this node.
* 红黑树的根节点如果发生了变化，就需要把变化之后的根节点放到双向链表的head
* 所以：我们可以认为：在树化之后，双向链表的头节点，就是红黑数的root节点，在每次向插入红黑树中插入数据之后，如果root节点发生了变化
* 同时会维护双向链表的节点
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
/**
* 这里会遍历前面维护好的的双向链表
*/
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
//首先将根节点的左右节点设置为null
x.left = x.right = null;
//把第一个hd，设置为root节点，默认是黑色的
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
/**
* 这里的x就是要插入到树中的元素
* 在每次插入到红黑树之前，是需要先判断当前要插入的节点是要插入到哪个位置？
* 父节点是谁？
*/
K k = x.key;
int h = x.hash;
Class<?> kc = null;
/**
* 遍历树中已经存在的节点，从root节点开始
*/
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
/**
* 如果新结点的hash值小于树中已经存在的树节点，就是-1；如果新结点的hash值大于树中的结点对应的hash，就是1，意思就是，-1往左插入，1往右插入
* 所以，判断当前节点是要插入到节点的左边还是右边，就是根据这里来判断的
* 如果root节点大于要插入的节点，那就是往左边插入，反之，向右边插入
*
* 所以：这里在判断dir的值时，有以下几个逻辑
* 1.先判断key的hash值，如果hash值相等，就进行下一步判断
* 2.再判断key是否实现了Comparable接口，如果实现了，就通过compareTo
* 去比较，如果比较的值还是相等，就执行下一步
* 3.调用tieBreakOrder
* 先判断k和pk对应的className是否一样
* 然后再判断identityHashCode对应的值
*
* 这里为什么要先判断hashCode，hashCode相等之后，在最后再调用System.identityHashCode()
* 是为了防止程序员自己重写hashCode方法，返回了固定值，比如：为重修额hashCode
* ，返回了1，那就区分不出来哪个key大 哪个key小了
*/
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
/**
* 这里是，根据上面的dir来进行遍历判断，for循环，一直找到最底层的孙子结点，判断条件就是p.left或者p.right为null，
* 就表示当前的p结点是最左边或者最右边的了 如果dir <= 0,就往左，否则 往右
*
*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
/**
* 我们可以理解为上面的逻辑就是为了找到当前要插入的x节点对应的parent
*
* 这是把x节点插入到红黑树中，并返回插入之后的root节点，因为有可能在插入X
* 节点之后，红黑树进行了平衡或者红黑颜色的转换，导致root节点变化
* 所以：这个方法就是把x插入到root节点，并进行平衡或者红黑转换的过程，最后会返回转换之后的root节点
*/
root = balanceInsertion(root, x);
break;
}
}
}
}
/**
* 下面这个方法中完成的操作：
* 1.把红黑树的根节点移到tab[i]
* 2.把root节点移到双向链表的第一个元素位置
* 这里是把跟结点移到tab[i]上，因为在红黑树转换的过程中，root结点是可能发生转换的
* 同时，把root结点对应的treeNode变成双线链表的头结点head,因为红黑树的root结点，很有可能是双向链表中的某个节点;要保证root的根节点对应的双线链表的头结点
*
*/
moveRootToFront(tab, root);
}
// 这个方法，我们可以简单认为，就做了两件事情
// 1、将当前要插入的节点，写入到红黑树中，就是最后一行前面的代码所做的事情
// 2、将当前最新的root节点，移动到双向链表的头部，就是最后一行代码做的事情
/**
* Ensures that the given root is the first node of its bin.
* 这个方法是把入参中的root节点，变为当前双向链表的root节点(头节点)
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
/**
* 如果root节点和tab[i]位置的元素不一样，就进行转换
*
* 这里有一个点没看懂：tab数组是当前hashmap的数组，为什么是从当前数组中
* 找到一个位置i对应的头结点？
*/
if (root != first) {
Node<K,V> rn;
// 将root节点赋值到tab[i]位置
tab[index] = root;
//rp是root节点的上一个节点（有可能进行转换之后，root节点在双向链表中间某个位置）
TreeNode<K,V> rp = root.prev;
//如果root节点不是最后一个节点，就把root下一个节点的prev指向root的前一个节点
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
//如果root的上一个节点不为null，就把上一个节点的next指向root的下一个节点
if (rp != null)
rp.next = rn;
//将现在tab[i]对应的元素设置为root的下一个节点，也就是把root节点放到first的前面
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
线程安全问题
https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653192000&idx=1&sn=118cee6d1c67e7b8e4f762af3e61643e&chksm=8c990d9abbee848c739aeaf25893ae4382eca90642f65fc9b8eb76d58d6e7adebe65da03f80d&scene=21#wechat_redirect
ConcurrentHashMap
https://blog.csdn.net/wwj17647590781/article/details/118151008?spm=1001.2014.3001.5501
构造器
不同种类的构造器
/**
* Creates a new, empty map with the default initial table size (16).
* 通过无参构造方法创建map,初始化容量为16
*/
public ConcurrentHashMap() {
}
/**
* Creates a new, empty map with an initial table size
* accommodating the specified number of elements without the need
* to dynamically resize.
* 指定初始容量的map，将指定的容量按照一定算法获取2的整数次幂
* @param initialCapacity The implementation performs internal
* sizing to accommodate this many elements.
* @throws IllegalArgumentException if the initial capacity of
* elements is negative
*/
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
/**
* Copies all of the mappings from the specified map to this one.
* These mappings replace any mappings that this map had for any of the
* keys currently in the specified map.
* 根据指定map创建chm
* @param m mappings to be stored in this map
*/
public void putAll(Map<? extends K, ? extends V> m) {
tryPresize(m.size());
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putVal(e.getKey(), e.getValue(), false);
}
/**
* Creates a new, empty map with an initial table size based on
* the given number of elements ({@code initialCapacity}) and
* initial table density ({@code loadFactor}).
*
* @param initialCapacity the initial capacity. The implementation
* performs internal sizing to accommodate this many elements,
* given the specified load factor.
* @param loadFactor the load factor (table density) for
* establishing the initial table size
* @throws IllegalArgumentException if the initial capacity of
* elements is negative or the load factor is nonpositive
* 指定table初始容量和负载因子的构造器
* @since 1.6
*/
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
/**
* Creates a new, empty map with an initial table size based on
* the given number of elements ({@code initialCapacity}), table
* density ({@code loadFactor}), and number of concurrently
* updating threads ({@code concurrencyLevel}).
* 指定table初始容量、负载因子、并发级别的构造器
* @param initialCapacity the initial capacity. The implementation
* performs internal sizing to accommodate this many elements,
* given the specified load factor.
* @param loadFactor the load factor (table density) for
* establishing the initial table size
* @param concurrencyLevel the estimated number of concurrently
* updating threads. The implementation may use this value as
* a sizing hint.
* @throws IllegalArgumentException if the initial capacity is
* negative or the load factor or concurrencyLevel are
* nonpositive
*/
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
常量
//最大容量.
private static final int MAXIMUM_CAPACITY = 1 << 30;
//默认初始容量
private static final int DEFAULT_CAPACITY = 16;
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//负载因子，为了兼容JDK1.8以前的版本而保留，JDK1.8中的ConcurrentHashMap的负载因子恒定为0.75
private static final float LOAD_FACTOR = 0.75f;
//链表--->树的阈值:即链接结点数大于8时， 链表转换为树.
static final int TREEIFY_THRESHOLD = 8;
//树--->链表的阈值:即树结点树小于6时，树转换为链表.
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 在链表--->树之前，还会有一次判断：
* 即只有键值对数量大于MIN_TREEIFY_CAPACITY，才会发生转换。
* 这是为了避免在Table建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 在树--->链表之前，还会有一次判断：
* 即只有键值对数量小于MIN_TRANSFER_STRIDE，才会发生转换.
*/
private static final int MIN_TRANSFER_STRIDE = 16;
//用于在扩容时生成唯一的随机数.
private static int RESIZE_STAMP_BITS = 16;
//可同时进行扩容操作的最大线程数.
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
/**
* The bit shift for recording size stamp in sizeCtl.
*/
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
/*
* hash值的意义
*/
static final int MOVED = -1; // 标识ForwardingNode结点（在扩容时才会出现，不存储实际数据）
static final int TREEBIN = -2; // 标识红黑树的根结点
static final int RESERVED = -3; // 标识ReservationNode结点（）
static final int HASH_BITS = 0x7fffffff; // 标识Node结点，自然数0，1，2...
//CPU核心数，扩容时使用
static final int NCPU = Runtime.getRuntime().availableProcessors();
字段
//Node数组，标识整个Map，首次插入元素时创建，大小总是2的幂次.
transient volatile Node<K, V>[] table;
//扩容后的新Node数组，只有在扩容时才非空.
private transient volatile Node<K, V>[] nextTable;
/**
* sizeCtl：控制table的初始化和扩容.很重要💦💦💦💦
* 0 : 初始默认值
* -1 : 有线程正在进行table的初始化
* >0 : table初始化时使用的容量，或初始化/扩容完成后的阈值threshold
* -(1 + nThreads) : 记录正在执行扩容任务的线程数
*/
private transient volatile int sizeCtl;
//扩容时需要用到的一个下标变量.
private transient volatile int transferIndex;
//计数基值,当没有线程竞争时，计数将直接加到该变量上。类似于LongAdder的base变量
private transient volatile long baseCount;
//计数数组，出现并发冲突时使用，这时候计数不能直接加到baseCount变量上，类似于LongAdder的cells数组
private transient volatile CounterCell[] counterCells;
// 自旋标识位，用于CounterCell[]扩容时使用。类似于LongAdder的cellsBusy变量
private transient volatile int cellsBusy;
// 视图相关字段
private transient KeySetView<K, V> keySet;
private transient ValuesView<K, V> values;
private transient EntrySetView<K, V> entrySet;
put方法源码分析
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
* 指定key,value,并且key,value都不能为null
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
* 可以通过调用该方法检索键值对
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/**
* @Description 实际的插入操作
* @param key 表示键值对=》键
* @param value 表示键值对=》值
* @param onlyIfAbsent true=>表示key不存在才进行插入操作
*
**/
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
// 使用链表保存时，binCount记录table[i]这个桶中所保存的结点数
// 使用红黑树保存时，binCount==2，保证put后更改计数值时能够进行扩容检查，同时不触发红黑树化操作
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();
// table[i]对应的桶为null，则直接插入结点
// tabAt(tab, i)方法是调用Unsafe类的方法查看值，保证每次获取到的值都是最新的
// table[i]的索引i的计算方式 (n - 1) & hash) 为什么这样计算
// 这是因为当table.length为2的幂次时，(table.length-1) 的二进制形式的特点是除最高位外全部是1，配合这种索引计算方式可以实现key在table中
// 的均匀分布 ，减少hash冲突——出现hash冲突时，结点就需要以链表或红黑树的形式链接到table[i]，这样无论是插入还是查找都需要额外的时间
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
// 插入一个链表结点，成功返回
break; // no lock when adding to empty bin
}
// 发现ForwardingNode结点（通过MOVED标识ForwardingNode结点存在），说明此时table正在扩容，则尝试协助数据迁移
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 出现hash冲突,也就是table[i]桶中已经有了结点
else {
V oldVal = null;
// 对table[i]结点上锁，避免并发情况
synchronized (f) {
// 再判断一下节点 是不是在这个 table[i]上
if (tabAt(tab, i) == f) {
// fh >= 0--->table[i]是链表结点
if (fh >= 0) {
// 记录结点数，超过阈值后，需要转为红黑树，提高查找效率
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 找到“相等”的结点，判断是否需要更新value值（onlyIfAbsent为false则可以插入）
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 记录key冲突的原来对应的value值
oldVal = e.val;
// onlyIfAbsent标志仅当不存在时才插入
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;
}
}
}
// 继续判断table[i]是不是红黑树结点
else if (f instanceof TreeBin) {
Node<K,V> p;
// 红黑树对应的基值，包括了treebin和root，所以以2为基础
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 超过阈值，链表 -> 红黑树 转换
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 表明本次操作增加了新值， 计数值加1
addCount(1L, binCount);
return null;
}
/**
* @Description 计算hash值的方法，防止并发情况
**/
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
/**
* Initializes table, using the size recorded in sizeCtl.
* 初始化table, 使用sizeCtl作为初始化容量.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// transient volatile Node<K,V>[] table;
// Node数组，标识整个Map，首次插入元素时创建，大小总是2的幂次.
// 自旋直到初始化成功（每次循环都获取最新的Node数组引用）
while ((tab = table) == null || tab.length == 0) {
// sizeCtl<0 ：说明table已经正在初始化/扩容，所以让出CPU时间片
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// 将sizeCtl更新成-1,表示正在初始化中
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// 如果CAS操作成功了，代表本线程将负责初始化工作
try {
// 再次检查table数组是否为空
if ((tab = table) == null || tab.length == 0) {
// 在初始化Map时，sizeCtl代表数组大小，默认16，所以此时n默认为16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 创建容量为16 node数组
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// n - (n >>> 2) = n - n/4 = 0.75n = 12
// 相当于设置了阈值threshold
sc = n - (n >>> 2);
}
} finally {
// 将计算后的sc=12直接赋值给sizeCtl，表示达到12长度就扩容,由于这里只会有一个线程在执行，直接赋值即可，没有线程安全问题
// 只需要保证可见性
sizeCtl = sc;
}
break;
}
}
return tab;
}
/**
* 更改计数值，并检查长度是否达到阈值
*/
private final void addCount(long x, int check) {
// 计数桶 as
CounterCell[] as; long b, s;
// !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)：尝试更新baseCount
// 如果counterCells不为null，则代表已经初始化了，直接进入if语句块
// 若竞争不严重，counterCells有可能还未初始化，为null，先尝试CAS操作递增baseCount值
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// 进入此语句块有两种可能：
// 1.counterCells被初始化完成了，不为null
// 2.CAS操作递增baseCount值失败了，说明出现并发冲突,则将计数值累加到Cell槽
CounterCell a; long v; int m;
// 标志是否存在竞争
boolean uncontended = true;
//1.先判断计数桶是否初始化,如果as=null，说明没有，进入语句块
//2.判断计数桶长度是否为空，若是进入语句块
//3.这里做了一个线程变量随机数，若桶的这个位置为空，进入语句块（根据线程hash值计算槽索引）
//4.到这里说明桶已经初始化了，且随机的这个位置不为空，尝试CAS操作使桶加1，失败进入语句块
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
// 检测是否扩容
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
/**
* 当出现了并发冲突，则不会再用CAS方式来计数了，直接使用桶方式，
* 从上面的addCount方法可以看出来，此时的countCell是为空的(或者不为空但CAS更新失败)，最终一定会进入fullAddCount方法来进行初始化桶
**/
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
...
//如果计数桶!=null，证明已经初始化，此时不走此语句块
if ((as = counterCells) != null && (n = as.length) > 0) {
...
}
//进入此语句块进行计数桶的初始化
//CAS设置cellsBusy=1，表示现在计数桶Busy中...
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
//若有线程同时初始化计数桶，由于CAS操作只有一个线程进入这里
boolean init = false;
try { // Initialize table
//再次确认计数桶为空
if (counterCells == as) {
//初始化一个长度为2的计数桶👌👌
CounterCell[] rs = new CounterCell[2];
//h为一个随机数，与上1则代表结果为0、1中随机的一个
//也就是在0、1下标中随便选一个计数桶，x=1，放入1的值代表增加1个容量
rs[h & 1] = new CounterCell(x);
//将初始化好的计数桶赋值给ConcurrentHashMap
counterCells = rs;
init = true;
}
} finally {
//最后将busy标识设置为0，表示不busy了
cellsBusy = 0;
}
if (init)
break;
}
//若有线程同时来初始化计数桶，则没有抢到busy资格的线程就先来CAS递增baseCount
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
扩容机制
linkedhashmap
https://blog.csdn.net/qq_40050586/article/details/105851970
概述
LinkedHashMap和HashMap的存储结构基本相同，都是数组加链表。唯一不同的是，链表结点有两个指针，分别是before和after，指向该结点的直接后继和直接前驱，再通过双向链表表头结点，就可以实现从双向链表中的任意一个结点开始，很方便地访问它的前驱结点和后继结点。LinkedHashMap采用的hash算法和HashMap相同，但它扩展了Entry（结点，用于存储key和value）。LinkedHashMap中的Entry增加了 before 和 after两个指针，用于维护双向链表。
构造函数
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 构造一个空的，按插入序（accessOrder = false）的LinkedHashMap，使用默认初始大小和负载因子0.75
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 默认构造函数也是关闭了get改变顺序，使用插入序。
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
* the same mappings as the specified map. The <tt>LinkedHashMap</tt>
* instance is created with a default load factor (0.75) and an initial
* capacity sufficient to hold the mappings in the specified map.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
/**
* 这个构造方法指定了accessOrder
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
维护链表关键
afterNodeRemoval，afterNodeInsertion，afterNodeAccess。这三个方法的主要作用是，在删除，插入，获取节点之后，对链表进行维护。简单来说，这三个方法中执行双向链表的操作
//在节点删除后，维护链表，传入删除的节点
void afterNodeRemoval(Node<K,V> e) { // unlink
//p指向待删除元素，b执行前驱，a执行后驱
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//这里执行双向链表删除p节点操作，很简单。
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
//在节点被访问后根据accessOrder判断是否需要调整链表顺序
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//如果accessOrder为false，什么都不做
if (accessOrder && (last = tail) != e) {
//p指向待删除元素，b执行前驱，a执行后驱
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//这里执行双向链表删除操作
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
//这里执行将p放到尾部
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
//保证并发读安全。
++modCount;
}
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//removeEldestEntry(first)默认返回false，所以afterNodeInsertion这个方法其实并不会执行
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
为什么不执行也可以呢，这个要到put操作的时候就能看出来了。
那么removeEldestEntry这个方法有什么用呢，看名字可以知道是删除最久远的节点，也就是head节点，这个方法实际是给我们自己扩展的。默认是没有用的，接下来实现LRU的代码中将可以看到它的作用。
put源码分析
LinkedHashMap没有重写HashMap的put方法，所以执行put操作的时候，还是使用的是HashMap的put方法。那么这样如何保证链表的逻辑呢？原因就是HashMap的putVal方法中实际调用了维护链表的方法，下面是关键代码：HashMap的putVal()方法
//默认的传入的evict是true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
................
................
................
................
if (e != null) { // existing mapping for key
//如果e不为null，此时的e指向的就是在map中的那个插入点，所以这个时候来赋值。
V oldValue = e.value;
// onlyIfAbsent入口参数，为true，则不更新value（前面已说明）。
//这个地方的主要作用主要控制如果map中已经有那个key了，是否需要需要更新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这里其实是插入成功后执行的，获得的效果就是将e放到了链表结尾。
//所以afterNodeInsertion方法就算什么都不做也可以。
//但是如果accessOrder为false，那么我们新插入的节点，都不会进入链表了
afterNodeAccess(e);
return oldValue;
}
}
//fast-fail机制的实现，为了保证并发读安全。
++modCount;
//容器中的键值对数自增，如果大于了阈值，开始扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
在put方法中，HashMap会在合适的位置使用 afterNodeAccess(e)，和afterNodeInsertion(evict);方法。因为在HashMap中也定义了这三个函数，但是都是为空函数，在LInkedHashMap中只是重写了这3个方法。我们在使用map.put(key,value)的时候，实际调用HashMap#putVal(key,value)方法，然后再调用afterNodeAccess方法，那么这个时候调用的会是子类的afterNodeAccess方法吗？
这个就要涉及到多态的知识了，可以从虚拟机方面去解释：在虚拟机加载类的解析过程中，对方法调用有两种分派方式，静态分派对应重载，动态分派对应重写。这里对应的就是动态分派。动态分配是在运行时发生的，它对于方法是按照实际类型来首先寻找的。找不到再往父类走。这里的实际类型其实值new 后面跟着的类。所以这里不用担心会调用到父类的方法。
afterNodeInsertion方法不是没有用，而是留给扩展用的，下面会展示。
还有一点，put操作中使用afterNodeAccess来将新插入的节点放到尾部。但是这个方法要受到accessOrder的控制，如果accessOrder为false（默认就为false）那么新插入的节点应该就不能插入到链表中了。这样设计有什么特殊的意义吗？
get源码分析
LinkedHashMap重写了HashMap的get方法，如下：
/**
* 调用hashmap的getNode方法获取到值之后，维护链表
* @param key
* @return
*/
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
remove源码分析
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;
//判断table是否为空，该key对应的桶是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
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就已经指向了要删除的节点了
//matchValue的作用是指现在是否需要值匹配。因为可能没有传入value，所以判断一下
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;
}
实现LRU算法缓存
LRU，即最近最少使用。LRU中保存的数据如果满了，那么就会将最近最少使用的数据删除。
LinkedHashMap通过使accessOrder为true，可以满足这种特性。
class LRUCache extends LinkedHashMap {
private int capacity;
public LRUCache(int capacity) {
//accessOrder为true
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return (int)super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
}
力扣算法LRU
这里重写了removeEldestEntry方法，然后removeEldestEntry方法在afterNodeInsertion中被调用，如果这个方法返回真，那么就会删除head指向的节点。根据每次get的节点都会放到尾部的特性，所以head指向的节点就是最久没有使用到的节点，所以可以删除。由于我们每次put完（HashMap#putVal()）都会调用这个afterNodeInsertion方法，所以可以上面的设计可以使put过后如果size超了，将删除最久没有使用的一个节点，从而腾出空间给新的节点。
总结
一句话总结，LinkedHashMap就是HashMap中将其node维护成了一个双向链表。只要搞懂了HashMap就可以很容易搞懂LinkedHashMap。
TreeMap
概念理解
TreeMap集合是基于红黑树（Red-Black tree）的 NavigableMap实现。该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。这句话是什么意思呢？就是说TreeMap可以对添加进来的元素进行排序，可以按照默认的排序方式，也可以自己创建排序器放入构造方法指定排序方式。
根据上一条，我们要想使用TreeMap存储并排序我们自定义的类（如User类），那么必须自己定义比较机制：一种方式是User类去实现java.lang.Comparable接口，并实现其compareTo()方法。另一种方式是写一个类（如MyCompatator）去实现java.util.Comparator接口，并实现compare()方法，然后将MyCompatator类实例对象作为TreeMap的构造方法参数进行传参（当然也可以使用匿名内部类）
类名及类成员变量
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 比较器对象
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 集合大小
private transient int size = 0;
// 树结构被修改的次数
private transient int modCount = 0;
// 静态内部类用来表示节点类型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // 键
V value; // 值
Entry<K,V> left; // 指向左子树的引用（指针）
Entry<K,V> right; // 指向右子树的引用（指针）
Entry<K,V> parent; // 指向父节点的引用（指针）
boolean color = BLACK; //
}
}
构造方法
public TreeMap() { // 1,无参构造方法
comparator = null; // 默认比较机制
}
public TreeMap(Comparator<? super K> comparator) { // 2，自定义比较器的构造方法
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) { // 3，构造已知Map对象为TreeMap
comparator = null; // 默认比较机制
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) { // 4，构造已知的SortedMap对象为TreeMap
comparator = m.comparator(); // 使用已知对象的构造器
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
put方法
public V put(K key, V value) {
Entry<K,V> t = root; // 获取根节点
// 如果根节点为空，则该元素置为根节点
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1; // 集合大小为1
modCount++; // 结构修改次数自增
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator; // 比较器对象
// 如果比较器对象不为空，也就是自定义了比较器
if (cpr != null) {
do { // 循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
parent = t; // t就是root
// 调用比较器对象的compare()方法，该方法返回一个整数
cmp = cpr.compare(key, t.key);
if (cmp < 0) // 待插入元素的key"小于"当前位置元素的key，则查询左子树
t = t.left;
else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树
t = t.right;
else // "相等"则替换其value。
return t.setValue(value);
} while (t != null);
}
// 如果比较器对象为空，使用默认的比较机制
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key; // 取出比较器对象
do { // 同样是循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
parent = t;
cmp = k.compareTo(t.key); // 同样调用比较方法并返回一个整数
if (cmp < 0) // 待插入元素的key"小于"当前位置元素的key，则查询左子树
t = t.left;
else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树
t = t.right;
else // "相等"则替换其value。
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent); // 根据key找到父节点后新建一个节点
if (cmp < 0) // 根据比较的结果来确定放在左子树还是右子树
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++; // 集合大小+1
modCount++; // 集合结构被修改次数+1
return null;
}
getEntry，getFirstEntry，getLastEntry方法
final Entry<K,V> getEntry(Object key) {
// 如果有自定义比较器对象，就按照自定义规则遍历二叉树
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) { // 按照默认比较规则遍历二叉树
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
final Entry<K,V> getFirstEntry() { // 获取第一个元素也就是最小的元素，一直遍历左子树
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
final Entry<K,V> getLastEntry() { // 获取最后个元素也就是最大的元素，一直遍历右子树
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
排序方案
默认排序
/**
* 验证有序集合
*/
@Test
public void checkSortCollection() {
// 默认排序，通过Comparable接口中compareTo方法
log.info("默认排序，key是字符串类型");
TreeMap<String, Object> map = new TreeMap<>();
map.put("c", "v1");
map.put("b", "v3");
map.put("A", "v2");
map.forEach((i, j) -> log.info("map:key->[{}],value:[{}]", i, j));
log.info("默认排序，key是数值类型");
TreeMap<Integer, Object> intMap = new TreeMap<>();
intMap.put(11,"Three");
intMap.put(1,"One");
intMap.put(3,"Two");
intMap.forEach((k,v)->log.info("key:[{}],value:[{}]",k,v));
}
16:05:32.535 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - 默认排序，key是字符串类型
16:05:32.600 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - map:key->[A],value:[v2]
16:05:32.602 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - map:key->[b],value:[v3]
16:05:32.602 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - map:key->[c],value:[v1]
16:05:32.602 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - 默认排序，key是数值类型
16:05:32.603 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - key:[1],value:[One]
16:05:32.603 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - key:[3],value:[Two]
16:05:32.603 [main] INFO com.geekmice.staging.staging.dao.EveryQuestionTest - key:[11],value:[Three]
自定义排序
实现Comparable接口，重写compareTo()方法
@Data
@AllArgsConstructor
@NoArgsConstructor
static class School implements Comparable<School> {
private String schoolName;
private String schoolAddr;
private Integer num;
/**
* 实现Comparable接口在这里自定义排序规则
* 如果什么不写的话，默认返回return 0;只能存储第一个被put的元素
* 升序这个写法
*
* @param o
* @return
*/
@Override
public int compareTo(School o) {
if (num > o.getNum()) {
return 1;
} else if (num < o.getNum()) {
return -1;
}
return 0;
}
}
案例说明
/**
* 验证有序集合
*/
@Test
public void checkSortCollection() {
log.info("自定义排序之key实现Comparable接口");
TreeMap<School, Integer> customizeKeyMap = new TreeMap<>();
customizeKeyMap.put(new School(UUID.randomUUID().toString(),UUID.randomUUID().toString(),10),1);
customizeKeyMap.put(new School(UUID.randomUUID().toString(),UUID.randomUUID().toString(),11),1);
customizeKeyMap.put(new School(UUID.randomUUID().toString(),UUID.randomUUID().toString(),1),1);
customizeKeyMap.forEach((k,v)->log.info("key:[{}],value:[{}]",k,v));
}
创建排序器
static class MyComparator implements Comparator<School> {
@Override
public int compare(School o1, School o2) {
if (o1.getNum() > o2.getNum()) {
return 1;
} else if (o1.getNum() < o2.getNum()) {
return -1;
}
return 0;
}
}
案例分析
/**
* 验证有序集合
*/
@Test
public void checkSortCollection() {
log.info("自定义排序之创建排序器实现Comparator接口");
MyComparator myComparator = new MyComparator();
TreeMap<School, Integer> customizeComparator = new TreeMap<>(myComparator);
customizeComparator.put(new School(UUID.randomUUID().toString(),UUID.randomUUID().toString(),1),1);
customizeComparator.put(new School(UUID.randomUUID().toString(),UUID.randomUUID().toString(),-1),1);
customizeComparator.put(new School(UUID.randomUUID().toString(),UUID.randomUUID().toString(),11),1);
customizeComparator.forEach((k,v)->log.info("key:[{}],value:[{}]",k,v));
}
ConcurrentHashMap是如何实现线程安全的
大厂之路一由浅入深、并行基础、源码分析一 “J.U.C”之collections框架：ConcurrentHashMap扩容迁移等方法的源码分析
超详细LinkedHashMap解析
HashSet的去重原理—Java基础