［重磅，建议收藏］JAVA集合框架中的常用集合及其特点、适用场景、实现原理简介

热文导读 | 点击标题阅读

Android史上第一震撼榜单—2017年Android百大框架排行榜，附完整项目

吊炸天！74款APP完整源码！

电子书免费下载！阿里重磅推荐，Android高级进阶必备：《深入理解Android热修复技术原理》

JDK提供了大量优秀的集合实现供开发者使用，合格的程序员必须要能够通过功能场景和性能需求选用最合适的集合，这就要求开发者必须熟悉Java的常用集合类。本文将就Java Collections Framework中常用的集合及其特点、适用场景、实现原理进行介绍，供学习者参考。当然，要真正深入理解Java的集合实现，还是要推荐去阅读JDK的源码。

Java提供的众多集合类由两大接口衍生而来：Collection接口和Map接口

Collection接口

Collection接口定义了一个包含一批对象的集合。接口的主要方法包括：

• size() - 集合内的对象数量

• add(E)/addAll(Collection) - 向集合内添加单个/批量对象

• remove(Object)/removeAll(Collection) - 从集合内删除单个/批量对象

• contains(Object)/containsAll(Collection) - 判断集合中是否存在某个/某些对象

• toArray() - 返回包含集合内所有对象的数组

Map接口

Map接口在Collection的基础上，为其中的每个对象指定了一个key，并使用Entry保存每个key-value对，以实现通过key快速定位到对象(value)。Map接口的主要方法包括：

• size() - 集合内的对象数量

• put(K,V)/putAll(Map) - 向Map内添加单个/批量对象

• get(K) - 返回Key对应的对象

• remove(K) - 删除Key对应的对象

• keySet() - 返回包含Map中所有key的Set

• values() - 返回包含Map中所有value的Collection

• entrySet() - 返回包含Map中所有key-value对的EntrySet

• containsKey(K)/containsValue(V) - 判断Map中是否存在指定key/value
  

在了解了Collection和Map两大接口之后，我们再来看一下这两个接口衍生出来的常用集合类：

List类集合

List接口继承自Collection，用于定义以列表形式存储的集合，List接口为集合中的每个对象分配了一个索引(index)，标记该对象在List中的位置，并可以通过index定位到指定位置的对象。

List在Collection基础上增加的主要方法包括：

• get(int) - 返回指定index位置上的对象

• add(E)/add(int, E) - 在List末尾/指定index位置上插入一个对象

• set(int, E) - 替换置于List指定index位置上的对象

• indexOf(Object) - 返回指定对象在List中的index位置

• subList(int,int) - 返回指定起始index到终止index的子List对象

List接口的常用实现类：

ArrayList

ArrayList基于数组来实现集合的功能，其内部维护了一个可变长的对象数组，集合内所有对象存储于这个数组中，并实现该数组长度的动态伸缩

ArrayList使用数组拷贝来实现指定位置的插入和删除：

插入：

删除：

LinkedList

LinkedList基于链表来实现集合的功能，其实现了静态类Node，集合中的每个对象都由一个Node保存，每个Node都拥有到自己的前一个和后一个Node的引用

LinkedList追加元素的过程示例：

ArrayList vs LinkedList

ArrayList的随机访问更高，基于数组实现的ArrayList可直接定位到目标对象，而LinkedList需要从头Node或尾Node开始向后/向前遍历若干次才能定位到目标对象
LinkedList在头/尾节点执行插入/删除操作的效率比ArrayList要高
由于ArrayList每次扩容的容量是当前的1.5倍，所以LinkedList所占的内存空间要更小一些
二者的遍历效率接近，但需要注意，遍历LinkedList时应用iterator方式，不要用get(int)方式，否则效率会很低

Vector

Vector和ArrayList很像，都是基于数组实现的集合，它和ArrayList的主要区别在于

• Vector是线程安全的，而ArrayList不是

• 由于Vector中的方法基本都是synchronized的，其性能低于ArrayList

• Vector可以定义数组长度扩容的因子，ArrayList不能

CopyOnWriteArrayList

• 与 Vector一样，CopyOnWriteArrayList也可以认为是ArrayList的线程安全版，不同之处在于 CopyOnWriteArrayList在写操作时会先复制出一个副本，在新副本上执行写操作，然后再修改引用。这种机制让 CopyOnWriteArrayList可以对读操作不加锁，这就使CopyOnWriteArrayList的读效率远高于Vector。 CopyOnWriteArrayList的理念比较类似读写分离，适合读多写少的多线程场景。但要注意，CopyOnWriteArrayList只能保证数据的最终一致性，并不能保证数据的实时一致性，如果一个写操作正在进行中且并未完成，此时的读操作无法保证能读到这个写操作的结果。

Vector vs CopyOnWriteArrayList

• 二者均是线程安全的、基于数组实现的List

• Vector是【绝对】线程安全的，CopyOnWriteArrayList只能保证读线程会读到【已完成】的写结果，但无法像Vector一样实现读操作的【等待写操作完成后再读最新值】的能力

• CopyOnWriteArrayList读性能远高于Vector，并发线程越多优势越明显

• CopyOnWriteArrayList占用更多的内存空间

Map类集合

Map将key和value封装至一个叫做Entry的对象中，Map中存储的元素实际是Entry。只有在keySet()和values()方法被调用时，Map才会将keySet和values对象实例化。

每一个Map根据其自身特点，都有不同的Entry实现，以对应Map的内部类形式出现。

前文已经对Map接口的基本特点进行过描述，我们直接来看一下Map接口的常用实现类

HashMap

HashMap将Entry对象存储在一个数组中，并通过哈希表来实现对Entry的快速访问：

由每个Entry中的key的哈希值决定该Entry在数组中的位置。以这种特性能够实现通过key快速查找到Entry，从而获得该key对应的value。在不发生哈希冲突的前提下，查找的时间复杂度是O(1)。

如果两个不同的key计算出的index是一样的，就会发生两个不同的key都对应到数组中同一个位置的情况，也就是所谓的哈希冲突。HashMap处理哈 希冲突的方法是拉链法，也就是说数组中每个位置保存的实际是一个Entry链表，链表中每个Entry都拥有指向链表中后一个Entry的引用。在发生哈希冲突时，将冲突的Entry追加至链表的头部。当HashMap在寻址时发现某个key对应的数组index上有多个Entry，便会遍历该位置上的 Entry链表，直到找到目标的Entry。

HashMap的Entry类：

static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        int hash;
}

HashMap由于其快速寻址的特点，可以说是最经常被使用的Map实现类

Hashtable

Hashtable 可以说是HashMap的前身（Hashtable自JDK1.0就存在，而HashMap乃至整个Map接口都是JDK1.2引入的新特性），其实现思 路与HashMap几乎完全一样，都是通过数组存储Entry，以key的哈希值计算Entry在数组中的index，用拉链法解决哈希冲突。二者最大的不同在于，Hashtable是线程安全的，其提供的方法几乎都是同步的。

ConcurrentHashMap

ConcurrentHashMap是HashMap的线程安全版（自JDK1.5引入），提供比Hashtable更高效的并发性能。