集合实现原理汇总

见得乐

发布于 2022-09-08 15:51:24

2490

发布于 2022-09-08 15:51:24

文章被收录于专栏：LearnPathLearnPath

集合框架图

ArrayList实现原理

对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。

private transient Object[] elementData;

ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。

调整数组容量

ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现:

    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
            // any size if real element table
            ? 0
            // larger than default for empty table. It's already supposed to be
            // at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //此处进行1.5倍扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

Fail-Fast机制

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。具体请参看下面HashMap的实现原理，也实现了Fail-Fast机制。

总结

ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素。
底层使用数组实现，顺序存储。
该集合是可变长度数组，数组扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量增长是其容量的1.5倍，这种操作的代价很高。
采用了Fail-Fast机制，面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险

详细实现原理博客链接：http://zhangshixi.iteye.com/blog/674856

LinkedList实现原理要点概括

LinkedList数据结构

LinkedList是List和Deque接口的双向链表的实现。实现了所有可选列表操作，并允许包括null值。

    private static class Node<E> {
        E item;    // 当前节点所包含的值
        Node<E> next;   //下一个节点
        Node<E> prev;    //上一个节点

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

实现随机访问

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    //返回指定索引位置的节点
    Node<E> node(int index) {
        // assert isElementIndex(index);
        //折半思想，当index < size/2时，从列表首节点向后查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {  //当index >= size/2时，从列表尾节点向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index

Fail-Fast机制

LinkedList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

总结

LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
底层的数据结构是基于双向链表的，该数据结构我们称为节点，顺序存储。
双向链表节点对应的类Node的实例，Node中包含成员变量：previous，next，item。其中，previous是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。 4.索引查找时通过与中间值比较遍历前半段或后半段从而节省时间。

详细实现原理博客链接：http://www.cnblogs.com/CherishFX/p/4734490.html

Vector实现原理

和ArrayList不同，Vector中的操作是线程安全的，但速度慢，在每个方法前都加上了锁（即synchronized关键字）。 - Vector实际上是通过一个数组去保存数据的。当我们构造Vecotr时；若使用默认构造函数，则Vector的默认容量大小是10。 - 当Vector容量不足以容纳全部元素时，Vector的容量会增加。若容量增加系数 >0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。 - Vector的克隆函数，即是将全部元素克隆到一个数组中。

详细实现原理博客链接：http://www.cnblogs.com/skywang12345/p/3308833.html

CopyOnWriteArrayList实现原理

与 Vector一样，CopyOnWriteArrayList也可以认为是ArrayList的线程安全版，不同之处在于当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWriteArrayList进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWriteArrayList是一种读写分离的思想，读和写不同的容器。

这种机制让CopyOnWriteArrayList可以对读操作不加锁，只对写的有关操作加锁（即方法前加synchronized关键字）这就使CopyOnWriteArrayList的读效率远高于Vector。

CopyOnWriteArrayList的理念比较类似读写分离，适合读多写少的多线程场景。但要注意，CopyOnWriteArrayList只能保证数据的最终一致性，并不能保证数据的实时一致性，执行读操作时是有可能会读到失效的数据的。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

与Vector区别： - 二者均是线程安全的。 - CopyOnWriteArrayList不能保证读的实时线程安全，CopyOnWriteArrayList读性能远高于Vector。CopyOnWriteArrayList占用更多的内存空间

详细实现原理博客链接：http://www.cnblogs.com/dolphin0520/p/3938914.html

HashMap实现原理

HashMap的数据结构

HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结构，但是在jdk1.8里加入了红黑树的实现，当链表的长度大于8时，转换为红黑树的结构。如图所示：

在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

    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) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。 HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。在HashMap中，哈希桶数组table的长度length大小必须为2的n次方

确定哈希桶数组索引位置

//方法一：
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值、高位运算、取模运算。

HashMap的put方法实现

put函数大致的思路为： 1. 对key的hashCode()做hash，然后再计算index; 2. 如果没碰撞直接放到bucket里； 3. 如果碰撞了，以链表的形式存在buckets后； 4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树； 5. 如果节点已经存在就替换old value(保证key的唯一性) 6. 如果bucket满了(超过load factor*current capacity)，就要resize。

HashMap的get方法实现

思路如下： 1. bucket里的第一个节点，直接命中； 2. 如果有冲突，则通过key.equals(k)去查找对应的entry 若为树，则在树中通过key.equals(k)查找，O(logn)；若为链表，则在链表中通过key.equals(k)查找，O(n)。

Fail-Fast机制

java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {  
    expectedModCount = modCount;  
    if (size > 0) { // advance to first entry  
    Entry[] t = table;  
    while (index < t.length && (next = t[index++]) == null)  
        ;  
    }  
}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：注意到modCount声明为volatile，保证线程之间修改的可见性。

final Entry<K,V> nextEntry() {     
    if (modCount != expectedModCount)     
        throw new ConcurrentModificationException();

迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

总结

HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。
底层使用数组实现，数组中每一项是个链表，即数组和链表的结合体。
HashMap在底层将key-value当成一个整体进行处理。HashMap底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置，当链表的长度大于8时，转换为红黑树的结构；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
HashMap进行数组扩容，两倍扩容。需要重新计算扩容后每个元素在数组中的位置，很耗性能。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历
采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常

详细实现原理博客链接：http://blog.csdn.net/richard_jason/article/details/53887222

Hashtable实现原理

总结： 1. Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键 2. 底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体 3. Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。 4. synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，即对每个方法操作都加上了synchronized关键字

详细实现原理博客链接：http://blog.csdn.net/zheng0518/article/details/42199477

ConcurrentHashMap实现原理

ConcurrentHashMap数据结构

ConcurrentHashMap相比HashMap而言，是多线程安全的，其底层数据与HashMap的数据结构相同，数据结构如下:

ConcurrentHashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树是为了提高查找效率。

ConcurrentHashMap的put方法实现

put函数底层调用了putVal进行数据的插入，对于putVal函数的流程大体如下。 1. 判断存储的key、value是否为空，若为空，则抛出异常，否则，进入步骤2 2. 计算key的hash值，随后进入无限循环，该无限循环可以确保成功插入数据，若table表为空或者长度为0，则初始化table表，否则，进入步骤3 3. 根据key的hash值取出table表中的结点元素，若取出的结点为空（该桶为空），则使用CAS将key、value、hash值生成的结点放入桶中。否则，进入步骤4 4. 若该结点的的hash值为MOVED(-1)，则对该桶中的结点进行转移，否则，进入步骤⑤ 5. 对桶中的第一个结点（即table表中的结点）进行加锁，对该桶进行遍历，桶中的结点的hash值与key值与给定的hash值和key值相等，则根据标识选择是否进行更新操作（用给定的value值替换该结点的value值），若遍历完桶仍没有找到hash值与key值和指定的hash值与key值相等的结点，则直接新生一个结点并赋值为之前最后一个结点的下一个结点。进入步骤6 6. 若binCount值达到红黑树转化的阈值(默认为8)，则将桶中的结构转化为红黑树存储，最后，增加binCount的值。

同步性能

ConcurrentHashMap的性能相比HashMap的线程安全同步集合和Hashtable而言，性能都要高出不少。原因是经过Collections封装的线程安全的HashMap和Hashtable都是对整个结构加锁，而ConcurrentHashMap是对每一个桶单独进行锁操作，不同的桶之间的操作不会相互影响，可以并发执行。因此，其速度会快很多。

详细实现原理博客链接：http://www.cnblogs.com/leesf456/p/5453341.html

HashSet实现原理

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。无序存储且不能重复（因为内部主要是由HashMap的key值来存储，key不能重复）

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成， HashSet的源代码如下：

public class HashSet<E>  extends AbstractSet<E>  
    implements Set<E>, Cloneable, java.io.Serializable  
{  
    // 底层使用HashMap来保存HashSet中所有元素。  
    private transient HashMap<E,Object> map;  

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

    /** 
     * 默认的无参构造器，构造一个空的HashSet。 
     * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
     */  
    public HashSet() {  
    map = new HashMap<E,Object>();  
    }  
    .........

    /** 
     * 返回此set中的元素的数量（set的容量）。 
     * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
     * @return 此set中的元素的数量（set的容量）。 
     */  
    public int size() {  
        return map.size();  
    }  

    /** 
     * 如果此set包含指定元素，则返回true。 
     * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) 
     * 的e元素时，返回true。 
     * 底层实际调用HashMap的containsKey判断是否包含指定key。 
     * @param o 在此set中的存在已得到测试的元素。 
     * @return 如果此set包含指定元素，则返回true。 
     */  
    public boolean contains(Object o) {  
    return map.containsKey(o);  
    }  

    public boolean add(E e) {  
    return map.put(e, PRESENT)==null;  
    }  

    public boolean remove(Object o) {  
    return map.remove(o)==PRESENT;  
    }  

    ........

详细实现原理博客链接：http://zhangshixi.iteye.com/blog/673143

LinkedHashMap实现原理

LinkedHashMap数据结构：

LinkedHashMap会将元素串起来，形成一个双链表结构。可以看到，其结构在HashMap结构上增加了链表结构。数据结构为（数组 + 单链表 + 红黑树 + 双链表），图中的标号是结点插入的顺序。

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

LinkedHashMap继承了HashMap，所以HashMap的一些方法或者属性也会被继承；同时也实现了Map结构

public class LinkedHashMap<K,V>  extends HashMap<K,V> implements Map<K,V> {
    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);
        }
    }
    // 版本序列号
    private static final long serialVersionUID = 3801124242820219131L;

    // 链表头结点
    transient LinkedHashMap.Entry<K,V> head;

    // 链表尾结点
    transient LinkedHashMap.Entry<K,V> tail;

    // 访问顺序
    final boolean accessOrder;
}

在HashMap.Node基础上增加了前后两个指针域，注意，HashMap.Node中的next域也存在。 LinkedHashMap(int)型构造函数:

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

LinkedHashMap的核心就是存在存储顺序（accessOrder = false）和访问顺序（accessOrder = true），主要是由双向链表来维护顺序，由上面的结果图可看出。

若访问顺序为true，且访问的对象不是尾结点，则下面的图展示了访问前和访问后的状态，假设访问的结点为结点3，从图中可以看到，结点3链接到了尾结点后面，从而实现访问顺序（最近最少使用）：

详细实现原理博客链接：http://www.cnblogs.com/leesf456/p/5248868.html

LinkedHashSet实现原理

HashSet的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序（由于LinkedHashSet底层使用LinkedHashMap来保存所有元素）。

对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承与HashSet，其所有的方法操作上又与HashSet相同

详细实现原理博客链接：http://zhangshixi.iteye.com/blog/673319

TreeMap实现原理

TreeMap 是基于红黑树的实现，是有序的，它根据 key 的自然顺序排序（如果是基本类型，那就是自然顺序，由小到大。如果是对象，那就是比较哈希值,由小到大），或者根据指定的比较器（comparetor）进行排序，具体取决于构造方法。 TreeMap 不是同步的，因为排序调用比较方法，所以不支持 null 键，但是可以 null 值。

与LinkedHashMap区别： 1. TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。 2. LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现. 3. TreeMap 的性能略微低于 HashMap。

详细实现原理博客链接：http://blog.csdn.net/chenssy/article/details/26668941

TreeSet实现原理

与HashSet完全类似，TreeSet里面绝大部分方法都市直接调用TreeMap方法来实现的。

与TreeMap的区别： 相同点： 1. TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是排好序的。 2. TreeMap和TreeSet都是非同步集合，因此他们不能在多线程之间共享，不过可以使用方法Collections.synchroinzedMap()和Collections.synchronizedList()来实现同步 3. 运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)，而HashMap/HashSet则为O(1)。

不同点： 1. 最主要的区别就是TreeSet和TreeMap非别实现Set和Map接口 2. TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序） 3. TreeSet中不能有重复对象，而TreeMap中可以存在

详细实现原理博客链接：http://blog.csdn.net/speedme/article/details/22661671

Collection和Collections区别

java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-22，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap