Java集合概述（上）

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是非线程安全的（没有线程安全措施）

补充：