# Java常用集合框架概述 ## 前言 Java 集合框架在我们日常的开发学习中应该是经常用到。那么什么是集合框架呢？ 从字面意思来看，就是集合的框架。 网友给出了以下解释： > 数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构，这些数据结构通常称为Java集合框架。 有人可能会说，数组不也是把数据组织在一起的集合吗？有什么区别？ 实际上数组长度在初始化时指定，只能保存定长的数据，另外它可以保存基本数据类型和对象引用。 但是集合就不一样了，它可以保存数量不确定的数据，同时可以保存具有映射关系的数据（比如Map<K,V>），另外只能保存对象引用，不能保存基本数据类型; 我们常见的集合框架大体分为两种： 1、实现 Collection 接口的 ``` // 实现List接口 List<String> lists = new ArrayList<>(); // 实现Set接口 Set<String> sets = new HashSet<>(); // 实现Quene接口 Queue<String> queues = new LinkedList<>(); ``` 2、实现 Map<K,V> 接口的 ```java Map<String,String> maps = new HashMap<>(); ``` 其中： - Set 代表无序、不可重复的集合； - List 代表有序、重复的集合； - Queue 代表一种队列集合实现； - Map 代表具有映射关系的集合，键值对存在 先来看下我画的集合框架的大体结构（一些不常用的没列出来）：  看不清的，请点击看大图：[大图地址](http://p2oza5z62.bkt.clouddn.com/2018-03-29-Java集合框架.png) 其中可以看到我们经常用到的 ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等集合框架 ## 一、实现了 Collection<E> 接口 先来看下 Collection<E> 这个接口：  可以看到，这个接口继承了 Iterable<E> 这个接口，那么这个接口是干啥的呢？我们进去看一下： 我们在 Api 文档看到了这样一句话:  官方的描述是：通过实现这个接口允许一个对象成为for-each循环语句的目标。并且是从 1.5 引入的 这个地方对应的就是我们使用迭代器（Iterator<E>）进行集合遍历，比如: ``` Set<String> set = new HashSet<>(); set.add("11111"); set.add("22222"); Iterator<String> iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } ``` 另外我们可以看到他有超多的子接口和实现类，其中就包括我们下面要分析的。 再来看下 Collection<E> 的方法：  我们经常使用的 add 、remove、clear 等方法，都是在这个地方定义的，我们使用的实现类都是要直接或间接实现这些接口。 好了，接下来就来看下具体的List、 Map、 Queue 等接口。 ### 1.1、List<E> 接口 看下官方 Api ：  最下面的那段官方说明: 该接口的用户对插入的每个元素的位置有精确的控制。用户可以通过其整数索引(列表中的位置)访问元素，并搜索列表中的元素。 可以看到 List<E> 接口扩展自 Collection<E> 接口，它主要定义了一个**允许重复**的**有序**集合，并且增加了面向位置的操作，允许在指定位置上进行操作。比如：``add(int index,E element )、addAll(int index,Collection c)、get(int index) ``等。 结合上面的思维导图可以看到，List<E> 接口扩展自 Collection<E> 接口，而 Collection<E> 接口继承于 Iterable<E> 接口，那么可以知道，实现了 List<E> 接口的子类也是可以使用迭代器进行遍历的。此外，还增加了一个能够双向遍历线性表迭代器 ListIterator。 List<E> 接口有一个很重要的抽象实现类： AbstractList<E> ，它实现了 List<E> 的大部分方法。 List 承诺可以将元素维护在特定的序列中，List 在 Collection 接口的基础上添加了大量的方法，使得可以在 List 的中间插入和移除元素。 有两种类型的 List ： - ArrayList 数组实现，它的长项在于随机访问元素，但是在 List 的中间插入和移除元素时较慢 - LinkedList 链表实现，它通过代价较低的在 List 中间进行插入和移除操作，提供了优化的顺序访问，LinekedList 在随机访问方面比较慢，但是它的特性集较 ArrayList 大（提供了更多的操作控件） 下面具体看下这两个 List 的实现类。 #### 1.1.1 ArrayList **ArrayList 是一个有序的集合，随机访问元素比较快，但是往 List 中间插入和移除元素较慢。** ArrayList 是一个其容量能够动态增长的动态数组。它继承了 AbstractList ，实现了 List、RandomAccess, Cloneable, java.io.Serializable。 为什么说 ArrayList 实际上是个数组呢？ 我们通过源码来看下: 先看下成员变量： ``` public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; /** * 默认的数组容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 定义的一个空数组， */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 这个也是个空数组，是为了和 EMPTY_ELEMENTDATA 空数组区分，用来知道当第一个元素被添加的时候，数组会增大多少 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 用于保存ArrayList中数据的数组 */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * 数组的大小 */ private int size; /** * 数组最大长度 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; } ``` 再来通过一个我们常用的 add 方法来分析下。 add方法： ```java /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } ``` 来看下 ensureCapacityInternal(size + 1) 方法: ```java private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } ``` 此时 minCapacity 为数组大小加1. 在 ensureCapacityInternal 方法里面又先调用了 calculateCapacity 方法: ```java private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } ``` 可以看到在 calculateCapacity 方法里面会拿 elementData 数组和默认的空数组进行比较： 如果是相等的，也就是说 elementData 是个空数组，那么 calculateCapacity() 返回默认数组大小和此时 minCapacity 之间的最大值，也就是 DEFAULT_CAPACITY 的值 8 ， 如果不相等，说明数组不为空，那么就返回 minCapacity 的值，即当前数组 size + 1; 然后把返回的值给 ensureExplicitCapacity() : ```java private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } ``` modCount 这个字段我们不需关心，是给迭代器用的。重要看下面: 如果说 minCapacity 减去当前数组的长度大于0，就去执行 grow（）方法： ```java /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ 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); } ``` 我们一行一行来分析: 首先，把当前数组长度赋值给 oldCapacity 接着用 oldCapacity 加上 oldCapacity / 2 计算出来的值为 newCapacity 如果 newCapacity 小于 minCapacity,那么把大的值 minCapacity 赋值给 newCapacity 如果 newCapacity 大于数组的最大长度 MAX_ARRAY_SIZE，去执行：hugeCapacity(minCapacity)： ```java private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } ``` 如果是 minCapacity 大于最大数组长度，那么返回 Integer 的最大值，否则返回 最大数组长度 MAX_ARRAY_SIZE。 继续看 grow 方法的最后一句： ``` elementData = Arrays.copyOf(elementData, newCapacity); ``` 很清晰了，调用 Arrays.copyOf 方法，生成 一个长度为 newCapacity 的新数组，赋值给 elementData。 好了，add方法已经分析完了。 总结下： **ArrayList 是用数组实现的，并且是动态的，默认长度为 8，如果当前长度已用完，那么每次增长的长度为当前长度的一半。** #### 1.1.2 LinkedList LinkedList 也像 ArrayList 一样实现了基本的 List 接口，但是它执行某些操作（在 List 的中间插入和移除）相比 ArrayList 更高效，但是在随机访问逊色于 ArrayList。 **这是因为 LinkedList 的实现机制与 ArrayList 完全不同。** ArrayList 内部是以数组的形式来保存集合中的元素的，因此随机访问集合元素时有较好的性能； LinkedList内部以双向链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色。它也可以被当作**堆栈、队列或双端队列**进行操作。 由于内部是使用链表实现的，那么必然会增加一些有链表特性的方法，比如: - void addFirst(E e):将指定元素插入此列表的开头。 - void addLast(E e): 将指定元素添加到此列表的结尾。 - E getFirst(E e): 返回此列表的第一个元素。 - E getLast(E e): 返回此列表的最后一个元素。 - boolean offerFirst(E e): 在此列表的开头插入指定的元素。 - boolean offerLast(E e): 在此列表末尾插入指定的元素。 - E peekFirst(E e): 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 - E peekLast(E e): 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 - E pollFirst(E e): 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 - E pollLast(E e): 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 - E removeFirst(E e): 移除并返回此列表的第一个元素。 boolean removeFirstOccurrence(Objcet o): 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。 - E removeLast(E e): 移除并返回此列表的最后一个元素。 - boolean removeLastOccurrence(Objcet o): 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。 这里我们就不过多的分析，有兴趣的可以自己去看下 LinkedList 的源码 #### 1.1.3 ArrayList LinkedList 使用场景 - 对于需要快速插入，删除元素，使用LinkedList。 - 对于需要快速随机访问元素，使用ArrayList。 ### 1.2、 Set<E> 接口 Set 不保存重复的元素，所以你可以件容易的得到一个对象是否存在某个 Set 中，正因为如此，查找是 Set 中最重要的操作，因此通常通过实现类 HashSet 来优化查找的速度。 Set 与 List 不同的是，List 继承与 Collection，并且有自己的实现，Set 具有和 Collection 一样的接口，没有特殊的功能，实际上 Set 就是 Collection，只是他们的行为不同（Set 用来存放无序的、不重复的对象的集合，这是典型的多态，Set 用来表现不同的行为）。 > 存入 Set 的每个元素都必须是唯一的，因为 Set 不保存重复元素，加入 Set 的元素必须定义 equals 方法以确保对象的唯一性（正常情况下最好同时重写 hashCode方法）。Set 和 Collection 有完全一样的接口，Set 接口不保证维护元素的次序。 Set 接口主要有三个实现类： - HashSet 散列集，查找速度快 - LinkedHashSet 链式散列集，查找速度快，遍历时会按照插入的顺序显示，底层为 链表维护 - TreeSet 树形集，有序的 Set，底层为树结构 #### 1.2.1 HashSet HashSet 是专门为快速查找而设计的 Set，存入 HashSet 的元素必须重新定义 hashCode（）。 #### 1.2.2 LinkedHashSet 具有HashSet的查询速度，且内部使用链表维护元素的顺序（插入的次序）。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。也必须重新定义 hashCode（）。 #### 1.2.3 TreeSet 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。 ### 1.3、 Queue Queue 是一个后进先出的容器，即从容器的一端放入事物，从另一端取出，并且事物放入容器的顺序与取出的顺序是相同的，队列通常被当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径。队列在并发编程中特别重要，因为他们可以安全第一将对象从一个任务传输给另一个任务。 从 思维导图中可以看出，LinkedList 不仅继承自 AbstractList。并且还实现了 Queue 接口。因此 LinkedList 可以作为 Queue 的一种实现。 如果你将 LinkedList 向上转型为 Queue，那么转换后的 对象会不能使用 LinkedList 的部分功能（继承于 AbstractList 的功能）。 ## 二、实现了 Map<K,V> 接口 Map 是一种将对象与对象相关联的设计。 Map 提供 key 到 value 的映射，你可以通过“键”查找“值”。一个 Map 中不能包含相同的 key ，每个 key 只能映射一个 value 所以 key 不可以相同，但是 value 是可以相同的。 常见以下几种不同的 Map ： - HashMap, - TreeMap, - LinkedHashMap 它们都有同样的基本接口 Map ，但是行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。 我们注意到在讲实现 Collection 接口的集合的时候，通过继承于 Iterable<E> 接口，我们让实现了 Collection 的集合框架具有了使用迭代器的能力，但是这里的 Map<E> 接口好像没有继承与 Iterable<E> 接口，那么，我们是否可以也让 Map 接口具有使用迭代器的能力呢？ 答案是肯定的，只是要通过 Map 里面的一个内部接口来实现。 Map 接口有一个重要的泛型内部接口 Entry<K,V>，它表示 Map 中的一个实体（一个 key-value 对）。接口中有 getKey(),getValue 方法。 - 我们可以通过 Map<K,V> 的 keySet() 方法获取 Map 中的 K（key） 值集合（Set<V> 类型）， - 通过 values() 方法 获得 Map 中的 V（value） 类型的集合 Collection<V> - 通过 entrySet() 方法获取 Map 的 Entry 集合 Set<Map.Entry<K, V>>。 即： ```java Map<Integer,String> map = new HashSet<>(); // 获取 key 集合 Set<Integer> keys = map.keySet(); // 获取 value 集合 Collection<String> values = map.values(); // 获取 Entry 集合 Set<Map.Entry<Integer,String>> entrys = map.entrySet(); ``` 细心的你可能已经发现了：存储 key 的集合和 存储 Entry 的集合使用的都是 Set 接口，而存储 value 的集合使用的是 Collection 接口。 原因前面已经说了：在 Map 中，不允许存在重复元素，key 是唯一的，Entry 也是唯一的，不存在重复值，正好 Set 是不允许重复值的，所以 key 和 Entry 都是使用的 Set 接口；然后在 Map 中 value 是可以重复的（只要 key 不重复），那么自然就可以使用 Collection 接口了。 也就是说，要遍历 Map，就要借助这个很重要的内部接口 Map.Entry<K,V> ### 2.1、 HashMap HashMap 基于散列表实现（它取代了Hashtable），它存储的内容是键值对 (key-value) 映射，插入和查询键值对的开销是固定的，可以通过构造器设置容量和敷在因子，已调整容器的性能。 该类实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null ，不支持线程同步。 ### 2.2、 LinkedHashMap 类似于 HashMap，但是迭代遍历它时，取得键值对的顺序是其 **插入顺序**，或者是最近最少使用的次序，只比 HashMap 慢一点，而在迭代访问时反而更快，因为是通过链表维护内部次序。 ### 2.3、 TreeMap 基于红黑树实现，查看 键 或者 键值对 时，他们会被排序，（排序规则由 Comparable 或 Comparator 决定），TreeMap 的特点是，得到的结果是经过排序的，TreeMap 是唯一带有 subMap() 方法的 Map，可返回一个子树。