在线目录生成工具

目录

0.前言

个人学习、整理和记录Java容器相关知识点用。其中大部分内容来自以下地址,表示感谢。
CS-Notes
InfoQ-java集合之ArrayList源码解读
美团技术团队-Java 8系列之重新认识HashMap

1.概览

容器主要包括Collection和Map两种,Collection存储着对象的集合,而Map存储这键值对(两个对象)的映射表。

1.1 Set

TreeSet:基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如HashSet,HashSet查找时间复杂度为O(1)a,TreeSet复杂度为O(logN)。
HashSet:基于哈西表实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,也就是说使用Iterator遍历HashSet得到的结果是不确定的。
LinkedHashSet:具有HashSet的查找效率,并且内部使用双向链表维护元素的插入顺序。

1.2 List

ArrayList:基于动态数组实现,支持随机访问。适用于查询多,删除插入少的场景。
Vector:和ArrayList类似,但是它是线程安全的。
CopyOnWriteArrayList:读写分离。
LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList还可以用作栈、队列和双向队列。适用于查询少,删除插入多的场景。

1.3 Queue

LinkedList:可以用它来实现双向队列。
PriorityQueue:基于堆结构实现,可以用来实现优先队列。

1.4 Map

TreeMap:基于红黑树实现。
HashMap:基于哈希表实现。
ConcurrentHashMap:和HashMap类似,但是是线程安全的。
LinkedHashMap:使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用顺序(LRU)。

2 常用容器分析

默认基于Jdk1.8。

2.1 ArrayList

继承关系

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


实现了RandomAccess接口,这是一个标记接口,官方解释是只要List实现了这个接口,就能支持随机访问,随机访问指的是可以使用索引遍历,即用for循环遍历数据,比使用iterator遍历数据更高效。
实现了Cloneable接口,这也是一个标记接口,表示该对象能被clone,即可以使用Object.clone()方法。如果没有实现Cloneable的类对象调用clone()方法会抛出CloneNotSupportException。且是深拷贝。
实现了Serializable接口,这也是一个标记接口,用于标记实现类可以序列化。

字段

ArrayList的字段以及说明如下:

    /**
    * 序列化版本标识,序列化和反序列化时使用
    */
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认的数据容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于ArrayList空实例的共享空数组实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
      * 用于默认大小空实例的共享空数组实例。
      * 我们将DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA区别开来
      * 以便在添加第一个元素时知道要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存放元素的数组
     * 备注:字段不设置为私有,是为了方便内部类的访问
     * 思考:为什么不是E[]呢?
     */
    transient Object[] elementData; 

    /**
     * 数组元素个数
     */
    private int size;

构造方法

有三个构造方法

//1
// 创建一个容量为10的ArrayList
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//2
/**
    * 1、创建ArrayList强制使用范型,避免使用原生类型引起类型不安全的问题
    * 2、java7之后的jdk增强了类型推导,建议使用new ArrayList<>(),最好不使用new ArrayList<E>
    */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//3
 // 使用Collection的实现比如Set,List创建一个ArrayList
     // 通常是Collection的实现进行相互转换
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

添加

有两种添加方式:单个添加(添加特定元素)和批量添加(添加集合)。
单个添加的流程如图:

相关源码如下:

/**
  * 在ArrayList结尾添加元素
  */
public boolean add(E e) {
    // 根据size处理容量
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    // 如果使用ArrayList()创建,默认容量=DEFAULT_CAPACITY=10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // minCapacity为此时elementData必须的最小长度
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    // 修改次数+1,用于fail-fast处理
    modCount++;
    // 如果minCapacity大于elementData的长度,则进行扩容处理
    if (minCapacity - elementData.length > 0)
        // 扩容,可能会引起溢出问题
        grow(minCapacity);
}
// ArrayList动态扩容机制的核心
private void grow(int minCapacity) {
    // 可能存在整型溢出
    int oldCapacity = elementData.length;
    // 容量默认扩大1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        // 可能1:newCapacity<0整型溢出
        // 可能2:newCapacity<minCapacity
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 数组深拷贝
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        // 说明已经整型溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
/**
  * 在ArrayList特定位置添加单个元素
  * 思考:add(E e)没有调用add(int index, E element),个人猜测是出于性能的考虑
  * 毕竟基于数组进行插入操作可能存在性能问题
  */
public void add(int index, E element) {
    // 检查位置是否合法
    rangeCheckForAdd(index);

    // 跟add(E e)中处理方式类似
    ensureCapacityInternal(size + 1); 
    // 将elementData中位置为index位置及其后面的元素都向后移动一个下标(底层是native方法,使用cpp直接操作内存。)
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

添加元素时,先使用ensureCapacityInternal()方法来保证容量足够,如果不够,使用grow()方法进行扩容,新容量的大小约为老容量的1.5倍。扩容操作需要调用Arrays.copyOf()把原数组整个复制到新数组中,这个操作代价很高,因此最好在创建ArrayList对象时就指定大概的容量大小,减少扩容操作的次数。

批量添加的相关代码如下:

    //
    public boolean addAll(Collection<? extends E> c) {
        // 集合转化成数组
        Object[] a = c.toArray();
        int numNew = a.length;
        // 跟add(E e)中处理方式类似
        ensureCapacityInternal(size + numNew); 
        // 将集合内的元素复制到elementData中,覆盖[size, size+numNew)的元素
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查位置是否合法
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew); 

        int numMoved = size - index;
        if (numMoved > 0)
            // 将elementData中位置为index及其以后的元素都向后移动numNew个位置
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

        // 将集合内的元素复制到elementData中,覆盖[index, index+numNew)的元素 
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

删除

删除可以分为四种:单个删除(删除特定元素、特定下标)、批量删除(删除集合中的元素)、批量保留(批量删除除集合外的元素)、清空。
单个删除,相关代码如下:

    // 删除ArrayList中第一次出现的特定元素
    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++)
                // 比较对象时依赖equals方法
                // 因此类型变量E对应的类注意重写equlas方法
                // 重写时注意遵守规范,具体参考effective java第三版的第10、11两条规则
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    // 根据下标删除元素
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将elemenData中index+1及其后面的元素都向前移动一个下标
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 根据上一步的操作, size-1位置的对象向前移动了一个下标
        // 如果没有elementData[--size]==null,可能会导致内存泄漏
        // 试想,ArrayList被add了100个对象,然后被remove了100次。按照GC的机制来说,100个对象应该可以被GC掉(假设没有对象对象),但是由于还存在ArrayList的实例引用,对应的100个对象就无法删除
        elementData[--size] = null; 
    }

    // 根据下标删除元素
    // 注意:java5后引入自动装箱、拆箱的机制,因此产生了一个有趣的问题:
    // 当类型变量为Integer的ArrayList调用remove时,可能调用remove(Object),也可能调用remove(Index)
    // 一定要注意测试是否符合自己的预期
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        // 如果被删除元素不是ArrayList的最后一个元素
        if (numMoved > 0)
             // 对应下标之后的元素向前移动一个下标
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 最后一个元素只为null,方便GC
        elementData[--size] = null; 

        return oldValue;
    }

需要调用System.arraycopy()将index+1后面的元素都复制到index位置上,该操作的时间复杂度为O(N),可以看到ArrayList删除元素的代价是比较高的。

批量删除和清空

    // 批量删除ArrayList和集合c都存在的元素
    public boolean removeAll(Collection<?> c) {
        // 非空校验
        Objects.requireNonNull(c);
        // 批量删除
        return batchRemove(c, false);
    }

    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++)
                if (c.contains(elementData[r]) == complement)
                    // 把需要保留的元素前置
                    elementData[w++] = elementData[r];
        } finally {
            // 即使c.contains抛异常,也要保持跟AbstractCollection行为的兼容性
            // 备注:ArrayList重写了AbstractCollection中的removeAll方法,removeAll调用了batchRemove
            if (r != size) {
                // 备注1:可能是上面的for循环出现了异常
                // 备注2:可能是其它线程添加了元素。
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                for (int i = w; i < size; i++)
                    // 跟fastRemove(int index)里面的操作类似,防止内存泄漏
                    elementData[i] = null;
                // 思考:为什么addAll的modCount+1,而removeAll的modCoun+size-w
                // 个人以为modCount只是做标记做了结构的修改并且用来做校验。
                // 因此+1,+2 +size-w并没有本质区别
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

 // 思考:上面是按照元素进行批量删除,如何按照下标区间进行批量删除呢?
批量保留

    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        // 批量保留
        return batchRemove(c, true);
    }

    public void clear() {
        modCount++;
        // 清空ArrayList里面所有的元素
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

查找

    // 返回元素第一次出现的下标
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    // 返回最后一次出现的位置
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

序列化

ArrayList基于数组实现,并且具有动态扩容特性,因此保存元素的数组不一定都会被使用,所以不用直接序列化elementData,而是根据size序列化包含的元素,忽略数组中的其他位置,提高效率并节省空间,通过使用writeObject() 和 readObject()方法来实现的。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // fail-fast,后续判断是否有并发处理
        int expectedModCount = modCount;
        // 序列化没有标记为static、transient的字段,包括size等。
        s.defaultWriteObject();

        // 没有意义,可以忽略
        s.writeInt(size);

        // 序列化元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            // ArrayList被并发处理,发生结构性修改
            throw new ConcurrentModificationException();
        }
    }
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 反序列化没有标记为static、transient的字段,包括size等
        s.defaultReadObject();

        // 可以忽略,跟writeObject里面的方法对应
        s.readInt(); 

        if (size > 0) {
            // 数组扩容
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 反序列化元素并填充到数组中
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

保存元素的数组elementData使用transient修饰,该关键字声明数组默认不会被序列化。

transient Object[] elementData; // non-private to simplify nested class access

Fail-Fast

modCount用来记录ArrayList结构发生变化的次数。结构发生变化是指添加或删除至少一个元素的所有操作,或者是调整内部数组的大小,仅仅只是设置元素的值不算结构变化。
在进行序列化或者迭代等操作时,需要比较操作前后modCount是否改变,如果改变了需要抛出ConcurrentModificationException。

2.2 CopyOnWriteArrayList

是一个并发安全的ArrayList,可以做到读写分离。写操作在一个复制的数组上进行,读操作在原始数组上进行,所以能做到读写分离,互不影响。

添加

@Override
public boolean add(E e) {
    /**
     * 增加元素 e 到数组的末尾
     * 操作步骤:
     *  1. 获取全局的 reentrantLock
     *  2. 将原来的 array1 copy 到一个 array.length + 1 的数组 array2 里面
     *  3. 将 先添加的元素e添加到新数组 array2 的最后一个空间里面 (array2[array2.length - 1] = e)
     *  4. 将 新数组 array2 赋值给 CopyOnWriteArrayList 中的 array
     */
    final ReentrantLock lock = this.lock;
    lock.lock();                                                    // 1. 获取 全局 lock
    try{
        Object[] elements = getArray();                             // 2. 获取原来的数组
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);    // 3. 新建一个 array2 将原来的数据赋值到这个新建的数组里面
        newElements[len] = e;                                       // 4. 将 e 赋值给 array2的最后一个空间里面
        setArray(newElements);                                      // 5. 将新数组 array2 赋值给 CopyOnWriteArrayList 中的 array
        return true;
    }finally {
        lock.unlock();                                              // 6. 释放锁
    }

}

 @Override
    public void add(int index, E element) {
        /**
         * 将元素 e 插入到数组 指定的索引下标 index 下
         * 操作步骤:
         *      1. 获取全局的锁
         *      2. 获取 CopyOnWriteArrayList 的 array, 及 array.length
         *      3. 进行参数校验 (index > len || index < 0) 则直接抛异常 -> 说明元素的插入只能在 0 - array.length 之间(包含两个端点)
         *      4. 获取插入点 index 与 array.length 之间的步长, 进行分类讨论
         *          1) 插入的数据正好在 原array数组的后一个节点 (numMoved = len), 则直接新建一个 array, 将原来的 array copy 过来
         *          2) 插入的 index 满足 0 <= index <= len - 1, 则新建一个数组, 原来 o -> index(index不包含) 拷贝来, index后面的数据拷贝到新数组的 index + 1 的空间
         *      5. 将 e 设置到 新 array 的 index 位置
         *      6. 将 新 array 设置到 CopyOnWriteArrayList 里面
         */
        final ReentrantLock lock = this.lock;
        lock.lock();                                                                    // 1. 获取全局的锁
        try{
            Object[] elements = getArray();
            int len = elements.length;
            if(index > len || index < 0){
                throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + len);
            }
            Object[] newElements;
            int numMoved = len - index;
            if(numMoved == 0){ // 走到这一步, 说明 数据是插入到 oldArray.length(这个值是指下标) 位置上的元素
                newElements = Arrays.copyOf(elements, len + 1); // 直接拷贝原数组到一个新的 array 数组中, 这个数组的长度是 len + 1
            }else{
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index); // 将原数组 index 前的数组都拷贝到新的数组里面
                System.arraycopy(elements, index, newElements, index + 1, numMoved); // 将原数组 index 以后的元素都 copy到新的数组里面(包括index位置的元素)
            }
            newElements[index] = element; // 将 index 赋值 element
            setArray(newElements); // 将 新的 array set到 CopyOnWriteArrayList 上
        }finally {
            lock.unlock();
        }

    }

删除

@Override
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){ // 说明删除的元素的位置在 len - 1 上, 直接拷贝原数组的前 len - 1 个元素
            setArray(Arrays.copyOf(elements, len - 1));
        }else{
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index); // 拷贝原数组 0 - index之间的元素 (index 不拷贝)
            System.arraycopy(elements, index + 1, newElements, index, numMoved); // 拷贝原数组 index+1 到末尾之间的元素 (index+1也进行拷贝)
            setArray(newElements);
        }
    }finally {
        lock.unlock();
    }
    return null;
}

public boolean remove(Object o){
    Object[] snapshot = getArray();
    // 获取 index 在 snapshot 中的位置, -1 表示不存在
    int index = indexOf(o, snapshot, 0, snapshot.length);
    return (index < 0) ? false : remove(o, snapshot, index);
}

/**
 * A version of remove(Object) using the strong hint that given
 * recent snapshot contains o at the given index
 */
private boolean remove(Object o, Object[] snapshot, int index){
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        // findIndex: <- 这个用法平时用的比较少, 在这里, 只要 break findIndex, 那 if(snapshot != current) 这里括号里面的其他代码就不执行了, 直接跳到括号外面, 建议写个小demo试一下
        if(snapshot != current) findIndex:{ // snapshot != current 表示数组被另外一个线程操作过, 有变化
            /**
             * 下面的操作是发生在 调用方法 "remove(Object o)" 中的 "indexOf"后 , 数组 array 发生变化而做的查询修正工作
             * 主要分 下面 4 中情况:
             *  1. 从 index,len 中取出一个较小的值 prefix, 从 current的prefix前个元素中寻找元素 o, 找到后, 直接 break, 执行下面的操作
             *  2. 若 index >= len, 则说明 元素 o 在另外的线程中已经被删除, 直接 return
             *  3. current[index] = o, 则说明, index 位置上的元素 o 还在那边, 直接 break
             *  4. 最后 在 index 与 len 之间寻找元素, 找到位置直接接下来的代码, 没找到 直接 return
             */
            int prefix = Math.min(index, len);
            for(int i = 0; i < prefix; i++){
                // 找出 current 数组里面 元素 o 所在的位置 i, 并且赋值给 index
                if(current[i] != snapshot[i] && eq(o, current[i])){
                    index = i;
                    break findIndex;
                }
            }

            if(index >= len){ // index >= len 表示元素 o 已经被删除掉
                return false;
            }
            if(current[index] == o){ // 元素 o 也在数组 current 的 index 位置
                break findIndex;
            }
            index = indexOf(o, current, index, len); // 在 current 中寻找元素 o 所在的位置 (这里不会出现 index > len 的情况, 上面的代码中已经做了判断)
            if(index < 0){ // 要删除的元素 在另外的线程中被删除掉了, 直接 return false
                return false;
            }
        }

        Object[] newElements = new Object[len - 1]; // 新建一个 len - 1 长度的数组
        System.arraycopy(current, 0, newElements, 0, index); // 拷贝老数组前 index 个元素
        System.arraycopy(current, index + 1, newElements, index, len - index - 1); // 拷贝 老数组 index + 1 后的元素 ( index + 1 包含)
        setArray(newElements);
        return true;
    }finally {
        lock.unlock();
    }
}

使用场景

CopyOnWriteArrayList在写操作的同时允许读操作,大大提升了读操作的性能,因此很适合读多写少的应用场景。
但是缺陷也比较明显:
1.内存占用:在写操作时需要复制一个新的数组,使得内存占用为原来的两倍左右;
2.数据不一致:读操作不能读取实时性的数据,因为部分写操作的数据还没有同步到读数组中。
所以CopyInWriteArrayList不适用内存敏感以及对实时性要求很高的场景。

2.3 HashMap

继承关系

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 
    {   }


实现了Cloneable接口,这也是一个标记接口,表示该对象能被clone,即可以使用Object.clone()方法。如果没有实现Cloneable的类对象调用clone()方法会抛出CloneNotSupportException。且是深拷贝。
实现了Serializable接口,这也是一个标记接口,用于标记实现类可以序列化。

存储结构

HashMap是数组+链表+红黑树(JDK8增加的红黑树)实现,如下图:

存储数据的是数组Node[] table,数组里面的元素是链表或者红黑树。Node是HashMap的一个内部类,实现了Map.Entry接口,本质上就是一个映射(键值对),上图的每个黑色圆点就是一个Node对象。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

JDK8增加红黑树,是为了当出现拉链过长(哈希值集中在某几个桶位置)时,也能够利用红黑树快速增删改查的特点,提升HashMap的性能

字段

列举几个关键字段

//默认值
//数组table的默认大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组的最大大小
static final int MAXIMUM_CAPACITY = 1 << 30;
//装载因子的默认大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转红黑树的阈值,JDK8新加
static final int TREEIFY_THRESHOLD = 8;


//实际使用的值
//存储数据的数组,数组的元素是链表或者是红黑树,长度是2的n次方
transient Node<K,V>[] table;

//键值对的数量
transient int size;

//size的临界值,当size大于等于这个值时,需要进行扩容操作
int threshold;

//装载因子,threshold= loadFactor*table的大小
final float loadFactor;

//修改次数,用来记录内部结构发生变化,主要用于迭代的快速失败,同ArrayList
 transient int modCount;

功能实现

主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个点展开。

1.确定哈希桶数组索引位置

不管增加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。HashMap的数据结构是数组和链表的结合,所以我们希望这个HashMap里面的元素位置尽量均匀些,尽量每个位置上的元素数量只有一个,这种情况下,当我们用hash算法求得这个位置的时候,就马上可以知道对应位置的元素,不用遍历链表,大大优化了查询效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。下面是java源码:

方法一:
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二:
static int indexFor(int h, int length) {  //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

hash算法本质上是三步:取key的HashCode值、高位运算、取模运算。
对于任意给定的对象,只要他的hashCode()返回值相同,那么程序调用方法一所计算得到的hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算(h%len),这样一来,元素的分布相对来说是比较均匀的。但是,取模运算的消耗是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处。这个方法非常巧妙,它通过h&(table.len - 1)来得到该对象的保存位,而hashMap规定数组的长度总是2的n次方,当len总是2的n次方时,h&(len-1)等价于取模运算h%len,但是具有更高的效率。
在JDK8的实现中,优化了高位运算的算法,通过hashCode的高16位异或低16位实现:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑,这么做可以在数组table的len比较小的时候,也能保证高低bit都参与到hash的计算中,同时不会有太大的开销。

2.分析HashMap的put方法流程

流程图如下:

①判断键值对数组table是否为空或null,如果是执行resize进行扩容;
②根据键key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果不为空,转向③;
③判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;
④判断table[i]是否是treeBode红黑树,如果是,则直接在树中插入键值对,否则转向⑤;
⑤遍历table[i],判断链表长度是否大于8,大于8就把链表转换成红黑树,在树中执行插入操作,否则在链表中执行插入,遍历过程中若发现key已经存在,直接覆盖value即可;
⑥插入成功后,判断实际存在的键值对数量size是否超过了最大容量threshold,如果超过,进行扩容。
JDK8中的HashMap的put方法源码如下:

1 public V put(K key, V value) {
 2     // 对key的hashCode()做hash
 3     return putVal(hash(key), key, value, false, true);
 4 }
 5 
 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 7                boolean evict) {
 8     Node<K,V>[] tab; Node<K,V> p; int n, i;
 9     // 步骤①:tab为空则创建
10     if ((tab = table) == null || (n = tab.length) == 0)
11         n = (tab = resize()).length;
12     // 步骤②:计算index,并对null做处理 
13     if ((p = tab[i = (n - 1) & hash]) == null) 
14         tab[i] = newNode(hash, key, value, null);
15     else {
16         Node<K,V> e; K k;
17         // 步骤③:节点key存在,直接覆盖value
18         if (p.hash == hash &&
19             ((k = p.key) == key || (key != null && key.equals(k))))
20             e = p;
21         // 步骤④:判断该链为红黑树
22         else if (p instanceof TreeNode)
23             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24         // 步骤⑤:该链为链表
25         else {
26             for (int binCount = 0; ; ++binCount) {
27                 if ((e = p.next) == null) {
28                     p.next = newNode(hash, key,value,null);
                        //链表长度大于8转换为红黑树进行处理
29                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
30                         treeifyBin(tab, hash);
31                     break;
32                 }
                    // key已经存在直接覆盖value
33                 if (e.hash == hash &&
34                     ((k = e.key) == key || (key != null && key.equals(k)))) 
35							break;
36                 p = e;
37             }
38         }
39         
40         if (e != null) { // existing mapping for key
41             V oldValue = e.value;
42             if (!onlyIfAbsent || oldValue == null)
43                 e.value = value;
44             afterNodeAccess(e);
45             return oldValue;
46         }
47     }

48     ++modCount;
49     // 步骤⑥:超过最大容量 就扩容
50     if (++size > threshold)
51         resize();
52     afterNodeInsertion(evict);
53     return null;
54 }

扩容机制

扩容(resize)就是重新计算容量,Java的数组是无法自动扩容的,所以使用一个新的数组代替已有的数组,就像是用小桶装水,如果要装更多的水,就需要换大桶。
由于JDK的resize融入了红黑树相关的逻辑,比较复杂,为了好理解使用JDK7的代码,本质上区别不大。

 1 void resize(int newCapacity) {   //传入新的容量
 2     Entry[] oldTable = table;    //引用扩容前的Entry数组
 3     int oldCapacity = oldTable.length;         
 4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
 5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
 6         return;
 7     }
 8  
 9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
10     transfer(newTable);                         //!!将数据转移到新的Entry数组里
11     table = newTable;                           //HashMap的table属性引用新的Entry数组
12     threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }

这里使用一个容量更大的数组来代替已有的小容量数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

 1 void transfer(Entry[] newTable) {
 2     Entry[] src = table;                   //src引用了旧的Entry数组
 3     int newCapacity = newTable.length;
 4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
 5         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
 6         if (e != null) {
 7             src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
 8             do {
 9                 Entry<K,V> next = e.next;
10                 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
11                 e.next = newTable[i]; //标记[1]
12                 newTable[i] = e;      //将元素放在数组上
13                 e = next;             //访问下一个Entry链上的元素
14             } while (e != null);
15         }
16     }
17 } 

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突),这一点和JDK8有点区别。在就数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能放到了新数组不同的位置。
说说JDK8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(长度是原来的2倍),所以,元素的新位置要么是原位置,要么是原位置再移动2次幂的位置,具体看下图。n为table的长度,图a表示扩容前的key1和key2两种key确定索引位置的示例,图b表示扩容后key1和key2两种key确定索引位置的示例,hash1表示key1对应的哈希与高位运算结果。

元素在重新计算hash后,因为n变成了2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

因此在扩充HashMap时,不需要想JDK7那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0,0索引不变,1索引变成“原索引+oldCap”

小结

1.扩容特别耗性能,所以使用HashMap时可以先估算map大小,初始化时给一个大致的数值,避免频繁扩容;
2.负载因子0.75是平衡时间和空间后的取值,可以修改,也可以大于1,但是一般不建议修改,除非情况特殊且你明确知道你的修改代表什么(如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值);
3.HashMap是线程不安全的,并发情况使用ConcurrentHashMap;
4.JDK8引入的红黑树,很大程度上优化了HashMap的性能。

为什么要求table的长度为2的n次方:
主要有两个原因,1.确定索引的时候,当len=2的幂次,h%len等价h & (len - 1),但是&运行效率高于%运算;2.扩容的时候,可以快速确定元素的新索引位置(原位置 或者 原位置+oldCap)。

2.4 ConcurrentHashMap

比较HashMap、HashTable、ConcurrentHashMap。
HashMap不是线程安全的,不能在并发的情况下使用。
HashTable是线程安全的,但是是通过整个加锁的方式,当一个线程在写操作时,其他的线程不能读写。效率不够。
ConcurrentHashMap线程安全,使用的是分段锁实现,每一个锁维护多个桶,当写数据时,其他桶位置依然可以进行读写,支持了并发读写,效率得到提高。

ConcurrentHashMap的实现,是在HashMap的基础上增加了分段锁,具体细节不再展开。