List

ArrayList

arrayList 主要的实现方式是通过数组对数据进行处理。有个主要的问题的是扩容这个问题，扩容是通过 System.arraycopy(original, 0, copy, 0,

Math.min(original.length, newLength));

这个方法进行的。问题的主要在remove

如果按下标插入元素、删除元素－add（i,e）、remove（i）、remove（e），则要用System.arraycopy（）来复制移动部分受影响的元素，性能就变差了。

越是前面的元素，修改时要移动的元素越多。直接在数组末尾加入元素－常用的add（e），删除最后一个元素则无影响

public E remove(int index) {
        rangeCheck(index);

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

        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

        return oldValue;
    }

LinkedList

linkList 主要用到的是双向链表。插入删除的时候只需要修改相关的指针即可。效率低的地方在于查找，需要从前往后比对。

CopyOnWriteArrayList

并发优化的ArrayList。基于不可变对象策略，在修改时先复制出一个数组快照来修改，改好了，再让内部指针指向新数组。

因为对快照的修改对读操作来说不可见，所以读读之间不互斥，读写之间也不互斥，只有写写之间要加锁互斥。但复制快照的成本昂贵，典型的适合读多写少的场景。

Queue

队列包含的数据结构比较包含阻塞和非阻塞以及单向队列双向队列，并发队列以及优先级队列。

ArrayQueue

Arrayqueue使用的也是数组默认16 操作跟数组类似

ArrayDeque

以循环数组实现的双向Queue。大小是2的倍数，默认是16。

为了支持FIFO，即从数组尾压入元素（快），从数组头取出元素（超慢），就不能再使用普通ArrayList的实现了，改为使用循环数组。

有队头队尾两个下标：弹出元素时，队头下标递增；加入元素时，队尾下标递增。如果加入元素时已到数组空间的末尾，则将元素赋值到数组[0]，同时队尾下标指向0，再插入下一个元素则赋值到数组[1]，队尾下标指向1。如果队尾的下标追上队头，说明数组所有空间已用完，进行双倍的数组扩容。

PriorityQueue

主要采用的数据结构是堆，最大对还是最小堆主要是看comparator中比较的方法。数值越小，优先级越高，越先出队

LinkedBlockingQueue/PriorityBlockingQueue/ArrayBlockingQueue

blockqueue中采用了两把锁来进行数据的存放，特别需要注意的是take/poll ,put/offer 前者是会产生阻塞的，而后者是会直接返回。

LinkedTransferQueue

ConcurrentLinkedQueue /ConcurrentLinkedDeque

无界的并发优化的Queue，基于链表，实现了依赖于CAS的无锁算法。

ConcurrentLinkedQueue的结构是单向链表和head/tail两个指针，因为入队时需要修改队尾元素的next指针，以及修改tail指向新入队的元素两个CAS动作无法原子，所以需要的特殊的算法。

里边用了CAS的锁保证线程安全。

本文由妖言君创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jan 10, 2021 at 03:03 pm

java 源码集合小结