集合类实现原理总结

发表于 | 分类于 | 阅读次数:
字数统计: 2.4k | 阅读时长 ≈ 9

集合类实现原理总结

整体认识

这里贴出一张网上某大神制作的关于集合类的整体结构关系

此图转载自 https://blog.csdn.net/u010887744/article/details/50575735

List

ArrayList——非线程安全

内部结构

ArrayList的内部结构其实就是一个数组。

由于是数组结构，故访问时间复杂度为O(1)，插入删除的时间复杂度为O(n)。

扩容机制

ArrayList的默认大小是10个元素，当容量不够时，则需要扩容，而扩容的大小是原来的1.5倍(JDK1.8)，其实现代码如下：

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

其决定新数组大小的则是int newCapacity = oldCapacity + (oldCapacity >> 1);

可以看出采用的是位运算得出原来的一半，再加上原来的大小，则得出了1.5倍。
而扩容的行为则是通过Arrays.copyOf(elementData, newCapacity);将原来的数组内容复制到新的数组中。

补充

关于网上部分文章提到的扩容为原来的1.5倍+1，其实是JDK1.6中的实现。扩容值算法如下：

int var4 = var2 * 3 / 2 + 1;

而自从JDK1.7开始则是采用位运算实现，故没有了后面的+1.

LinkedList——非线程安全

内部结构

采用双向链表实现，故插入的时间复杂度是O(1)，而查询的时间复杂度是O(n)

由于还实现了Deque接口，故还可以用作双端队列

由于是链表结构，故只要是遍历链表就需要使用ListIterator

采用了索引优化，可以根据index选择从first或者last开始遍历。

Vector——线程安全

内部结构

与ArrayList相同，采用数组的形式实现

初始大小10，最大容量Integer.MAX_VALUE - 8。

扩容机制

扩容为原来的两倍

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

线程安全的实现

所有可能发生竞争的方法都采用synchronized关键字实现，故效率极低，现在已经不再使用。

若要使用线程安全的List则应该使用CopyOnWriteArrayList。

CopyOnWriteArrayList——线程安全

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

写锁的实现

只在写的时候对数组加锁，采用的是ReentrantLock，加锁之后再复制原来的数组到新数组中，并添加新的元素。

在这个加锁的期间，由于其他线程仍然可以进行读操作，但读的数组是加锁前的旧数组，因此可能会读到原来的旧数据。

适用场景

适合用在读多写少的场景，即可以并发的读而不需要额外的同步操作，只有少量的写操作需要依靠锁来保证线程安全。

Map

HashMap——非线程安全

内部结构

HashMap中主干是一个Node数组，每个Node包含一个key-value的键值对。

transient Node<k,v>[] table;//存储（位桶）的数组</k,v>

Node是HashMap的一个静态内部类。

//Node是单向链表，它实现了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> {
    final int hash;
    final K key;
    V value;
    Node<k,v> next;
    //构造函数Hash值 键 值 下一个节点
    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; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
    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;
}

冲突解决

在HashMap中是以数组（也称为位桶）+ 链表 + (红黑树)的形式存在，当hash值冲突时，则以链表的形式解决hash冲突。

新特性

在JDK1.8中则更是增加了红黑树的结构，当链表的长度超过阈值8时，则会将这部分hash冲突的链表转为红黑树，这样的目的在于，当HashMap中的hash冲突过多而导致链表过长时，仍能较快速的查找到对应的value值，即从以前的 O(n)变为了O(log(n))。

补充

当链表长度超过8时，还要判断当前的map集合中是否总数量达到了64个，如果没有达到的话，不是进行红黑树的转换，而是直接进行扩容。

扩容机制

构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16）

当链表数组的容量超过初始容量的0.75倍（负载因子）时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。

为什么要扩容？为什么需要使用负载因子

因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，因为链表的长度很大（JDK1.8使用了红黑树后会改进很多），扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率。

LinkedHashMap——非线程安全

LinkedHashMap继承自HashMap，大部分属性都类似，但HashMap不保证存储顺序，而LinkedHashMap会维护元素的顺序，顺序可分为访问顺序和插入顺序，默认是保证插入顺序（即迭代遍历的顺序是元素插入的顺序）

// 第三个参数用于指定accessOrder值
Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);

通过以上构造函数，可以指定accessOrder的值为true从而使其保证访问顺序，访问顺序是指，当每次调用get()方法后，对应的key-value键值对则被放在了链表的尾部。

内部结构

LinkedHashMap是由一个双向链表组成。

LinkedHashMap使用的是LRU算法(最近最少使用) 。当你插入元素时它会将节点插入双向链表的链尾，如果key重复，则也会将节点移动至链尾，当用get()方法获取value时也会将节点移动至链尾。

TreeMap——非线程安全

内部结构

基于红黑树实现

排序方式

其映射根据键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。其基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

当自定义比较器时，需要自定义类实现java.lang.Comparable接口，并重写compareTo()方法。

相比较于LinkedHashMap的保证插入顺序，TreeMap是在元素的内容上有序（相当于内容排序）

HashTable——线程安全

现在已经不再使用，其线程安全的实现方式是所有的方法都是synchronized方法，故虽然保证了线程安全，但效率很低。若需要使用线程安全的Map则应该使用ConcurrentHashMap。

底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化

初始size为11，扩容：newsize = olesize*2+1

ConcurrentHashMap——线程安全

内部结构

在JDK1.7中采用的是ReentrantLock+Segment+HashEntry的结构

在JDK1.8中则是采用数组+链表+红黑树的结构，其线程安全的保证则是通过synchronized+CAS的形式。

线程安全实现机制

在JDK1.7中采用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

而在JDK1.8中则直接参考了JDK1.8中HashMap的结构，采用数组+链表+红黑树的结构，而线程安全则是通过CAS来实现。而锁的细粒度也从JDK1.7中的segment段降低为了JDK1.8中的每个Node，且由于红黑树的引入，使得在当链表节点过多的情况下能提高查询效率。

Set

由于Set底层都是采用对应的Map实现，所以不再赘述。

需要注意的是在Set中，Map对应的key则是对应的Set的值，而Map对应的value则是采用同一个Object对象

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
-------------本文结束感谢您的阅读-------------