java集合概述（上）

前言

先说说，为什么要写这么一篇博客（我总是喜欢写原因）。因为最近到年底了，正好又要准备面试，所以在做各方面的技术总结。而java集合是java非常重要的一部分，自己前前后后也花了不少时间学习，但是一直比较零散。所以，打算趁着这个机会，来写一个总结。

由于能力有限，这方面没有足够积累，如果有什么问题，还请指出。谢谢。

集合分类，主要分为：

• collection（继承iterable接口）：按照单个元素存储的集合
  • list：一种线性数据结构的主要体现。有序，可重复
  • set：一种不允许出现重复元素的集合。无序（插入顺序与输出顺序不一致），不可重复
  • queue：一种先进先出（fifo）的数据结构。有序，可重复，先进先出
• map（无继承接口）：按照k-v存储的map
  • keyset：可以查看所有的key。底层实现各不相同。concurrenthashmap则是采用的自定义实现的keysetview内部静态类（实现了set接口），而hashmap这样的abstractmap子类，则是是set接口
  • values：同上，concurrenthashmap采用valuesetview，hashmap采用set接口
  • entryset：同上，concurrenthashmap采用entrysetview，hashmap采用set接口

原本map是打算按照 abstractmap；sortedmap；concurrentmap；来分类，但是发现这个分类属于理论价值，大于使用价值，也可能是我现在层次不够吧。最后还是学着孤尽大佬在《码处高效》中那样，通过三个视图，来观察map。具体后面阐述，我也只是阐述其中部分的map。

论述方面，我主要会从数据组织方式（底层数据存储方式），数据处理方式（如hashmap的put操作等），特点小结结三个方面进行阐述。但是由于内容量的问题，这里并不会非常细致地阐述代码实现。

最后，由于内容量的缘故，这部分内容，我将分为两个部分。这篇博客主要论述list与map，而set与queue放在另外一篇博客。

一，list

arraylist

数据组织方式

    transient object[] elementdata; // non-private to simplify nested class access

arraylist的底层是一个object类型的数组。那么arraylist就有着和数组一样的特点：随机查询快，但数据的插入，删除慢（因为很可能需要移动其他元素）。

数据处理方式

add

    public void add(int index, e element) {
        // 校验index是否在0-size范围内，如果不是，抛出异常indexoutofboundsexception
        rangecheckforadd(index);

        // 这个操作后面有多个操作，总结一下，就是校验，判断是否需要扩容，扩容。
        ensurecapacityinternal(size + 1);  // increments modcount!!
        // 通过system.arraycopy操作，为新添加的元素element，在elementdata数组的对应index位置，腾出空间
        system.arraycopy(elementdata, index, elementdata, index + 1,
                         size - index);
        // 紧跟着上面的操作elementdata数组的index位置，赋值为element
        elementdata[index] = element;
        // 数组元素数量+1
        size++;
    }

grow

    // 简单来说， 就是根据所给的mincapacity，计算对应容量（2的幂次方），然后校验容量，最后扩容
    private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length;
        int newcapacity = oldcapacity + (oldcapacity >> 1);
        if (newcapacity - mincapacity < 0)
            newcapacity = mincapacity;
        if (newcapacity - max_array_size > 0)
            newcapacity = hugecapacity(mincapacity);
        // mincapacity is usually close to size, so this is a win:
        elementdata = arrays.copyof(elementdata, newcapacity);
    }

小结

根据其数据组织方式，与数据处理方式，可以明确：

• arraylist随机查询快（直接通过index定位数据中具体元素）
• arraylist插入与删除操作慢（涉及数组元素移动操作system.arraycopy，还可能涉及扩容操作）
• arraylist是容量可变的（自带扩容操作，初始化，默认为default_capacity=10）
• arraylist是非线程安全的（没有线程安全措施）

补充：

• arraylist的默认容量为10（即无参构造时）
• 出于性能考虑，避免多次扩容，最好在初始化时设置对应size（即使后面不够了，它也可以自动扩容）

linkedlist

数据组织方式

    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;
        }
    }

linkedlist的底层是自定义的node双向链表。那么linkedlist就有着和链表一样的特点：数据的插入与删除快，但是随机访问慢。

数据处理方式

add

    public void add(int index, e element) {
        // 数据校验，index是否超出0-size范围
        checkpositionindex(index);

        if (index == size)
            // 如果插入的元素是放在最后一个，那就执行尾插入操作（因为linkedlist是有保存first与last两个node的，所以可以直接操作）
            linklast(element);
        else
            // 首先通过node(index)方法，获取到当前index位置的node元素（内部实现，依旧是遍历。不过会根据index与列表中值的比较结果，判断是从first开始遍历，还是从last开始遍历），再通过linkbefore方法，进行插入操作
            linkbefore(element, node(index));
    }

peek

    
    // linkedlist实现了deque接口，所以需要实现其中的peek方法。获取当前数组的第一个元素，但不进行删除操作
    public e peek() {
        final node<e> f = first;
        return (f == null) ? null : f.item;
    }

小结

根据其数据组织方式，与数据处理方式，可以明确：

• linkedlist随机查询慢（需要进行遍历查询，虽然通过列表中值，降低了一半的遍历范围，但其数据组织方式决定了它的速度慢）：

  测试表明，10w条数据，linkedlist的随即提取速度与arraylist相比，存在数百倍的差距（引自《码出高效》）

• linkedlist插入与删除操作快（依旧需要靠遍历来定位目标元素，但只需要修改链表节点的前后节点引用）
• linkedlist是容量可变的（链表可以随意链接）

• linkedlist是非线程安全的（没有线程安全措施）

补充：

• 通过链表，可以有效地将零散的内存单元通过引用的方式串联起来，形成按链路顺序查找的线性结构，内存利用率较高（引用自《码出高效》）

vector

vector本质与arraylist没太大区别，底层同样是object数组，默认大小依旧为10（不过vector采用的是不推荐的魔法数字）。

唯一的区别，就是vector在关键方法上添加了sychronized关键字，来确保线程安全。

但是，由于处理得较为粗糙，以及其特点，所以性能很差，基本已经被抛弃。

这里就不再赘述了。

copyonwritearraylist

copyonwritearraylist，作为cow容器的一员，其思想就是空间换时间，主要针对读多写少的场景。当有元素写入时，会新建一个数组，将原有数组的元素复制过来，然后进行写操作（此时数组的读操作，还是针对原数组）。在写操作完成后，会将读操作针对的数组引用，从原数组指向新数组。这样就可以在写操作进行时，不影响读操作的进行。

数据组织方式

    /** the array, accessed only via getarray/setarray. */
    // 一方面通过transient避免序列化，另一方面通过volatile确保可见性，从而确保单个属性（这里是引用变量）的线程安全
    private transient volatile object[] array;

数据处理方式

add

    public void add(int index, e element) {
        final reentrantlock lock = this.lock;
        // 进行加锁，同时只能有一个写操作
        // 另外，加锁操作放在try块外，一方面是try规范（lock操作并不会发生异常，并且可以减少try块大小），另一方面是避免加锁失败，finally的释放锁出现illegalmonitorstateexception异常
        lock.lock();
        try {
            // 获取原有数组，并赋值给elements（引用变量）
            object[] elements = getarray();
            int len = elements.length;
            // 数据校验
            if (index > len || index < 0)
                throw new indexoutofboundsexception("index: "+index+
                                                    ", size: "+len);
            // 下面的操作，就是对原有数组进行复制，并赋值给newelements（并且留出index位置）
            object[] newelements;
            int nummoved = len - index;
            if (nummoved == 0)
                newelements = arrays.copyof(elements, len + 1);
            else {
                newelements = new object[len + 1];
                system.arraycopy(elements, 0, newelements, 0, index);
                system.arraycopy(elements, index, newelements, index + 1,
                                 nummoved);
            }
            // 设置新数组index位置的值为element，完成赋值操作
            newelements[index] = element;
            // 将数组引用（读操作正在读的数组引用）改为newelements
            setarray(newelements);
        } finally {
            // 无论是否异常，都需要释放锁，
            lock.unlock();
        }
    }

最大的特色，就是这部分了。至于remove操作，都是类似的。故不再赘述。

小结

由于copyonwritearraylist的数据组织方式与arraylist一致，也是采用的数组，故：

• copyonwritearraylist随机查询快
• copyonwritearraylist插入与读写慢
• copyonwritearraylist是容量可变的（每次进行增删的写操作，都会新建一个数组，进而进行替换）

补充：

• copyonwritearraylist是线程安全的（读写操作隔离，写操作通过reentrantlock确保线程安全）
• copyonwritearraylist的写操作不直接影响读操作（两者在内存上针对的不是同一个数组）
• copyonwritearraylist只适用于读多写少场景（毕竟写操作是需要复制数组）
• copyonwritearraylist占据双倍内存（因为写操作的时候需要复制数组）
• copyonwritearraylist的性能会随着写入频次与数组大小上升，而快速下降（写入频次m x 数组大小n）

推荐：高并发请求下，可以攒一下要进行的写操作（如添加，或删除，可以分开保存），然后进行addall或removeall操作。这样可以有效减低资源消耗。但是这个攒的度需要好好把握，就和请求合并一样，需要好好权衡。

二，map

treemap

数据组织方式

数据处理方式

小结

hashmap

hashmap一方面是工作中用的非常多的集合，另一方面是面试的高频（我每次面试几乎都会被人问这个）。

而hashmap，与concurrenthashmap一样，都存在jdk8之前与jdk8之后的区别。不过，我应该会以jdk8之后为重点，毕竟现在springboot2.x都要求jdk8了。

数据组织方式

jdk8之前

    // jdk8之前，其底层是数组+链表
    // 链表底层entry是map的内部接口
    transient entry<k, v>[] table;

jdk8之后

    transient node<k, v>[] table;


    static class node<k, v> implements map.entry<k, v> {
        final int hash;
        final k key;
        v value;
        node<k, v> next;
    }

数据处理方式

jdk8之前的put方法（注释并不多，因为我没有源码，我是按照笔记图片，手撸的这段）

    public v put (k key, v value) {
        // hashmap采用延迟创建。判断当前table是否为空。如果为空，就根据默认值15，创建一个数组，并赋值给table
        if (table == empty_table) {
            inflatetable(threshold);
        }
        // 数据校验
        if ( key == null) 
            return putfornullkey(value);
        // 根据key，计算哈希值
        int hash = hash(key);
        // 通过indexfor（内部貌似采用位运算），根据key的哈希值与数组长度，计算该k-v键值对在数组中的下标i
        int i = indexfor(hash, table.length);
        for (entry<k, v> e = table[i]; e != null; e = e.next) {
            object k;
            if (e.hash = hash && ((k = e.key) || key.equals(k))) {
                v oldvalue = e.value;
                e.value = value;
                e.recordaccess(this);
                return oldvalue;
            }
        }

            // 记录修改次数+1，类似版本号
        modcount++;
        addentry(hash, key, value, i);
        return null;
    }

jdk8之后的put方法

    public v put(k key, v value) {
        return putval(hash(key), key, value, false, true);
    }


    // 计算key的哈希值（数据校验，key的哈希值，即其hashcode）
    static final int hash(object key) {
        int h;
        // 通过其hashcode的高16位与其低16位的异或运算，既降低系统性能开销，又避免高位不参加下标运算造成的碰撞
        return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
    }


    // 执行主要put操作
    final v putval(int hash, k key, v value, boolean onlyifabsent,
                   boolean evict) {
        node<k,v>[] tab; node<k,v> p; int n, i;
        // 从下面这个代码块，可以看出java8后的hashmap等，代码晦涩不少
        if ((tab = table) == null || (n = tab.length) == 0)
            // 如果table为null，或table.length为0（其中混杂了赋值语句），就进行进行初始化操作（通过resize()操作，这点与spring的refresh()应用是一致的），并将其长度赋值给n（注意这里，都赋值给了局部变量，而非全局变量）
            n = (tab = resize()).length;
        // 根据key的hash值，计算其下标，并判断数组中对应下标位置是否为null
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果对应位置为null，直接通过newnode方法（生成node），设置数组对应i位置为对应新node
            tab[i] = newnode(hash, key, value, null);
        else {
            // 如果对应位置不为null，那就需要进行链表操作，进而判断是否树化（红黑树），是否扩容等
            node<k,v> e; k k;
            // 通过hash与equals等，判断新添加值的key与已存在值的key是否真正相等
            // 这里扩展两点：第一，判断对象是否相等，必须hashcode与equals都判断相等。前者避免两个对象只是值，但不是同一个对象（两位都是p9大佬，不代表两位就是同一个人）。后者避免哈希碰撞问题（即使是两个不同的对象的内存地址，也可能哈希值相等）
            // 第二，我看到这里的时候，比较担心，会不会出现value相等，但是hashcode不同，导致这里判断为false。然后我发现包装类型，早就重写了hashcode方法，如integer的hashcode就直接返回value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 如果相等，就直接更新对应node即可
                e = p;
            // 如果上面判断失败，则判断原有的数组元素，是不是已经树化（不再是node类型，而是treenode，当然treenode依旧是由node构成的）
            else if (p instanceof treenode)
                // 如果原有数组元素已经树化，那么就进行调用puttreeval方法，将当前元素，置入目标红黑树中（其中涉及红黑树的旋转等操作）
                e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);
            // 如果不是空，也不是相同元素，更不是红黑树，那说明那已经是一个链表（已经由多个元素），或即将成为链表（已经有一个元素，并即将添加一个新的元素）
            else {
                // 遍历对应链表元素，并通过bincount记录链表已存在的元素数
                for (int bincount = 0; ; ++bincount) {
                    // 如果e=p.next()为null，说明达到了链表的最后（e的前一个值为当前链表的最后一个元素）
                    if ((e = p.next) == null) {
                        // 通过newnode获得对应p的node，并将其设置为链表的最后一个元素
                        p.next = newnode(hash, key, value, null);
                        // 通过bincount，判断链表的长度是否达到了树化的阈值
                        if (bincount >= treeify_threshold - 1) // -1 for 1st
                            // 达到阈值，则通过当前table数组与hash值，以及treefybin方法，将当前数组位置的链表树化
                            treeifybin(tab, hash);
                        break;
                    }
                    // 在遍历过程中，找到了相同的元素，即跳过（因为内容相同）
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 该赋值操作，属于链表的操作，从而继续链表遍历
                    p = e;
                }
            }
            // 下面这段代码，就涉及到hashmap的putifabsent（也是调用putval，只是第四个参数onlyifabsent不同）
            // 简单来说，就是遇到key相同的元素，怎么处理。put操作是直接赋值，而putifabsent则是判断对应key的value是否为null，如果是null，才会赋值。否则就不变（类似redis）
            // 只不过，这个过程通过新增的第四个参数控制，从而确保同一套代码（putval方法），实现两种不同功能（put与putifabsent）
            if (e != null) { // existing mapping for key
                v oldvalue = e.value;
                if (!onlyifabsent || oldvalue == null)
                    e.value = value;
                afternodeaccess(e);
                return oldvalue;
            }
        }
        // 版本号
        ++modcount;
        // 一方面size前缀自增，另一方面，判断自增后的size是否超过阈值（默认16*0.75=12，数组容量*负载因子）
        if (++size > threshold)
            // 扩容（扩容2倍后，重排）
            resize();
        // 空方法，为子类保留的，如linkedhashmap
        afternodeinsertion(evict);
        return null;
    }

这个方法可以算是hashmap的核心，毕竟通过这个方法，也算是摸到了hashmap的运行机制了。

流程简述：

1. 如果hashmap的底层数组没有初始化，则通过resize()方法进行构建
2. 对key计算hash值，然后再计算下标
3. 如果数组对应下标位置为null（这里我认为不该用哈希碰撞），则直接放入对应位置
4. 如果数组对应下标位置为treenode（即对应位置已经树化），则通过puttreeval方法，将对应node置入树中
5. 否则遍历数组对应下标位置的链表，将对应node置入
6. 如果链表的长度超过阈值，则进行树化操作
7. 如果节点存在旧值，直接替换
8. 如果数组的元素数量超过阈值（数组容量*负载因子），则进行扩容（扩容2倍，重排）

jdk8之后的get方法

    public v get(object key) {
        node<k,v> e;
        return (e = getnode(hash(key), key)) == null ? null : e.value;
    }


    // 这里我觉得没什么说的。根据不同情况，分别从数组，红黑树，数组来获取目标元素
    final node<k,v> getnode(int hash, object key) {
        node<k,v>[] tab; node<k,v> first, e; int n; k k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof treenode)
                    return ((treenode<k,v>)first).gettreenode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

小结

就使用场景而言，《码出高效》给出这样一句话：

除局部方法或绝对线程安全的情形外，优先推荐concurrenthashmap。两者虽然性能相差无几，但后者解决了高并发下的线程安全问题。hashmap的死链问题及扩容数据丢失问题是慎用hashmap的两个主要原因。

这里，我忍不住站在java工程师的角度，推荐《码出高效》以及配套的《阿里java开发手册》。作为一名也算看过不少技术书籍的开发者，这两本书在我这儿，也算得上是优秀书籍了。

不过，文中也提到，这种情形，在jdk8之后有所修复，改善。具体的，可以看看书籍（主要内容有点多）。

concurrenthashmap

concurrenthashmap部分，我将只描述jdk8之后的版本。

而jdk8之前的版本，其实底层就是类似hashtable的segament组成的数组。通过分段锁，达成线程安全。算是hashtable与hashmap的折中方案。复杂度并不是很高，不过jdk8之后的版本，就较为复杂。首先，引入红黑树，优化存储结构。其次，取消原有的分段锁设计，采用了更高效的线程安全设计方案（利用了无锁操作cas与头节点同步锁等）。最后，使用了更优化的方式统计集合内的元素数量（引用自《码出高效》，我还真没注意到这点）。

数据组织方式

    transient volatile node<k,v>[] table;


    static class node<k,v> implements map.entry<k,v> {
        final int hash;
        final k key;
        volatile v val;
        volatile node<k,v> next;

        node(int hash, k key, v val, node<k,v> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }

        // 此处省略其内部方法，感兴趣的，可以自行查看
    }

从上述来看，concurrenthashmap的底层数据组织为数组+链表。依据jdk8后的hashmap，可以推测，在对应条件下，链表会转为红黑树结构。事实也是如此，请看下代码。

    static final class treenode<k,v> extends node<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,
                 treenode<k,v> parent) {
            super(hash, key, val, next);
            this.parent = parent;
        }

        // 此处省略其内部方法，感兴趣的，可以自行查看
    }

concurrenthashmap，与hashmap一样，其内部也有专门为红黑树服务的treenode。

所以，从数据组织方面来看，其实concurrenthashmap与同版本的hashmap，可以说就是一个模子刻出来的（毕竟都是doug lea带着撸的）。

两者的区别，或者说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) {
        // 数据校验，如果key或value为null，直接npe
        if (key == null || value == null) throw new nullpointerexception();
        // 通过spread方法，计算hash值（本质还是与hashmap一样，针对hashcode进行高低16位异或计算等）
        int hash = spread(key.hashcode());
        // 记录链表长度
        int bincount = 0;
        // 这里的循环操作是为了之后的cas操作（就是cas的自旋操作）
        for (node<k,v>[] tab = table;;) {
            node<k,v> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                // 同hashmap一样，如果数组为空或长度为0，则进行数组初始化操作（循环头中已经完成赋值操作）
                tab = inittable();
            else if ((f = tabat(tab, i = (n - 1) & hash)) == null) {
                // 如果数组对应位置为null，则通过cas操作，进行值的插入操作
                if (castabat(tab, i, null,
                             new node<k,v>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // 如果对应节点的node.hash值为moved=-1
            else if ((fh = f.hash) == moved)
                // 进行resize协助操作（具体协助方式，还没研究）
                tab = helptransfer(tab, f);
            else {
                v oldval = null;
                synchronized (f) {
                    if (tabat(tab, i) == f) {
                        // 如果数组对应位置（即首节点）的哈希值大于等于零（树化后等情况下，对应位置哈希值小于零）
                        //  static final int moved     = -1; // hash for forwarding nodes
                        //  static final int treebin   = -2; // hash for roots of trees
                        //  static final int reserved  = -3; // hash for transient reservations
                        if (fh >= 0) {
                            // 说明此情况下，数组对应位置，存储的是链表。进行链表插入，遍历操作（具体参照hashmap的put操作）
                            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;
                                }
                            }
                        }
                        // 如果数组对应位置的元素，是树化节点（即为treebin实例）
                        else if (f instanceof treebin) {
                            node<k,v> p;
                            bincount = 2;
                            // 调用puttreeval方法，进行红黑树的值插入操作
                            if ((p = ((treebin<k,v>)f).puttreeval(hash, key,
                                                           value)) != null) {
                                oldval = p.val;
                                // 判断onlylfabsent参数，进行val设置。具体参照hashmap的put方法的对应位置解释
                                if (!onlyifabsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                // 前面的各类操作，都会计算bincount（数组当前位置存储的节点数）
                if (bincount != 0) {
                    // 如果对应节点数超过了树化阈值treeify_threshold=8
                    if (bincount >= treeify_threshold)
                        // 对数组当前位置，进行树化操作
                        treeifybin(tab, i);
                    if (oldval != null)
                        return oldval;
                    break;
                }
            }
        }
            // 计数
        addcount(1l, bincount);
        return null;
    }

小结

concurrenthashmap的魅力在于其线程安全的实现，有机会好好研究研究，专门写一个相关的博客。

三，总结

其实，java集合主要从两个维度分析。一个是底层数据组织方式，如链表与数组（基本就这两种，或者如hashmap那样组合两种）。另一个是线程安全方式，就是线程安全与非线程安全。

最后就是由于一些底层数据组织方式的调整，带来的循环，有序等特性。