第13章_集合源码

1.ArrayList源码分析

1.1ArrayList概述

ArrayList 的底层是一个基于数组实现的动态数组，其能够根据扩容机制能够实现容量的动态增长。

1.2类声明

ArrayList类的声明如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ....
}        

• List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
• RandomAccess 是一个标志接口（Marker），支持快速随机访问（通过元素序号快速获取元素对象 —— get(int index)）
• Cloneable ：实现浅克隆（clone()）
• java.io.Serializable ：ArrayList 支持序列化

继承树结构如下：

1.3属性

ArrayList属性如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
    *序列化id
    */
    private static final long serialVersionUID = 8683452581122892189L;

    /**
    * 默认容量大小为10
    */
    private static final int DEFAULT_CAPACITY = 10;

	/**
    * 指定 ArrayList 容量为0（空实例）时，返回此空数组
    */
    private static final Object[] EMPTY_ELEMENTDATA = {};

  	/**
    * 与 EMPTY_ELEMENTDATA 的区别是，它是默认返回的，而前者是用户指定容量为 0 才返回
    */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   	/**
    * 存放元素的Object类型的数组，用transient修饰，不可被序列化
    */
    transient Object[] elementData; 

     /**
  	* ArrayList 实际所含元素个数（大小）
  	*/
    private int size;
    
    /**
    * 最大数组容量为 Integer.MAX_VALUE – 8
    */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

1.4构造函数

ArrayList 提供了 1 个无参构造和 2 个带参构造来初始化 ArrayList ，我们在创建 ArrayList 时，经常使用无参构造的方式，其本质就是初始化了一个空数组，直到向数组内真的添加元素的时候才会真的去分配容量。例如：向数组中添加第一个元素，数组容量扩充为 10。这样做可以延迟数组的创建，节省内存空间。

补充：JDK1.7 无参构造初始化 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组elementData。

1. 含有int类型参数的构造函数

• 如果传入参数也就是初始容量大于0，则新建一个初始容量大小的数组
• 如果传入的参数初始容量等于0，将 EMPTY_ELEMENTDATA 赋值给 elementData
• 如果传入的参数初始容量小于0，将抛出异常

/**
* 带参构造函数，参数为用户指定的初始容量
*/
public ArrayList(int initialCapacity) {
    	//如果初始化容量大于0
        if (initialCapacity > 0) {
            //新建一个初始化容量大小的Object类型数组
            this.elementData = new Object[initialCapacity];
        //如果初始化为0    
        } else if (initialCapacity == 0) {
            //将EMPTY_ELEMENTDATA属性赋值给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 否则初始容量小于0，则抛出异常 “非法的容量”
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

2. 无参构造

• 如果没有传入参数，则使用默认无参构建方法创建 ArrayList 对象。elementData 是一个大小为 0 的空数组

/**
* 无参构造。没有指定初始容量，将成员变量elementData的值设为默认值
*/
public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

3. 含有Collection<? extends E> 类型的参数的构造函数

• 表示传入的集合中的元素只能是 E 及其子类的对象
• 将参数中的集合转换为数组，赋值给 elementData
• 给 size 进行赋值，size 代表集合元素数量。判断参数是否为空，如果数组的大小不等于 0，则进一步判断是否转化为 Object 类型的数组，如果不是，则进行复制，并赋值给elementData
• 否则，设置元素数组为空数组

/**
* 接受一个集合参数，表示传入的集合中的元素只能是 `E` 及其子类的对象
*/
   public ArrayList(Collection<? extends E> c) {
       // 将参数中的集合转换为数组，赋值给 elementData 
       elementData = c.toArray();
       // 如果数组的大小不等于 0
       if ((size = elementData.length) != 0) {
            // 如果c.toArray()返回的数组类型不是Object[]类型的
       	// 则利用Arrays.copyOf()创建一个大小为size的、类型为Object[]的数组, 并将elementData中的元素复制到新的数组中
       	// 最后让elementData 指向新的数组
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
           //如果数组的大小等于0，则设置为空数组
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }

1.5最小实例化容量方法

• 将 ArrayList 实例的容量调整为列表的当前大小，作用是减少 ArrayList 实例占用的内存空间，使其仅占用与当前元素数量相当的空间。

    /**
 	  * 最小化实例容量方法，可以根据实际元素个数，将数组容量优化，防止浪费
	  */
public void trimToSize() {
       //modCount 的值加一，表示对列表进行了结构修改
       modCount++;
       //检查列表的大小 size 是否小于数组 elementData 的长度
       if (size < elementData.length) {
           //使用三目运算符判断 size 是否为零。
           //如果为零，则将 elementData 赋值为空数组；
           //否则，使用 Arrays.copyOf 方法将 elementData 复制为一个新的长度为 size 的数组。
           elementData = (size == 0)
             ? EMPTY_ELEMENTDATA
             : Arrays.copyOf(elementData, size);
       }
   }

1.6常用方法解析

/**
 * 返回数组中元素数量
 */
public int size() {
    return size;
}

/**
 * 判断数组中元素是否为空，此列表元素数量为 0 则返回 true
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * 此列表含有指定元素，则返回true
 */
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * 返回此列表中元素首次出现位置的索引
 * 若不包含此元素，则返回 -1
 */
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        // 本质就是循环 equals 比对
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

/**
 * 返回此列表中指定元素的最后一次出现的索引
 * 如果此列表不包含元素，则返回 -1
 */
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        // 逆向循环 equals 比对
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}


/**
 * 返回 ArrayList 实例的浅拷贝
 */
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 实现数组的复制，参数为被复制者的参数
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

/**
 * 返回一个包含此列表中所有元素的数组（理解为将集合转为数组即可）
 */
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

/**
 * 将list转化为你所需要类型的数组，然后返回
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // 复制用法
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

// Positional Access Operations

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

/**
 * 返回此列表中指定位置的元素。
 */
public E get(int index) {
    // index 范围检查
    rangeCheck(index);
    return elementData(index);
}

/**
 * 用指定的元素替换此列表中指定位置的元素。
 */
public E set(int index, E element) {
    // index 范围检查
    rangeCheck(index);
    // 根据 index 找到想替换的旧元素
    E oldValue = elementData(index);
    // 替换元素
    elementData[index] = element;
    return oldValue;
}

/**
 * 将指定的元素追加到此列表的末尾。
 */
public boolean add(E e) {
    // 确认 list 容量，尝试容量加 1，看看有无必要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 赋值
    elementData[size++] = e;
    return true;
}

/**
 * 在此列表中的指定位置插入指定的元素
 * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
 */
public void add(int index, E element) {
    // 调用 rangeCheckForAdd 对 index 进行范围检查
    rangeCheckForAdd(index);
    // 保证容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 自己复制自己，index 之后全部元素向后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 然后将 index 赋值为指定的元素
    elementData[index] = element;
    size++;
}

/**
 * 移除该列表中指定位置的元素。 将后续元素向前移动一位（从其索引中减去一个元素）。
 */
public E remove(int index) {
    // 调用 rangeCheckForAdd 对 index 进行范围检查
    rangeCheck(index);
    modCount++;
    // 找到待移除的值
    E oldValue = elementData(index);
    // 计算出需要移动元素的数量
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将 index + 1 及其后面的元素向前移动一位，覆盖被删除的元素值
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 把数组最后一个元素赋值为null，将元素个数减一
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

/**
 * 从集合中移除第一次出现的指定元素
 */
public boolean remove(Object o) {
    //判断查找的元素是否为null
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 遍历数组，查找要进行删除元素的位置，并调用fastRemove方法删除
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
 * 不调用rangeCheck方法进行范围检查，跳过范围检查的删除方式
 */
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
}

/**
 * 从列表中删除所有元素。
 */
public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        // 元素全部设为 null
        elementData[i] = null;
    // 长度设为 0
    size = 0;
}

/**
 * 按指定集合的Iterator返回的顺序
 * 将指定集合中的所有元素追加到此列表的末尾。
 */
public boolean addAll(Collection<? extends E> c) {
    // 转为数组
    Object[] a = c.toArray();
    // 拿到待添加指定数组的长度
    int numNew = a.length;
    // 确认 list 容量，尝试容量加上 numNew，看看有无必要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 利用 arraycopy 指定数组a的元素追加到当前数组 elementData 后
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 按指定集合的Iterator返回的顺序
 * 将指定集合中的所有元素添加到此列表中，从指定位置开始
 * 
 */
public boolean addAll(int index, Collection<? extends E> c) { 
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 计算需要移动的元素
    int numMoved = size - index;
    if (numMoved > 0)
        // 实现元素指定位置的插入，本质还是 arraycopy 自身
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

/**
 * 删除指定索引范围内的元素（fromIndex - toIndex）
 */
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

/**
 * 检查给定的索引是否在范围内。
 */
private void rangeCheck(int index) {
    // 下标越界就直接抛异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 另一个版本，针对add 和 addAll使用
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 与上面套娃使用
 */
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

/**
 * 从此列表中删除指定集合中包含的所有元素。
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 仅保留此列表中包含在指定集合中的元素。即删掉没有的部分
 */
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

/**
 * 删除的具体逻辑
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            // 通过循环判断数组中有没有指定数组中的每一个值，complement 是参数传递的
            if (c.contains(elementData[r]) == complement)
                // 就将原数组的r位置的数据覆盖掉w位置的数据
                // r位置的数据不变，并其w自增，r自增
                // 否则，r自增，w不自增
                // 本质：把需要移除的数据都替换掉，不需要移除的数据前移
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

// writeObject readObject 序列化相关的省略
   
/**
 * 列表迭代器：List集合特有的迭代器
 */
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}


public ListIterator<E> listIterator() {
    return new ListItr(0);
}

// foreach 遍历等同于 iterator
public Iterator<E> iterator() {
    return new Itr();
}


private class Itr implements Iterator<E> {
    // 下一个要访问的元素下标
    int cursor; 
    // 上一个要访问的元素下标
    int lastRet = -1; 
    // 代表对 ArrayList 修改次数的期望值，初始值为 modCount
    int expectedModCount = modCount;

    Itr() {}

    // 下标如果
    public boolean hasNext() {
        return cursor != size;
    }

    /**
     * 刚开始cursor = 0，lastRet = -1
     * 整个过程结束 cursor 和 lastRet 都会自增 1
     */
    @SuppressWarnings("unchecked")
    public E next() {
        // 跳转本质是判断 modCount 是否等于 expectedModCount
        checkForComodification();
        int i = cursor;
       // 判断 cursor 是否超过集合大小和数组长度
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        // 将 cursor 赋值给 lastRet，然后把此下标处的元素返回
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        // 先判断 lastRet 的值是否小于 0
        if (lastRet < 0)
            throw new IllegalStateException();
        // 跳转本质是判断 modCount 是否等于 expectedModCount
        checkForComodification();

        try {
            // 直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    
    // forEachRemaining 略

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

1.7扩容原理

按照以下代码进行分析：

public class ArrrayListDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
    }
}

1. 首先创建ArrayList对象实例，进入构造器方法
   • 查看常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即默认创建的是一个空数组。elementData就是Object类型的数组。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

2. 跳出构造器方法，执行add()方法
   • 首先调用ensureCapacityInternal()方法用于确保内部容量。

public boolean add(E e) {
    //确定数组容量，尝试容量加1
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

3. 调用ensureCapacityInternal()方法
   • 调用calculateCapacity(elementData, minCapacity)方法
   • 参数minCapacity此时为1

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

4. 调用calculateCapacity()方法，求得最小容量
   • 传递的参数为elementData(此时为空数组)和minCapacity(此时为1)。
   • 此时elementData 就是等于空数组，同时DEFAULT_CAPACITY(10)>minCapacity(1)，所以返回10。

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果当前的数组对象elementData数组为空
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 返回“默认的容量”和“传入参数 minCapacity ”两者之间的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //如果当前的数组对象elementData不为空，则直接返回minCapacity
    return minCapacity;
    }

5. 再次回到ensureCapacityInternal方法

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

6. 调用ensureExplicitCapacity方法，判断添加元素的时候是否需要对当前数组进行扩容
   • 此时minCapacity为10，minCapacity - elementData.length = 10

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 如果当前的最小容量比数组对象elementData的长度大
    if (minCapacity - elementData.length > 0)
        //进行扩容
        grow(minCapacity);
}

此方法的核心就是 if 判断这个数组需不需要扩容，可以分为三种情况

• add 第 1 个元素时：此时数组还只是一个被初始化过的空数组，minCapacity 经过 calculateCapacity 计算会返回 DEFAULT_CAPACITY 的默认值 10，而 elementData.length 也自然是 0，所以 minCapacity - elementData.length > 0 是成立的，直接进入 grow(minCapacity); 开始扩容。

• add 第 2 到 10 个元素的时候（以 2 举例）：此时 minCapacity = size + 1 = 1 + 1 = 2 ，而 elementData.length 已经在添加第 1 个元素后等于 10 了。所以 minCapacity - elementData.length > 0 就不成立了，所以不会进入 grow(minCapacity); ，也不会扩容

• • 添加第 3 … 10 个元素的时候，都是一样的。

• add 第 11 个元素的时候，minCapacity 变成了 11，比 10 还要大，所以又一次进去扩容了

7. 调用grow()方法进行扩容
   • 进行扩容
   • 如果扩容后的长度依然小于所需最小容量，则直接将所需最小容量当作新容量
   • 如果新容量大于了所规定的最大容量，调用hugeCapacity()方法
   • 最后调用 Arrays.copyOf() 方法，用来复制原数组，将 elementData 赋值为得到的新数组

private void grow(int minCapacity) {
    // 原始的容量
    int oldCapacity = elementData.length;
    // 扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量小于最小容量
    if (newCapacity - minCapacity < 0)
        //则将最小容量当作新容量
        newCapacity = minCapacity;
    //如果新容量大于了所规定的最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //调用hugeCapacity()方法
        newCapacity = hugeCapacity(minCapacity);
    // 最后调用 Arrays.copyOf() 方法，用来复制原数组，将 elementData 赋值为得到的新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

8. hugeCapacity(int minCapacity) 方法，用于处理 minCapacity 超出 MAX_ARRAY_SIZE 的情况

private static int hugeCapacity(int minCapacity) {
    //如果最小容量小于0，抛出异常
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //判断最小容量是否大于所规定的最大容量，如果大于则扩容至，不大于就为MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

9. System.arraycopy() 和 Arrays.copyOf()方法

阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！

System.arraycopy() 方法

源码：

// 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
/**
*   复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

场景：

/**
 * 在此列表中的指定位置插入指定的元素。
 *先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
 *再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //arraycopy()方法实现数组自己复制自己
    //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

Arrays.copyOf()方法

源码：

   public static int[] copyOf(int[] original, int newLength) {
   	// 申请一个新的数组
       int[] copy = new int[newLength];
// 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
       System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
       return copy;
   }

场景：

/**
  以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
  */
 public Object[] toArray() {
 //elementData：要复制的数组；size：要复制的长度
     return Arrays.copyOf(elementData, size);
 }

10. 回到add()方法

• 此时elementData就是一个长度为10的空数组。
• elementData[size++] = e;将元素存储在索引为0的位置，并将size加1。其中size是用于记录元素个数。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

2.LinkList源码分析

2.1LinkedList概述

LinkedList 底层是基于双向链表实现的。其中的元素在逻辑上是连续的，但是在物理结构上不一定连续。

在 LinkedList 的内部，有一个名为 Node 的内部类用来表示链表中的节点。每个节点都包含一个元素和两个指向前驱节点和后继节点的指针。当我们创建一个 LinkedList 对象时，它会初始化一个空的链表。

当我们向 LinkedList 中添加元素时，它会创建一个新的节点，并将其插入到链表中。由于链表是动态分配内存的，因此不需要进行扩容操作。

2.2类声明

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    ...
}

• List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
• Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。
• Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
• Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

结构树如下：

2.3属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 双向链表的节点个数
    transient int size = 0;

    /**
     * 双向链表指向头节点的指针
     */
    transient Node<E> first;

    /**
     * 双向链表指向尾节点的指针
     */
    transient Node<E> last;

}

从以上源码可以看出，LinkedList 的属性比较少，分别是：

• size ：双向链表的节点个数
• first：双向链表指向头节点的指针
• last： 双向链表指向尾节点的指针

注意：first 和 last 是由引用类型 Node 连接的，这是它的一个内部类。

2.4内部类Node解析

LinkedList 是通过双向链表实现的，而双向链表就是通过 Node 类来实现的。

• Node 类中通过 item 变量存储当前元素
• 通过 next 变量指向当前节点的下一个节点
• 通过 prev 变量指向当前节点的上一个节点

private static class Node<E> {
    // item表示当前存储元素
    E item;
    // next表示当前节点的前驱节点
    Node<E> next;
    // prev表示当前节点的后继节点
    Node<E> prev;

    //构造函数
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

2.5构造方法

LinkedList 中有一个无参构造函数和一个有参构造函数。

// 创建一个空的链表对象
public LinkedList() {
}

// 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.6常用方法解析

2.6.1插入节点

LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。

在 LinkedList 中，当我们向链表中添加一个元素时，它会创建一个新的节点来存储这个元素。这个过程是通过调用 LinkedList 类中的 linkLast() 方法或 linkBefore() 方法实现的。

例如，当我们调用 add() 方法在链表末尾添加一个元素时，它会调用 linkLast() 方法。在这个方法中，首先会创建一个新的节点，并将其元素设置为要添加的元素。然后，它会将新节点的前驱节点设置为原链表的最后一个节点，并将原链表最后一个节点的后继节点设置为新节点。最后，它会更新链表的大小和修改次数。

1. add(E e)：用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。

2. add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

案例如下：

• 只有1个元素的LinkedList

• 包含4个元素的LinkedList

1. add(E e) 方法，将指定的元素追加到此列表的末尾

   /**
   * 添加元素到末尾
   */
public boolean add(E e) {
       //调用LinkLast方法
       linkLast(e);
       return true;
   }

其中，调用的 linkLast() 方法，设置元素 e 为最后一个元素：

• 获取链表的最后一个节点
• 创建一个新节点
• 使新的一个节点为最后一个节点
• 如果最后一个节点为 null，则表示链表为空，则将 newNode 赋值给 first 节点
• 否则尾节点的 last 指向 newNode

/**
 * Links e as last element.
 */
void linkLast(E e) {
    //获取到链表中的最后一个节点
    final Node<E> l = last;
    //创建一个新的节点，新节点的元素就是添加的元素，前驱节点就是之前的last节点
    final Node<E> newNode = new Node<>(l, e, null);
    // 使新的一个节点为最后一个节点
    last = newNode;
    // 如果最后一个节点为null，则表示链表为空，则将newNode赋值给first节点
    // 即当前newNode节点即为fast节点，又为last节点
    if (l == null)
        first = newNode;
    else
        // 否则尾节点的next 指向 newNode
        l.next = newNode;
    // 元素的个数加1
    size++;
    // 修改次数自增
    modCount++;
}

• add(int index,E e)方法

public void add(int index, E element) {
    // 判断是否是现有元素的索引
    checkPositionIndex(index);

    // 如果index==size，直接在链表的最后插入元素，相当于add(E e)方法
    if (index == size)
        linkLast(element);
    else
    	// 否则调用node方法将index位置的节点找出，接着调用linkBefore 方法
        // 参数为当前添加的元素和插入位置的节点元素
        linkBefore(element, node(index));
}

调用checkPositionIndex方法判断是否是现有元素的索引

   private void checkPositionIndex(int index) {
       //如果不在就抛出异常
       if (!isPositionIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
/**
* 判断是否是现有元素的索引
*/
   private boolean isPositionIndex(int index) {
       return index >= 0 && index <= size;
   }

如果是在非null节点之前节点，则调用linkBefore()方法，在非 null 节点 succ 之前插入元素 e

   /**
   * 在链表中间添加节点，参数为插入的节点和插入位置的节点
   */
void linkBefore(E e, Node<E> succ) {
       // 获取到插入节点的前驱节点
       final Node<E> pred = succ.prev;
       //创建一个新的节点，新节点的元素就是添加的元素，前驱节点就是之前插入节点的前驱节点
       //后继节点就是插入的节点
       final Node<E> newNode = new Node<>(pred, e, succ);
       // 构建双向链表，succ的前驱节点为新的节点
       succ.prev = newNode;
       // 如果前驱节点为null，则把newNode赋值给first，newNode就是头节点
       if (pred == null)
           first = newNode;
       else
           // 构建双向链表
           pred.next = newNode;
       // 元素的个数加1   
       size++;
       // 修改次数自增
       modCount++;
   }

2.6.2删除节点

LinkedList删除元素相关的方法一共有 5 个：

1. removeFirst()：删除并返回链表的第一个元素。
2. removeLast()：删除并返回链表的最后一个元素。
3. remove(E e)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
4. remove(int index)：删除指定索引处的元素，并返回该元素的值。
5. void clear()：移除此链表中的所有元素。

• remove(Object obj)方法

• remove(int index)方法

1. remove()方法，删除头节点

在remove()方法中调用的是removeFirst方法，即删除first节点

public E remove() {
    //调用`unlinkFirst()`方法
    return removeFirst();
}

获取到头节点first，如果头节点为空则抛出异常，否则调用unlinkFirst()方法

public E removeFirst() {
    //获取到头节点
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    //头节点不为空，调用unlinkFirst(Node<E> f)方法
    return unlinkFirst(f);
}

在unlinkFirst()方法中接收first节点作为参数

private E unlinkFirst(Node<E> f) {
    //获取到头节点的元素
    final E element = f.item;
    //获取到头节点的下一个节点
    final Node<E> next = f.next;
    //头节点元素为null
    f.item = null;
    //头节点的后继节点为null
    f.next = null; // help GC
    //将头节点的下一个节点作为头节点
    first = next;
    if (next == null)
        last = null;
    else
        //头节点的前驱节点为null
        next.prev = null;
    //节点数量减1
    size--;
    modCount++;
    return element;
}

2. remove(int index) 方法，删除指定位置的元素

检查索引 index 的位置，调用 node 方法获取节点，接着调用 unlink(E e) 方法：

public E remove(int index) {
    // 检查索引index的位置
    checkElementIndex(index);
     // 调用node方法获取节点，接着调用unlink(E e)方法
    return unlink(node(index));
}

nulink(Node x)方法

E unlink(Node<E> x) {
    // 获取当前节点（也就是待删除节点）的元素
    final E element = x.item;
    // 获取当前节点的下一个节点
    final Node<E> next = x.next;
    // 获取当前节点的前一个节点
    final Node<E> prev = x.prev;

    // 如果前一个节点为空，则说明当前节点是头节点
    if (prev == null) {
        // 直接让链表头指向当前节点的下一个节点
        first = next;
    } else { // 如果前一个节点不为空
        // 将前一个节点的 next 指针指向当前节点的下一个节点
        prev.next = next;
        // 将当前节点的 prev 指针置为 null，，方便 GC 回收
        x.prev = null;
    }

    // 如果下一个节点为空，则说明当前节点是尾节点
    if (next == null) {
        // 直接让链表尾指向当前节点的前一个节点
        last = prev;
    } else { // 如果下一个节点不为空
        // 将下一个节点的 prev 指针指向当前节点的前一个节点
        next.prev = prev;
        // 将当前节点的 next 指针置为 null，方便 GC 回收
        x.next = null;
    }

    // 将当前节点元素置为 null，方便 GC 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink() 方法的逻辑如下：

1. 首先获取待删除节点 x 的前驱和后继节点；
2. 判断待删除节点是否为头节点或尾节点：
   • 如果 x 是头节点，则将 first 指向 x 的后继节点 next。
   • 如果 x 是尾节点，则将 last 指向 x 的前驱节点 prev。
   • 如果 x 不是头节点也不是尾节点，执行下一步操作
3. 将删除节点的前驱节点的next指向删除节点的后继节点
4. 将删除元素的后继节点的pre指向删除节点的前驱节点

2.6.3修改节点

set(int index, E element) 方法，将指定下标处的元素修改成指定值

public E set(int index, E element) {
    //判断是否是现有元素的索引
	checkElementIndex(index);
	// 通过node(int index)找到对应下标的元素
	Node<E> x = node(index);
 	// 取出该节点的元素，供返回使用
	E oldVal = x.item;
 	// 用新元素替换旧元素
	x.item = element;
	// 返回旧元素
	return oldVal;
}

2.6.4获取节点

LinkedList获取元素相关的方法一共有 3 个：

1. getFirst()：获取链表的第一个元素。

2. getLast()：获取链表的最后一个元素。

3. get(int index)：获取链表指定位置的元素。

get(int index) 返回此列表中指定位置的元素

public E get(int index) {
	// 判断index是否是现有元素的索引
    checkElementIndex(index);
    // 调用node()方法
    return node(index).item;
}

在此调用了node() 方法：

该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。

// 返回指定下标的非空节点
Node<E> node(int index) {
    // 如果index小于size的二分之一  从前开始查找（向后查找）  反之向前查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 遍历，循环向后查找，直至 i == index
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.6.5遍历链表

遍历链表在2.8章节详细说明

2.7双端队列操作方法的源码剖析

1. offerFirst(E e) 方法，将元素添加到首部

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

2. offerLast(E e) 方法，将元素添加到尾部

public boolean offerLast(E e) {
     addLast(e);
     return true;
 }

3. peekFirst() 方法，获取此集合列表的第一个元素值

public E peekFirst() {
     final Node<E> f = first;
     return (f == null) ? null : f.item;
  }

4. peekLast() 方法，获取此集合列表的最后一个元素值

public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

5. pollFirst() 方法，删除此集合列表的第一个元素，如果为 null，则会返回 null

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

6. pollLast() 方法 ，删除此集合列表的最后一个元素，如果为 null 会返回 null

public E pollLast() {
      final Node<E> l = last;
      return (l == null) ? null : unlinkLast(l);
  }

7. push(E e) 方法，将元素添加到此集合列表的首部

public void push(E e) {
     addFirst(e);
 }

8. pop() 方法，删除并返回此集合列表的第一个元素，如果为null会抛出异常

//删除首部，如果为null会抛出异常
public E pop() {
    return removeFirst();
}

9. removeFirstOccurrence(Object o)方法，删除集合中元素值等于o的第一个元素值

public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

注：removeFirstOccurrence() 和 remove 方法是一样的，它的内部调用了 remove 方法

10. removeLastOccurrence(Object o)方法，删除集合中元素值等于o的最后一个元素值

public boolean removeLastOccurrence(Object o) {
    //因为LinkedList中的元素允许存在null值，所以需要进行null判断
    if (o == null) {
    	// 从最后一个节点往前开始遍历
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
            	 // 调用unlink方法删除指定节点
                unlink(x);
                return true;
            }
        }
    } else {
    	// 否则元素不为空，进行遍历
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

2.8LinkedList迭代器

推荐使用for-each（增强for循环） 循环来遍历 LinkedList 中的元素， for-each 循环最终会转换成迭代器形式。

LinkedList<String> list = new LinkedList<>();
list.add("apple");
list.add("banana");
list.add("pear");

for (String fruit : list) {
    System.out.println(fruit);
}

LinkedList 的遍历的核心就是它的迭代器的实现。

// 双向迭代器
private class ListItr implements ListIterator<E> {
    // 表示上一次调用 next() 或 previous() 方法时经过的节点；
    private Node<E> lastReturned;
    // 表示下一个要遍历的节点；
    private Node<E> next;
    // 表示下一个要遍历的节点的下标，也就是当前节点的后继节点的下标；
    private int nextIndex;
    // 表示当前遍历期望的修改计数值，用于和 LinkedList 的 modCount 比较，判断链表是否被其他线程修改过。
    private int expectedModCount = modCount;
    ....
        
}

下面我们对迭代器 ListItr 中的核心方法进行详细介绍。

我们先来看下从头到尾方向的迭代：

// 判断还有没有下一个节点
public boolean hasNext() {
    // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
    return nextIndex < size;
}
// 获取下一个节点
public E next() {
    // 检查在迭代过程中链表是否被修改过
    checkForComodification();
    // 判断是否还有下一个节点可以遍历，如果没有则抛出 NoSuchElementException 异常
    if (!hasNext())
        throw new NoSuchElementException();
    // 将 lastReturned 指向当前节点
    lastReturned = next;
    // 将 next 指向下一个节点
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

再来看一下从尾到头方向的迭代：

// 判断是否还有前一个节点
public boolean hasPrevious() {
    return nextIndex > 0;
}

// 获取前一个节点
public E previous() {
    // 检查是否在迭代过程中链表被修改
    checkForComodification();
    // 如果没有前一个节点，则抛出异常
    if (!hasPrevious())
        throw new NoSuchElementException();
    // 将 lastReturned 和 next 指针指向上一个节点
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

3.Vector源码分析

3.1Vector概述

Vector 是一个基于数组实现的动态数组，它和ArrayList一样能够根据扩容机制能够实现容量的动态增长。

3.2类声明

Vector类声明如下 ：

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ....
}

• List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
• RandomAccess 是一个标志接口（Marker），支持快速随机访问（通过元素序号快速获取元素对象 —— get(int index)）
• Cloneable ：实现浅克隆（clone()）
• java.io.Serializable ：ArrayList 支持序列化

结构树如下：

3.3构造方法

1. 调用无参构造
   • 在无参构造中又调用本类当中的有参构造Vector(int initialCapacity)
   • 默认初始化容量为10
   • 在构造函数Vector(int initialCapacity)又调用Vector(int initialCapacity, int capacityIncrement)方法，capacityIncrement默认为0

   public Vector(int initialCapacity, int capacityIncrement) {
       super();
       //如果当前initialCapacity小于0，就抛出异常
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
      	//创建一个容量大小为10的Object类型的数组elementData
       this.elementData = new Object[initialCapacity];
       this.capacityIncrement = capacityIncrement;
   }

/**
* 调用带有int，int类型参数的构造方法
*/
   public Vector(int initialCapacity) {
       this(initialCapacity, 0);
   }

/**
* 无参构造，调用带有int类型参数的构造方法
*/
   public Vector() {
       this(10);
   }

2. 调用有参构造Vector(int initialCapacity, int capacityIncrement)
   • 需要传入两个int类型的参数，分别是数组的初始化长度和扩容的增量

总结：

Vector默认的扩容机制是按两倍扩容。这意味着，如果创建Vector对象时没有指定capacityIncrement，则每次扩容时，新容量等于原容量的两倍。

如果创建Vector对象时指定了capacityIncrement，则每次扩容时，新容量等于原容量加上capacityIncrement。

3.4扩容原理

1. 调用add()方法

public synchronized boolean add(E e) {
    modCount++;
    //调用ensureCapacityHelper方法确保容量
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

2. 进入ensureCapacityHelper方法

• 判断内容容量，首先添加元素时minCapacity = 1，elementData.length = 10。所以不用扩容

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

3. 查看扩容方法grow()

• 假设此时elementData为10，oldCapacity就为10，capacityIncrement为0，则newCapacity就为原来的oldCapacity两倍。

private void grow(int minCapacity) {
    // 获取到当前对象数组容量
    int oldCapacity = elementData.length;
    // 扩容，默认是按照两倍进行扩容，即capacityIncrement = 0
    // 当capacityIncrement不为0时，就按照原始容量+增量进行扩容
    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);
}

4.HashSet源码分析

4.1HashSet简介

HashSet 是 Java 集合 Set 的一个实现类，Set 是一个接口，其实现类除 HashSet 之外，还有 TreeSet，并继承了 Collection。

4.2类声明

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    ...
}

• 实现了 Serializable 接口，表明它支持序列化。
• 实现了 Cloneable 接口，表明它支持克隆，可以调用超类的 clone（）方法进行浅拷贝。
• 继承了 AbstractSet 抽象类，和 ArrayList 和 LinkedList 一样，在他们的抽象父类中，都提供了 equals() 方法和 hashCode() 方法。它们自身并不实现这两个方法
• 实现了 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持，不能保证元素的顺序。

1.3属性

   // 底层使用HashMap来保存HashSet中所有元素。
private transient HashMap<E,Object> map;

   // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
   private static final Object PRESENT = new Object();

1.4构造函数

//无参构造方法，完成map的创建
public HashSet() {
    map = new HashMap<>();
}
//指定集合转化为HashSet, 完成map的创建
public HashSet(Collection<? extends E> c) {
   map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
   addAll(c);
}
//指定初始化大小，和负载因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
//指定初始化大小
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
//指定初始化大小和负载因子，dummy 无实际意义
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

通过构造函数，不难发现，HashSet 的底层是采用 HashMap 实现的。

1.5常用方法解析

1. 添加方法

//添加一个元素，如果该元素已经存在，则返回true，如果不存在，则返回false
public boolean add(E e) {
    //往map中添加元素，返回null，说明是第一个往map中添加该key
    return map.put(e, PRESENT)==null;
}

往 HashSet 中添加元素，实际是往 Map 成员变量里面添加对应的 key 和 value；Map 中的 key 实际就是要添加的元素，value 是一个对象类型的静态常量；

private static final Object PRESENT = new Object();

当第一次往 Map 中添加 key 时，添加成功返回 null，所以当第一次往 HashSet 中添加元素时，会返回 true；由于 HashMap 中的 key 不能重复，所以 HashSet 不能存储重复元素。

2. 删除方法

//删除指定的元素，删除成功返回true
public boolean remove(Object o) {
    //实际是删除map中的一个对象
    return map.remove(o)==PRESENT;
}

当 HashSet 删除一个元素时，实际是操作 Map 删除对应的元素；当删除 Map 中一个不存在的对象是，会返回 null，所以这里当返回 PERSENT 时，说明之前 HashSet 往 Map 中添加过对应的元素，因此，当 remove(o) 返回 true 时，说明之前已经存在该元素，并且成功删除；当返回 false 时，说明之前并没有添加过该对象。

4. iterator() 方法

//获取hashSet的迭代器
public Iterator<E> iterator() {
    //调用map获取keySet
    return map.keySet().iterator();
}

Hashset 获取迭代器实际是获取 Map 的 keySet 的 iterator。

5. size() 方法

public int size() {
    return map.size();
}

size() 方法实际是调用 Map 集合中的 size() 方法。

总结：

我们发现 HashSet 的底层源码特别少，主要是因为 HashSet 的方法基本都是借助 HashMap 的方法来实现的。

HashSet 存储的元素对应 HashMap 的 key，因为 HashMap 不能存储重复的 key，所以 HashSet 不能存放重复元素；由于HashMap 的 key 是基于 hashCode 存储对象的，所以 HashSet 中存放的对象也是无序的；HashSet 也没有提供 get 方法，可以通过 Iterator 迭代器获取数据。

5.HashMap源码分析

5.1HashMap概述

HashMap 在jdk1.8之前的存储结构是数组+链表，到了jdk1.8变成了数组+链表+红黑树。

在 JDK1.6 和 JDK1.7 中，HashMap 采用数组 + 链表实现，即使用拉链法处理哈希冲突，同一 hash 值的链表都存储在一个链表里。但是当位于一个链表中的元素较多时，通过 key 值依次查找的效率较低。而 JDK1.8 中，HashMap 采用数组 + 链表 + 红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，在性能上进一步得到提升。

注意：不是说变成了红黑树效率就一定提高了，只有在链表的长度大于8，而且数组的长度大于64的时候才会将链表转化为红黑树，

问题一：什么是红黑树呢？

红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的o(n)降低为o(logn)。红黑树的查找效率很高。

问题二：为什么不一下子把整个链表变为红黑树呢？

这个问题的意思是这样的，就是说我们为什么非要等到链表的长度大于等于8的时候，才转变成红黑树？在这里可以从两方面来解释

（1）构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。

（2）HashMap频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率。

JDK1.7时的数据结构：

JDK1.8时的数据结构：

5.2属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;    
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量：2^30，超过仍按2^30来算
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子（负载因子/加载因子）
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; // 下面会分析结构源码
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 阈值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 负载因子
    final float loadFactor;
}

• table：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。

• loadFactor：

  ​ 负载因子，默认为 0.75。loadFactor 负载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于1，那么数组中存放的数据（entry）也就越多，也就越密。loadFactor 越小，也就是趋近于 0，数组中存放的数据（entry）也就越少，也就越稀疏。

  ​ loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75，是官方给出的一个比较好的临界值。给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

• threshold：扩容的阈值。threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要对数组扩容。

5.3构造函数

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

上面 4 个构造方法中

• 无参构造HashMap()初始化负载因子

• HashMap(int initialCapacity)可以指定初始容量大小，并调用有参构造HashMap(int initialCapacity, float loadFactor)

• HashMap(int initialCapacity, float loadFactor)：可以指定初始化容量和负载因子，并根据指定的初始容量调用tableSizeFor()方法计算得阈值threshold。

  • 即阈值就是大于等于指定初始化容量的最小2次幂

  •     static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    
      * 但是发现并没将`initialCapacity`参数没有被保存下来，那么它怎么参与数组的初始化过程呢？这会在扩容机制方法`resize()`中出现。
    
    * `HashMap(Map<? extends K, ? extends V> m)`：将一个几个列表作为参数传入
    
    
    
    ## 5.4Node节点
    
    `Node`类是一个静态内部类。这个`Node`类表示哈希表中的一个节点，它既可以是数组中的元素，也可以是链表结构中的元素。
    
    ```java
    // 继承自 Map.Entry<K,V>
    static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
      final K key;//键
      V value;//值
      // 指向下一个节点
      Node<K,V> next;
      Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
       }
       public final K getKey()        { return key; }
       public final V getValue()      { return value; }
       public final String toString() { return key + "=" + value; }
       // 重写hashCode()方法
       public final int hashCode() {
           return Objects.hashCode(key) ^ Objects.hashCode(value);
       }
    
       public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
       }
       // 重写 equals() 方法
       public final boolean equals(Object o) {
           if (o == this)
               return true;
           if (o instanceof Map.Entry) {
               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
               if (Objects.equals(key, e.getKey()) &&
                   Objects.equals(value, e.getValue()))
                   return true;
           }
           return false;
       }
    }

5.5树节点TreeNode

TreeNode类是一个静态内部类。表示红黑树中的一个节点，它包含了键值对的信息。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父
    TreeNode<K,V> left;    // 左
    TreeNode<K,V> right;   // 右
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;           // 判断颜色
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    // 返回根节点
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

5.6添加元素源码分析

我们在存储一个元素的时候，大多是使用下面的这种方式。

public class Test {
    public static void main(String[] args) {
        HashMap<String, Integer> map= new HashMap<>();
        //存储一个元素
        map.put("张三", 20);
    }
}

存储的时候只需要调用put方法即可。根据HashMap的数据结构，可以画出以下流程图：

1. put()方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

put方法其实调用的是putVal方法。putVal方法有5个参数：

（1）第一个参数hash：调用了hash方法（散列函数）计算hash值（散列值）

   /**
   * 散列函数
   */
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

散列值的计算：调用hashCode()函数计算出key的散列值，并和散列值的无符号右移16位后的结果进行异或运算。

（2）第二个参数key：就是我们传入的key值，也就是例子中的张三

（3）第三个参数value：就是我们传入的value值，也就是例子中的20

（4）第四个参数onlyIfAbsent：如果为true，则仅在键不存在时才插入值

（5）第五个参数evict ：如果为false，那么数组就处于创建模式中，所以一般为true。

2. 调用putVal()方法

下面方法的步骤可以总结为：

1. 首先，检查数组是否为空，如果为空，则调用resize()方法进行扩容。

2. 然后，根据哈希值计算键值对应该存储在数组的索引位置。

   • 计算方式为(n - 1) & hash，即将每个元素的key的hash值，与最大索引值进行与操作，如果对应的索引处为空，则直接添加。
   • 为什么HashMap的容量要为2的幂次方呢？
   • 因为在putVal()方法中，计算key对应的散列值是根据当前的HashMap容量减1和hash值做与操作，由于HashMap的容量都是2的幂次方，减1后转换为二进制全为1，由于2进制做与运算时，同为1则为1，所以通过这种算法能够将哈希值均匀地映射到散列表中，使元素分布更加均匀，较少碰撞。

3. 如果该位置为空，则直接在该位置创建一个新节点。

4. 如果该位置不为空，则检查该位置的节点是否与要插入的key相同。如果相同，则更新节点的值。

5. 如果该位置的节点不是要插入的键值对，并且该节点是一个树节点，则调用putTreeVal方法将键值对插入到红黑树中。如果存在相同的key，就会进行替换。

6. 如果该位置的节点不是要插入的键值对，并且该节点不是一个树节点，则遍历链表，查找是否有与要插入的键值对相同的节点。如果找到了，则更新节点的值；否则，在链表尾部插入一个新节点。如果链表长度超过了阈值，则调用treeifyBin()方法转换为红黑树结构，但是在转换为红黑树之前，会判断当前的HashMap容量是否大于64，如果大于64才会转换为红黑树。

7. 最后，更新哈希表的大小，并判断哈希表中的节点数量是否大于阈值，如果大于阈值，就进行扩容。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab表示的就是数组，p表示当前插入的节点
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果数组为空，就调用resize()方法创建一个新数组
    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;
        //判断插入的key是否和原先的key相同，如果相同就直接替换原来的值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //key不同，就判断插入的数据结构是否是红黑树
        else if (p instanceof TreeNode)
            //如果是红黑树就直接调用putTreeVal()方法添加到红黑树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //当前的数据结构为链表，遍历链表
            for (int binCount = 0; ; ++binCount) {
                //遍历链表，到达链表的尾部
                if ((e = p.next) == null) {
                    //在链表尾部添加新节点
                    p.next = newNode(hash, key, value, null);
                    //判断当前链表中的节点数量是否大于等于树型阈值，
                    //如果大于等于就调用treeifyBin()方法转换为红黑树结构
                    //因为bigCount的下标是从0开始的，所以这里树化阈值需要减1
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果在链表中存在对应的key，则替换节点对应的值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判断哈希表中的节点数量是否大于阈值，如果大于阈值，就进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

5.7扩容机制

在 HashMap 中，数组的长度均是 2 的幂次方，阈值大小为数组长度与负载因子的乘积。当 HashMap 中的键值对数量(size）超过阈值(threshold)时，进行扩容。

HashMap 的扩容机制与其他变长集合的不太一样，HashMap 按当前数组长度的 2 倍进行扩容，阈值也变为原来的 2 倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。

流程图如下：

resize就是进行扩容的方法

下面方法的步骤可以总结为：

1. 首先，获取旧哈希表的信息，包括旧哈希表、旧容量和旧阈值。这些信息分别存储在oldTab、oldCap和oldThr变量中。

2. 如果容量大于0并且容量大于所规定的最大容量，则将Integer类型的最大值赋值给阈值threshold，如果容量大于0但是不大于所规定的最大值，则将容量和阈值都扩大为原来的两倍。

3. 如果阈值大于0，则将阈值赋值给最新容量。

4. 如果容量和阈值都不大于0，则初始化默认容量，并将默认容量和负载因子的乘积作为阈值。

5. 如果新阈值仍然为0，则根据新容量和负载因子计算新阈值。具体计算方法是将新容量乘以负载因子，然后取整。

6. 接下来，根据新的容量创建一个新的哈希表，并将旧哈希表中的元素复制到新哈希表中。

   • 如果旧哈希表中的元素是一个单独的节点，则直接将其复制到新哈希表中；
   • 如果旧哈希表中的元素是一个树节点，则调用split方法将其分裂到新哈希表中；
   • 否则，遍历链表，将链表中的节点分别复制到新哈希表中。

7. 在复制链表中的节点时，需要保持节点在链表中的相对顺序不变。具体做法是遍历旧链表，将每个节点分别插入到两个新链表中。其中一个新链表用于存储索引位置不变的节点，另一个新链表用于存储索引位置改变的节点。最后，将两个新链表分别插入到新哈希表中。这样做可以保证在扩容后，链表中的元素顺序不变。

8. 最后，返回新哈希表。`

9. 这里把oldThr > 0情况单独拿出来说一下。在这种情况下，会将 oldThr 赋值给 newCap，等价于newCap = threshold = tableSizeFor(initialCapacity)。我们在初始化时传入的 initialCapacity 参数经过 threshold 中转最终赋值给了 newCap。这也就解答了前面提的一个疑问：initialCapacity 参数没有被保存下来，那么它怎么参与哈希表的初始化过程的呢？

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //获取到当前数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //获取到旧的阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //扩容
    //如果数组不为空，表明已经初始化了
    if (oldCap > 0) {
        //如果当前的数组容量大于了所规定的最大容量`MAXIMUM_CAPACITY = 1 << 30`
        if (oldCap >= MAXIMUM_CAPACITY) {
            //如果大于等于了最大容量，就将Integer类型的最大值赋值为阈值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 按旧容量和阈值的2倍计算新容量和阈值的大小
        //进行数组扩容时，如果新容量（newCap）小于最大容量（MAXIMUM_CAPACITY）并且旧容量（oldCap）大于等于默认初始容量（DEFAULT_INITIAL_CAPACITY），则将阈值（threshold）也扩大一倍，以保持负载因子不变。
        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
       /*
     	* 如果阈值已经初始化过了，那就直接使用旧的阈值
     	* HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
     	*/
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 没有初始化阈值那就初始化一个默认的容量和阈值
        // 容量为初始容量DEFAULT_INITIAL_CAPACITY = 16
        // 阈值为初始负载因子和初始化容量的乘积
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 如果新阈值仍然为0，则根据新容量和负载因子计算新阈值
    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;
            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 { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表，并将链表节点按原顺序进行分组
                    //这段代码会遍历旧链表中的每个节点，根据节点的哈希值和旧哈希表的容量来判断节点在新哈希表中的索引位置是否改变。                         //如果索引位置不变，那么将节点插入到一个新链表中；如果索引位置改变，那么将节点插入到另一个新链表中。最后，这段                         //代码会将两个新链表分别插入到新哈希表中。其中一个新链表用于存储索引位置不变的节点，另一个新链表用于存储索引位                         //置改变的节点。这样做可以保证在扩容后，链表中的元素顺序不变。
                    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);
                    // 将分组后的链表映射到新哈希表中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

5.8树化和链化

在 JDK 1.8 及以后的版本中，HashMap 引入了红黑树结构。当桶中链表元素个数大于等于 8 时，链表会转换成树结构；若桶中链表元素个数小于等于 6 时，树结构还原成链表。

中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

为什么要在8时转换为红黑树：

选择8和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。当为8时，hash碰撞发生8次的概率已经降低到了6×10⁻⁸。如果真的碰撞发生了8次，此时的链表性能已经已经很差了，操作的hash碰撞的可能性非常大了，后序可能还会继续发生hash碰撞。所以，将链表转换为红黑树来提升性能。

5.8.1链表树化

当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。

//树化的阈值
static final int TREEIFY_THRESHOLD = 8;

/**
 * 最小树化容量当桶数组容量小于该值时，优先进行扩容，而不是树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

/**
 * 将普通节点链表转换成树形节点链表
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 为头节点（head），tl 为尾节点（tail）
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将普通节点替换成树形节点
            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)
            // 将树形链表转换成红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

树化要满足两个条件：

1. 链表的长度大于了阈值（默认为8）。
2. 哈希表的数组长度大于等于64。

只有当这两个条件都满足时，才会进行树化。如果哈希表的容量小于64，则会通过扩容来减少哈希冲突。

当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。

回到上面的源码中，我们继续看一下 treeifyBin 方法。该方法主要的作用是将普通链表转成为由 TreeNode 型节点组成的链表，并在最后调用 treeify 是将该链表转为红黑树。TreeNode 继承自 Node 类，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。我们假设树化前，链表结构如下：

HashMap 在设计之初，并没有考虑到以后会引入红黑树进行优化。所以并没有像 TreeMap 那样，要求键类实现 comparable 接口或提供相应的比较器。但由于树化过程需要比较两个键对象的大小，在键类没有实现 comparable 接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。为了解决这个问题，HashMap 是做了三步处理，确保可以比较出两个键的大小，如下：

1. 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
2. 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较
3. 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder

通过上面三次比较，最终就可以比较出孰大孰小。比较出大小后就可以构造红黑树了，最终构造出的红黑树如下：

可以看出，链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位），我们仍然可以按遍历链表的方式去遍历上面的红黑树。

5.8.2红黑树拆分

扩容后，普通节点需要重新映射，红黑树节点也不例外。按照一般的思路，我们可以先把红黑树转成链表，之后再重新映射链表即可。这种处理方式是大家比较容易想到的，但这样做会损失一定的效率。不同于上面的处理方式，HashMap 实现的思路则是在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。

以上就是红黑树拆分的逻辑，下面看一下具体实现吧：

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    /* 
     * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
     * 下面的循环是对红黑树节点进行分组，与上面类似
     */
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            /* 
             * hiHead == null 时，表明扩容后，
             * 所有节点仍在原位置，树结构不变，无需重新树化
             */
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    // 与上面类似
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

从源码上可以看得出，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。举个例子说明一下，假设扩容后，重新映射上图的红黑树，映射结果如下：

5.8.3红黑树链化

前面说过，红黑树中仍然保留了原链表节点顺序。有了这个前提，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。相关代码如下：

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // 遍历 TreeNode 链表，并用 Node 替换
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 替换节点类型
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

5.9HashMap产生死循环问题

HashMap的死循环问题会在JDK1.7中出现，主要原因是因为HashMap本身的工作机制和并发操作从而导致死循环的出现。

在JDK1.7当中，HashMap使用的数据结构是数据+链表，同时在插入元素时，采用的头插法插入。在并发场景下对HashMap进行扩容时，假设有两个线程都指向了链表的头节点，当一个线程 A 在扩容还未完成的时候，不巧的是失去了 CPU 时间片，不能获得执行机会，另外一个线程 B 抢先扩容完毕了，并且链表变成了逆序，而线程 A 还在按照顺序操作，造成指针混乱，于是出现死循环。

这个问题在 JDK1.8 中得到了解决。JDK1.8 中的 HashMap 使用了一种新的数据结构——红黑树，它能够有效地避免死循环问题的出现。此外，在 JDK1.8 中，HashMap 在插入元素时采用尾插法插入，这也有助于避免死循环问题的出现。但是在多线程环境建议使用 ConcurrentHashMap 来代替 HashMap，以确保线程安全。

5.10HashMap为什么线程不安全

有之前说的死循环问题，下面说一下数据覆盖问题：

假设两个线程A、B都在进行put操作，插入的key的散列值是相同的，当线程A计算出散列值后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了。

6.LinkedHashMap源码分析

6.1LinkedHashMap概述

LinkedHashMap 是 Java 提供的一个集合类，它继承自 HashMap，并在 HashMap 基础上维护一条双向链表，使得具备如下特性:

1. 支持遍历时会按照插入顺序有序进行迭代。
2. 支持按照元素访问顺序排序，适用于封装 LRU(Least Recently Used，最近最少使用）缓存工具。
3. 因为内部使用双向链表维护各个节点，所以遍历时的效率和元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。

6.2类声明

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
	...
}

• 可以看到，LinkedHashMap就时直接继承了HashMap，其双向链表结构就是节点内部类Entry当中定义的before 和 after 指针使节点具备双向链表的特性。

6.2LinkedHashMap使用演示

6.2.1插入顺序遍历

如下所示，我们按照顺序往 LinkedHashMap 添加元素然后进行遍历。

HashMap < String, String > map = new LinkedHashMap < > ();
map.put("a", "2");
map.put("g", "3");
map.put("r", "1");
map.put("e", "23");

for (Map.Entry < String, String > entry: map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

输出：

a:2
g:3
r:1
e:23

可以看出，LinkedHashMap 的迭代顺序是和插入顺序一致的,这一点是 HashMap 所不具备的。

6.2.2访问顺序遍历

LinkedHashMap 定义了排序模式 accessOrder(boolean 类型，默认为 false)，访问顺序则为 true，插入顺序则为 false。

为了实现访问顺序遍历，我们可以使用传入 accessOrder 属性的 LinkedHashMap 构造方法，并将 accessOrder 设置为 true，表示其具备访问有序性。

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
map.put(4, "four");
map.put(5, "five");
//访问元素2,该元素会被移动至链表末端
map.get(2);
//访问元素3,该元素会被移动至链表末端
map.get(3);
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

输出：

1 : one
4 : four
5 : five
2 : two
3 : three

可以看出，LinkedHashMap 的迭代顺序是和访问顺序一致的。

6.2.3LRU 缓存

从上一个我们可以了解到通过 LinkedHashMap 我们可以封装一个简易版的 LRU（Least Recently Used，最近最少使用） 缓存，确保当存放的元素超过容器容量时，将最近最少访问的元素移除。

具体实现思路如下：

• 继承 LinkedHashMap;
• 构造方法中指定 accessOrder 为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素；
• 重写removeEldestEntry 方法，该方法会返回一个 boolean 值，告知 LinkedHashMap 是否需要移除链表首元素（缓存容量有限）。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    /**
     * 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

测试代码如下，初始化缓存容量为 2，然后按照次序先后添加 4 个元素。

LRUCache < Integer, String > cache = new LRUCache <> (2);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
for (int i = 0; i < 4; i++) {
    System.out.println(cache.get(i));
}

输出：

null
null
three

从输出结果来看，由于缓存容量为 2 ，因此，添加第 3 个元素时，第 1 个元素会被删除。添加第 4 个元素时，第 2 个元素会被删除。

6.3LinkedHashMap的内部类Entry

LinkedHashMap 是在 HashMap 的基础上为 bucket 上的每一个节点建立一条双向链表，这就使得转为红黑树的树节点也需要具备双向链表节点的特性，即每一个树节点都需要拥有两个引用存储前驱节点和后继节点的地址，所以对于树节点类 TreeNode（因为LinkedHashMap继承了HashMap，所以LinkedHashMap当中使用的TreeNode就是父类HashMap当中的，所以TreeNode需要具有双向链表的特点） 的设计就是一个比较棘手的问题。

对此我们不妨来看看两者之间节点类的类图，可以看到:

Entry接口时Map接口当中的一个内部接口，HashMap的节点内部类Node实现了该接口。而LinkedHashMap 的节点内部类 Entry 继承了HashMap当中的节点内部类Node，并在Node的基础上添加了before 和 after 指针使节点具备双向链表的特性。

因为LinkedHashMap 的节点内部类 Entry 具有了双向链表的特点，所以HashMap 的树节点 TreeNode 继承了具备双向链表特性的 LinkedHashMap 的 Entry。

为什么 HashMap 的树节点 TreeNode 要通过 LinkedHashMap 获取双向链表的特性呢?为什么不直接在 Node 上实现前驱和后继指针呢?

第一个问题，我们都知道 LinkedHashMap 是在 HashMap 基础上对节点增加双向指针实现双向链表的特性,所以 LinkedHashMap 内部链表转红黑树时，对应的节点会转为树节点 TreeNode,为了保证使用 LinkedHashMap 时树节点具备双向链表的特性，所以树节点 TreeNode 需要继承 LinkedHashMap 的 Entry。

第二个问题，我们直接在 HashMap 的节点 Node 上直接实现前驱和后继指针,然后 TreeNode 直接继承 Node 获取双向链表的特性为什么不行呢？其实这样做也是可以的。只不过这种做法会使得使用 HashMap 时存储键值对的节点类 Node 多了两个没有必要的引用，占用没必要的内存空间。

所以，为了保证 HashMap 底层的节点类 Node 没有多余的引用，又要保证 LinkedHashMap 的节点类 Entry 拥有存储链表的引用，设计者就让 LinkedHashMap 的节点 Entry 去继承 Node 并增加存储前驱后继节点的引用 before、after，让需要用到链表特性的节点去实现需要的逻辑。然后树节点 TreeNode 再通过继承 Entry 获取 before、after 两个指针。

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

但是这样做，不也使得使用 HashMap 时的 TreeNode 多了两个没有必要的引用吗?这不也是一种空间的浪费吗？

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	//略

}

对于这个问题，作者们认为在良好的 hashCode 算法时，HashMap 转红黑树的概率不大。就算转为红黑树变为树节点，也可能会因为移除或者扩容将 TreeNode 变为 Node，所以 TreeNode 的使用概率不算很大，对于这一点资源空间的浪费是可以接受的。

6.4构造函数

LinkedHashMap 构造方法有 4 个实现也比较简单，直接调用父类即 HashMap 的构造方法完成初始化。

public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity,
    float loadFactor,
    boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

我们上面也提到了，默认情况下 accessOrder 为 false，如果我们要让 LinkedHashMap 实现键值对按照访问顺序排序(即将最近未访问的元素排在链表首部、最近访问的元素移动到链表尾部)，需要调用第 4 个构造方法将 accessOrder 设置为 true。

6.5get方法

get 方法是 LinkedHashMap 增删改查操作中唯一一个重写的方法， accessOrder 为 true 的情况下， 它会在元素查询完成之后，将当前访问的元素移到链表的末尾。

public V get(Object key) {
     Node < K, V > e;
     //获取key的键值对,若为空直接返回
     if ((e = getNode(hash(key), key)) == null)
         return null;
     //若accessOrder为true，则调用afterNodeAccess将当前元素移到链表末尾
     if (accessOrder)
         afterNodeAccess(e);
     //返回键值对的值
     return e.value;
 }

从源码可以看出，get 的执行步骤非常简单:

1. 调用父类即 HashMap 的 getNode 获取键值对，若为空则直接返回。
2. 判断 accessOrder 是否为 true，若为 true 则说明需要保证 LinkedHashMap 的链表访问有序性，执行步骤 3。
3. 调用 LinkedHashMap 重写的 afterNodeAccess 将当前元素添加到链表末尾。

关键点在于 afterNodeAccess 方法的实现，这个方法负责将元素移动到链表末尾。

void afterNodeAccess(Node < K, V > e) { // move node to last
    LinkedHashMap.Entry < K, V > last;
    //如果accessOrder 且当前节点不是链表尾节点
    if (accessOrder && (last = tail) != e) {

        //获取当前节点、以及前驱节点和后继节点
        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 指向前驱节点,这个 else其实 没有意义，因为最开头if已经确保了p不是尾结点了，自然after不会是null
            last = b;

        //如果last为空，则说明当前链表只有一个节点p，则将head指向p
        if (last == null)
            head = p;
        else {
            //反之让p的前驱指针指向尾节点，再让尾节点的前驱指针指向p
            p.before = last;
            last.after = p;
        }
        //tail指向p，自此将节点p移动到链表末尾
        tail = p;

        ++modCount;
    }
}

从源码可以看出， afterNodeAccess 方法完成了下面这些操作:

1. 如果 accessOrder 为 true 且链表尾部不为当前节点 p，我们则需要将当前节点移到链表尾部。
2. 获取当前节点 p、以及它的前驱节点 b 和后继节点 a。
3. 将当前节点 p 的后继指针设置为 null，使其和后继节点 p 断开联系。
4. 尝试将前驱节点指向后继节点，若前驱节点为空，则说明当前节点 p 就是链表首节点，故直接将后继节点 a 设置为首节点，随后我们再将 p 追加到 a 的末尾。
5. 再尝试让后继节点 a 指向前驱节点 b。
6. 上述操作让前驱节点和后继节点完成关联，并将当前节点 p 独立出来，这一步则是将当前节点 p 追加到链表末端，如果链表末端为空，则说明当前链表只有一个节点 p，所以直接让 head 指向 p 即可。
7. 上述操作已经将 p 成功到达链表末端，最后我们将 tail 指针即指向链表末端的指针指向 p 即可。

7.CopyOnWriteArrayList 源码分析

7.1CopyOnWriteArrayList 简介

在 JDK1.5 之前，如果想要使用并发安全的 List 只能选择 Vector。而 Vector 是一种老旧的集合，已经被淘汰。Vector 对于增删改查等方法基本都加了 synchronized，这种方式虽然能够保证同步，但这相当于对整个 Vector 加上了一把大锁，使得每个方法执行的时候都要去获得锁，导致性能非常低下。

JDK1.5 引入了 Java.util.concurrent（JUC）包，其中提供了很多线程安全且并发性能良好的容器，其中唯一的线程安全 List 实现就是 CopyOnWriteArrayList 。

7.2Copy-On-Write 思想

CopyOnWriteArrayList名字中的“Copy-On-Write”即写时复制，简称 COW。

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

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

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

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

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

7.3CopyOnWriteArrayList 源码分析

这里以 JDK1.8 为例，分析一下 CopyOnWriteArrayList 的底层核心源码。

CopyOnWriteArrayList 的类定义如下：

public class CopyOnWriteArrayList<E>
extends Object
implements List<E>, RandomAccess, Cloneable, Serializable
{
  //...
}

CopyOnWriteArrayList 实现了以下接口：

• List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
• RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。
• Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
• Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

7.3.1构造函数

CopyOnWriteArrayList 中有一个无参构造函数和两个有参构造函数。

// 创建一个空的 CopyOnWriteArrayList
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

// 按照集合的迭代器返回的顺序创建一个包含指定集合元素的 CopyOnWriteArrayList
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 CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

7.3.2插入元素

CopyOnWriteArrayList 的 add()方法有三个版本：

• add(E e)：在 CopyOnWriteArrayList 的尾部插入元素。
• add(int index, E element)：在 CopyOnWriteArrayList 的指定位置插入元素。
• addIfAbsent(E e)：如果指定元素不存在，那么添加该元素。如果成功添加元素则返回 true。

这里以add(E e)为例进行介绍：

// 插入元素到 CopyOnWriteArrayList 的尾部
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原来的数组
        Object[] elements = getArray();
        // 原来数组的长度
        int len = elements.length;
        // 创建一个长度+1的新数组，并将原来数组的元素复制给新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 元素放在新数组末尾
        newElements[len] = e;
        // array指向新数组
        setArray(newElements);
        return true;
    } finally {
        // 解锁
        lock.unlock();
    }
}

从上面的源码可以看出：

• add方法内部用到了 ReentrantLock 加锁，保证了同步，避免了多线程写的时候会复制出多个副本出来。锁被修饰保证了锁的内存地址肯定不会被修改，并且，释放锁的逻辑放在 finally 中，可以保证锁能被释放。
• CopyOnWriteArrayList 通过复制底层数组的方式实现写操作，即先创建一个新的数组来容纳新添加的元素，然后在新数组中进行写操作，最后将新数组赋值给底层数组的引用，替换掉旧的数组。这也就证明了我们前面说的：CopyOnWriteArrayList 线程安全的核心在于其采用了 写时复制（Copy-On-Write） 的策略。
• 每次写操作都需要通过 Arrays.copyOf 复制底层数组，时间复杂度是 O(n) 的，且会占用额外的内存空间。因此，CopyOnWriteArrayList 适用于读多写少的场景，在写操作不频繁且内存资源充足的情况下，可以提升系统的性能表现。
• CopyOnWriteArrayList 中并没有类似于 ArrayList 的 grow() 方法扩容的操作。由于每次修改都会创建一个新的内部数组副本，因此不需要像 ArrayList 那样进行扩容操作。相反，每次修改都会根据需要创建一个足够大的新数组来容纳所有元素。

7.3.3 读取元素

CopyOnWriteArrayList 的读取操作是基于内部数组 array 并没有发生实际的修改，因此在读取操作时不需要进行同步控制和锁操作，可以保证数据的安全性。这种机制下，多个线程可以同时读取列表中的元素。

// 底层数组，只能通过getArray和setArray方法访问
private transient volatile Object[] array;

public E get(int index) {
    return get(getArray(), index);
}

final Object[] getArray() {
    return array;
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

不过，get方法是弱一致性的，在某些情况下可能读到旧的元素值。

get(int index)方法是分两步进行的：

1. 通过getArray()获取当前数组的引用；
2. 直接从数组中获取下标为 index 的元素。

这个过程并没有加锁，所以在并发环境下可能出现如下情况：

1. 线程 1 调用get(int index)方法获取值，内部通过getArray()方法获取到了 array 属性值；
2. 线程 2 调用CopyOnWriteArrayList的add、set、remove 等修改方法时，内部通过setArray方法修改了array属性的值；
3. 线程 1 还是从旧的 array 数组中取值。

7.3.4获取列表中元素的个数

public int size() {
    return getArray().length;
}

CopyOnWriteArrayList中的array数组每次复制都刚好能够容纳下所有元素，并不像ArrayList那样会预留一定的空间。因此，CopyOnWriteArrayList中并没有size属性CopyOnWriteArrayList的底层数组的长度就是元素个数，因此size()方法只要返回数组长度就可以了。

7.3.5删除元素

CopyOnWriteArrayList删除元素相关的方法一共有 4 个：

1. remove(int index)：移除此列表中指定位置上的元素。将任何后续元素向左移动（从它们的索引中减去 1）。
2. boolean remove(Object o)：删除此列表中首次出现的指定元素，如果不存在该元素则返回 false。
3. boolean removeAll(Collection<?> c)：从此列表中删除指定集合中包含的所有元素。
4. void clear()：移除此列表中的所有元素。

这里以remove(int index)为例进行介绍：

public E remove(int index) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
    	   //获取当前array数组
        Object[] elements = getArray();
        // 获取当前array长度
        int len = elements.length;
        //获取指定索引的元素(旧值)
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        // 判断删除的是否是最后一个元素
        if (numMoved == 0)
        	   // 如果删除的是最后一个元素，直接复制该元素前的所有元素到新的数组
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 分段复制，将index前的元素和index+1后的元素复制到新数组
            // 新数组长度为旧数组长度-1
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            //将新数组赋值给array引用
            setArray(newElements);
        }
        return oldValue;
    } finally {
       	// 解锁
        lock.unlock();
    }
}

7.3.6判断元素是否存在

CopyOnWriteArrayList提供了两个用于判断指定元素是否在列表中的方法：

• contains(Object o)：判断是否包含指定元素。
• containsAll(Collection<?> c)：判断是否保证指定集合的全部元素。

// 判断是否包含指定元素
public boolean contains(Object o) {
    //获取当前array数组
    Object[] elements = getArray();
    //调用index尝试查找指定元素，如果返回值大于等于0，则返回true，否则返回false
    return indexOf(o, elements, 0, elements.length) >= 0;
}

// 判断是否保证指定集合的全部元素
public boolean containsAll(Collection<?> c) {
    //获取当前array数组
    Object[] elements = getArray();
    //获取数组长度
    int len = elements.length;
    //遍历指定集合
    for (Object e : c) {
        //循环调用indexOf方法判断，只要有一个没有包含就直接返回false
        if (indexOf(e, elements, 0, len) < 0)
            return false;
    }
    //最后表示全部包含或者制定集合为空集合，那么返回true
    return true;
}

8.ConcurrentHashMap源码分析

8.1概述

ConcurrentHashMap 是 HashMap 的线程安全版本，其内部和 HashMap 一样，也是采用了数组 + 链表 + 红黑树的方式来实现。

如何实现线程的安全性？加锁。但是这个锁应该怎么加呢？在 HashTable 中，是直接在 put 和 get 方法上加上了 synchronized，但是这么做锁的粒度太大，会非常影响并发性能，所以在 ConcurrentHashMap 中并没有采用这么直接简单粗暴的方法，其内部采用了非常精妙的设计，大大减少了锁的竞争，提升了并发性能。

8.2ConcurrentHashMap数据结构

在JDK1.7中，ConcurrentHashMap 的数据结构是由 Segment 数组（分段锁）和 HashEntry 数组组成的。每个 Segment 都包含一个 HashEntry 数组，其中每个 HashEntry 都是一个链表。Segment 本身继承自 ReentrantLock，因此它充当了分段锁的角色。这种设计允许多个线程同时对不同的 Segment 进行写操作，从而提高了并发性能。

Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

可以发现 Java8 的 ConcurrentHashMap 相对于 Java7 来说变化比较大，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时，链表会转换成红黑树。JDK1.8中的 ConcurrentHashMap 使用了更多的 CAS 操作和无锁技术来实现线程安全，而不再依赖分段锁。

8.3源码和问题分析

8.3.1Concurrenthashmap和HashTable实现线程安全的方式

ConcurrentHashMap 和 HashTable 都是线程安全的哈希表实现，但它们实现线程安全的方式不同。

HashTable 使用 synchronized 关键字来保证线程安全。这意味着每次对 HashTable 进行修改操作时，都需要获取一个全局锁。这种方式可以确保线程安全，但在高并发情况下，锁竞争激烈会导致性能下降。

相比之下，ConcurrentHashMap 采用了更加高效的方式来实现线程安全。在 JDK1.7 中，ConcurrentHashMap 采用分段锁技术，在多线程场景下，锁的竞争更加细粒度，可以提供更好的并发性能。在JDK1.8中，ConcurrentHashMap 不再使用 Segment 数组，而是直接使用一个 Node 数组。每个 Node 都是一个链表，当链表长度超过一定阈值时，会转换为红黑树以提高查找效率。JDK1.8中的 ConcurrentHashMap 使用了更多的 CAS 操作和无锁技术来实现线程安全。

CAS（Compare and Swap）是一种无锁算法，它通过比较内存中的值与预期值是否相等来决定是否执行更新操作。这种方式可以避免使用显式锁，从而减少锁竞争带来的开销。

在JDK1.8中的 ConcurrentHashMap 中，CAS 操作被用于实现无锁的读操作和部分写操作。例如，在扩容时，新建一个更大的数组并将旧数组中的元素复制到新数组中时，就使用了 CAS 操作来保证线程安全。

此外，JDK1.8中的 ConcurrentHashMap 还使用了无锁技术来实现部分写操作。例如，在向哈希表中添加元素时，如果目标桶为空，则可以使用无锁技术直接将新元素插入到桶中。

8.3.2如何用 CAS 保证数组初始化的安全

下面就是初始化的方法：

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        //　如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。
        if ((sc = sizeCtl) < 0)
            // 让出 CPU 使用权
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

这里面有一个非常重要的变量 sizeCtl，这个变量对理解整个 ConcurrentHashMap 的原理非常重要。

sizeCtl 有四个含义：

• sizeCtl<-1 表示有 N-1 个线程正在执行扩容操作，如 -2 就表示有 2-1 个线程正在扩容。
• sizeCtl=-1 占位符，表示当前正在初始化数组。
• sizeCtl=0 默认状态，表示数组还没有被初始化。
• sizeCtl>0 记录下一次需要扩容的大小。

知道了这个变量的含义，上面的方法就好理解了，第二个分支采用了 CAS 操作，因为 SIZECTL 默认为 0，所以这里如果可以替换成功，则当前线程可以执行初始化操作，CAS 失败，说明其他线程抢先一步把 sizeCtl 改为了 -1。扩容成功之后会把下一次扩容的阈值赋值给 sc，即 sizeClt。

8.3.3put 操作如何保证数组元素的可见性

ConcurrentHashMap 中存储数据采用的 Node 数组是采用了 volatile 来修饰的，但是这只能保证数组的引用在不同线程之间是可用的，并不能保证数组内部的元素在各个线程之间也是可见的，所以这里我们判定某一个下标是否有元素，并不能直接通过下标来访问，那么应该如何访问呢？源码给你答案：

1. 根据 key 计算出 hashcode 。
2. 判断是否需要进行初始化。
3. 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
5. 如果都不满足，则利用 synchronized 锁写入数据。
6. 如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥64 时才会将链表转换为红黑树。

可以看到，这里是通过 tabAt 方法来获取元素，而 tableAt 方法实际上就是一个 CAS 操作。

如果发现当前节点元素为空，也是通过 CAS 操作（casTabAt）来存储当前元素。

如果当前节点元素不为空，则会使用 synchronized 关键字锁住当前节点，并进行对应的设值操作。

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key 和 value 不能为空
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        // f = 目标位置元素
        Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值
        if (tab == null || (n = tab.length) == 0)
            // 数组桶为空，初始化数组桶（自旋+CAS)
            tab = initTable();
        //tabAt为nul1表示当前位置没有元素，采用Unsafe方法获取元素而不是直接tab[i]
	   //volatile修 饰数组只针对数组的引用保证可见，对内部元素则不一定。
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                break;  // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 使用 synchronized 加锁加入节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 说明是链表
                    if (fh >= 0) {
                        binCount = 1;
                        // 循环加入新的或者覆盖节点
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 红黑树
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

8.3.4为什么ConcurrentHashMap不允许插入空值

在向ConcurrentHashMap当中添加元素时，调用put方法：

public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        ...
    }

即当插入的键值对数据的key或者是value为空时，则直接抛出NPE异常。

为什么不允许插入null值呢？

原因是因为当在ConcurrentHashMap当中插入null值得时候会引起歧义。当在ConcurrentHashMap当中插入null值，那么取值的时候就会产生两个结果：

1. 值没有在集合中，所以返回null
2. 值就是null，所以返回的就是他原本的null值

这样就产生了歧义问题。

为什么HashMap不担心产生起义问题？

因为HashMap的设计是给单线程使用的，如果取到null值，就可以调用HashMap的containsKey()方法来区分null值到底是插入的null值，还是不存在当前值。

而在ConcurrentHashMap是多线程情况下使用的，情况更加复杂，如一个线程调用ConcurrentHashMap的containsKey(key)方法，期望返回的值是false，但是另一个线程调用ConcurrentHashMap的put()方法，插入了一个key，并且存入的是null。则第一个线程返回的就是true。则上述产生的歧义不能够被证伪。

总结：ConcurrentHashMap在源码中加入不允许插入null值的设计，主要目的是为了防止并发场景下的歧义问题。