Java集合类梳理

集合框架

Collection

Collection 接口用于表示任何对象或元素组。它是 List 和 Set 的父接口。

Collection 声明的方法：

点击查看方法摘要

List

List集合代表一个有序、可变长、可重复的集合，集合中每个元素都有其对应的顺序索引。List集合默认按照元素的添加顺序设置元素的索引，可以通过索引（类似数组的下标）来访问指定位置的集合元素。

List相当于下图的格子，按顺序放入值，for循环可以挨个取出：

实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

特点梳理：

• List集合为列表类型，以线性方式，有序存取对象。各元素的顺序就是对象插入时的顺序，即元素按进入先后有序保存。

• List集合有序是指存储的元素有下标，下标从0开始，以1递增。所以可以通过使用索引来访问List集合中的元素，即可以用下标进行元素的操作

• List集合中的元素允许重复，即可以存储重复的元素。

List常用方法

点击查看方法摘要

ArrayList

ArrayList是一个动态数组，也是我们最常用的集合，是List类的典型实现。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

如上图，ArrayList若要找Killer，则要通过for循环，从Tom开始挨个找才能找到，ArrayList的查询速度比LinkedList快，但不及HashMap快。数据若是很庞大，而且又频繁查找的业务，建议使用散列表。

特点梳理：

• 底层数据结构是数组，添加、查找、删除均采用基本数组操作，可以存储重复元素

• 查找效率高，添加、删除效率低，整体效率高

• 初始大小10，最大容量Integer.MAX_VALUE - 8

• 满时扩容，扩容大小为1.5倍，（int newCapacity = oldCapacity + (oldCapacity >> 1）。

• 采用Arrays.copyOf()产生新数组

• 没有同步，线程不安全

ArrayList常用方法

点击查看方法摘要

LinkedList

LinkedList 是List 接口的另一个实现类，除了可以根据索引访问集合元素外，LinkedList 还实现了 Deque 接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用。

LinkedList 的实现机制与 ArrayList 的实现机制完全不同，ArrayList 内部以数组的形式保存集合的元素，所以随机访问集合元素有较好的性能；LinkedList 内部以链表的形式保存集合中的元素，所以随机访问集合中的元素性能较差，但在插入删除元素时有较好的性能。

特点梳理：

• 同时实现了Queue和Deque接口

• 底层采用双向链表实现，头结点不存放数据，允许为null

• 只要是遍历链表就需要使用 ListIterator

• 索引优化，可以根据 index 可以选择从 first 和 last 开始遍历

• 线程不安全

LinkedList常用方法

点击查看方法摘要

Vector

与 ArrayList 相似，但是 Vector 是同步的。所以说 Vector 是线程安全的动态数组。它的操作与 ArrayList 几乎一样。

Vector 类实现了可扩展的对象数组。 像数组一样，它包含可以使用整数索引访问的组件。 但是， Vector 的大小可以根据需要增长或缩小，以适应在创建 Vector 之后添加和删除项目。

特点梳理：

• 底层由数组实现，添加、查找、删除均采用基本数组操作，所以查找效率高，添加、删除效率低

• 初始大小10，最大容量 Integer.MAX_VALUE - 8

• 满时扩容，扩容大小为1.5倍，（int newCapacity = oldCapacity + (oldCapacity >> 1）

• 采用 Arrays.copyOf() 产生新数组

• 线程不安全

Vector 常用方法

点击查看方法摘要

Stack

Stack 继承自 Vector，实现一个后进先出的堆栈。Stack 提供5个额外的方法使得 Vector 得以被当作堆栈使用。基本的 push 和 pop 方法，还有 peek 方法得到栈顶的元素，empty 方法测试堆栈是否为空，search 方法检测一个元素在堆栈中的位置。Stack 刚创建后是空栈。

Stack 常用方法

点击查看方法摘要

Set

继承自 Collection 接口，且方法相同，Set 没有在 Collection 的基础上进行功能的扩展，只是比Collection 接口更加严格了，Set 接口是无序的。

Set集合的实现类可说是基于Map集合去写的。通过内部封装Map集合来实现的比如HashSet内部封装了HashMap。

Set相当于往袋子里放东西，无序取出（使用迭代器取出），如下图：

特点梳理：

• 继承自Collection

• Set集合中的元素无序，即插入无序

• 不可指定位置访问，即没有索引值

HashSet

HashSet是Set集合最常用实现类，是其经典实现。HashSet是按照hash算法来存储元素的，因此具有很好的存取和查找性能。

HashSet使用HashMap的数据结构，仅使用HashMap中的key结构，value值一律为null。也就是说真实数据存储在 HashMap 的 key 列，value 列全部为空。

HashSet 存储原理：

当向 HashSet 集合存储一个元素时，HashSet 会调用该对象的 hashCode() 方法得到其 hashCode 值，然后根据 hashCode 值决定该对象的存储位置，

HashSet 集合判断两个元素相等的标准是：

1. 两个对象通过 equals() 方法比较返回 true
2. 两个对象的hashCode()方法返回值相等。

因此，如果（1）和（2）有一个不满足条件，则认为这两个对象不相等，可以添加成功。如果两个对象的 hashCode() 方法返回值相等，但是两个对象通过 equals() 方法比较返回 false，HashSet会以链式结构将两个对象保存在同一位置，这将导致性能下降，因此在编码时应避免出现这种情况。

HashSet 查找原理：

基于 HashSet 以上的存储原理，在查找元素时，HashSet 先计算元素的 HashCode 值（也就是调用对象的 hashCode 方法的返回值），然后直接到 hashCode 值对应的位置去取出元素即可，这就是 HashSet 速度很快的原因。

重写 hashCode() 方法的基本原则：

1. 在程序运行过程中，同一个对象的hashCode()方法返回值应相同。
2. 当两个对象通过equals()方法比较返回true时，这两个对象的hashCode()方法返回值应该相等。
3. 对象中用作equals()方法比较标准的实例变量，都应该用于计算hashCode值。

特点梳理：

• 不能保证元素的顺序

• HashSet不是线程同步的，如果多线程操作HashSet集合，则应通过代码来保证其同步

• 集合元素值可以是null

HashSet 常用方法

点击查看方法摘要

LinkedHashSet

LinkedHashSet 是 HashSet 的一个子类，具有 HashSet 的特性，也是根据元素的 hashCode 值来决定元素的存储位置。但它使用链表维护元素的次序，元素的顺序与添加顺序一致。由于 LinkedHashSet 需要维护元素的插入顺序，因此性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

LinkedHashSet 是一个非线程安全的集合。如果有多个线程同时访问当前 LinkedHashSet 集合容器，并且有一个线程对当前容器中的元素做了修改，那么必须要在外部实现同步保证数据的冥等性。

特点梳理：

• LinkedHashSet的底层使用LinkedHashMap存储元素

• LinkedHashSet是有序的，它是按照插入的顺序排序的

• LinkedHashSet 是一个非线程安全的集合

LinkedHashSet 常用方法

点击查看方法摘要

TreeSet

TreeSet 是 SortedSet 接口的实现类，TreeSet可以保证元素处于排序状态，它采用红黑树的数据结构来存储集合元素。TreeSet 支持两种排序方法：自然排序和定制排序，默认采用自然排序。

排序：

当向TreeSet中添加自定义对象时，有 2 种排序方法：

1. 自然排序

要求自定义类实现 java.lang.Comparable 接口并重写 compareTo(Object obj) 方法。在此方法中，指明按照自定义类的哪个属性进行排序

2. 定制排序

当元素不具备比较性时，此时只能为容器添加比较器来解决问题，即创建 TreeSet 时向其中加入Comparator

特点梳理：

• 有序

• 不可重复

• 红黑树

• 基于Treemap实现

• 自定义排序等特点

• 非线程安全

• TreeSet中存储的类型必须是一致的，不能一下存 int，一下又存 String

TreeSet常用方法

点击查看方法摘要

EnumSet

EnumSet 是一个专为枚举类设计的集合抽象类，EnumSet 中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显式或隐式地指定。不允许添加 null 值。EnumSet 的集合元素也是有序的，它以枚举值在 Enum 类内的定义顺序来决定集合元素的顺序。

特点梳理：

• EnumSet的集合元素也是有序的，EnumSet以枚举值在Enum类内的定义顺序来决定集合元素的顺序

• EnumSet在内部以位向量的形式存储，这种存储形式非常紧凑、高效，因此 EnumSet 对象占用内存很小，而且运行效率很好。尤其是进行批量操作（如调用containsAll()和retainAll()方法）时，如果其参数也是EnumSet集合，则该批量操作的执行速度也非常快

• EnumSet 集合不允许加入 null 元素，如果试图插入 null 元素，EnumSet 将抛出 NullPointerException 异常

• EnumSet 类没有暴露任何构造器来创建该类的实例，程序应该通过它提供的类方法来创建 EnumSet 对象

• 如果只是想判断 EnumSet 是否包含 null 元素或试图删除 null 元素都不会抛出异常，只是删除操作将返回false，因为没有任何 null 元素被删除。

EnumSet 常用方法

点击查看方法摘要

Map

Map 接口采用键值对 Map 的存储方式，保存具有映射关系的数据，因此，Map 集合里保存两组值，一组值用于保存 Map 里的 key，另外一组值用于保存 Map 里的 value，key 和 value 可以是任意引用类型的数据。key 值不允许重复，可以为 null。如果添加 key-value 对时 Map 中已经有重复的 key，则新添加的 value 会覆盖该 key 原来对应的 value。常用实现类有 HashMap、LinkedHashMap、TreeMap等。

Map 声明的方法：

点击查看方法摘要

HashMap

HashMap 基于 hashing 原理，通过 put() 和 get() 方法存储和获取对象。当我们将键值对传递给 put() 方法时，它调用键（key）对象的 hashCode() 方法来计算 hashCode 值，然后找到对应的 bucket 位置来储存值（value）对象。当获取对象时，通过键（key）对象的 equals() 方法找到正确的键值对，然后返回对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会存储在链表的下一个节点中。

原理图 1：

注：JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

原理图 2： 原理图 3： 如上“原理图 3”，散列表中有散列数组，散列数组存放的元素是线性表（散列桶）。往散列表存放数据是键值对放进去，“Mac”和“Jerry”的HashCode一样，所以计算出来的散列值一样，假设该散列值计算得到的下标是2，就将“Mac”和“Jerry”存放在散列数组下标为2的这个散列桶里。而“Andy”的散列值计算得到的下标是8，那么“Andy”就保存在下标为8的散列桶里。由于所存放的数据只在下标为2和8的散列桶中，所以散列数组中其它位置则为空值。要找25这个元素，只要计算“Jerry”的散列值，最后计算得到下标2，然后在对应的散列桶中依次查找“Jerry”，就可以找到对应的25。

其实真正意义上的散列表如下图所示，以上“原理图”只是说明原理罢了，使用HashMap时将其想象成多行两列的表格即可。

真正存取的有意义的元素是key值所对应的value值，key值只不过是value值所取的名字，为了方便以后的查找之用。

特点梳理：

• 底层采用哈希表+链表或红黑树实现。

• 哈希表初始容量 1