Java 集合知识点总结

本文是个人阅读学习JavaGuide的集合知识的总结笔记。

总览

Collection接口，主要用于存放单一元素；
Map 接口，主要用于存放键值对。

• List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
• Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
• Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
• Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x” 代表 key，“y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

Collection 接口

需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

List

ArrayList： Object[] 数组（线程不安全）
LinkedList： 双向链表 (线程不安全，JDK1.6 之前为循环链表，JDK1.7 取消了循环)
Vector：Object[] 数组 (古老实现类，线程安全)

推荐使用 ArrayList，性能更好，可以完全替代 LinkedList。

ArrayList源码&扩容机制

ArrayList 的底层是数组队列，相当于动态数组，适用于频繁的查找工作，线程不安全。与 Java 中的数组相比，它的容量能动态增长。

ArrayList 继承于 AbstractList ，实现了 List, RandomAccess（快速随机访问）, Cloneable（能被克隆）, java.io.Serializable（支持序列化）这些接口。

• 以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
• grow()方法，扩容的核心方法。int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！

Set

HashSet(无序，唯一): 底层数据结构是哈希表（基于 HashMap 实现），底层采用 HashMap 来保存元素。用于不需要保证元素插入和取出顺序的场景。

HashSet 检查重复：
当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功

LinkedHashSet: 是 HashSet 的子类，底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的。用于保证元素的插入和取出顺序满足 FIFO 的场景。

TreeSet(有序，唯一): 底层数据结构是红黑树 (自平衡的排序二叉树) 元素是有序的，排序的方式有自然排序和定制排序。用于支持对元素自定义排序规则的场景。

Queue

• PriorityQueue: Object[] 数组来实现二叉堆。在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。非线程安全的，默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

• ArrayQueue: Object[] 数组 + 双指针

• Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

• Deque 是双端队列，在队列的两端均可以插入或删除元素。

• 选用 ArrayDeque 来实现队列要比 LinkedList 更好。ArrayDeque 也可以用于实现栈。

Map接口

HashMap

HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap源码&底层数据结构

• JDK1.8 之前，HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。
• JDK1.8 以后，在解决哈希冲突时有了较大的变化。当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。

HashMap 的遍历

• entrySet 的性能比 keySet 的性能高出了一倍之多，因此我们应该尽量使用 entrySet 来实现 Map 集合的遍历。
• EntrySet 之所以比 KeySet 的性能高是因为，KeySet 在循环时使用了 map.get(key)，而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。为什么要用“又”这个词？那是因为在使用迭代器或者 for 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 map.get(key) 查询时，相当于遍历了两遍。
• 不能在遍历中使用集合 map.remove() 来删除数据，这是非安全的操作方式，但我们可以使用迭代器的 iterator.remove() 的方法来删除数据，这是安全的删除集合的方式。
• 我们应该尽量使用迭代器（Iterator）来遍历 EntrySet 的遍历方式来操作 Map 集合，这样就会既安全又高效了。

LinkedHashMap

LinkedHashMap： 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

TreeMap

TreeMap： 红黑树（自平衡的排序二叉树）实现了 NavigableMap 接口（对集合内元素的搜索的能力）和 SortedMap 接口（对集合中的元素根据键排序的能力）。

Hashtable

Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）Hashtable 基本被淘汰了。

需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。

ConcurrentHashMap 源码&底层数据结构

• Java 7 中 ConcurrentHashMap 的存储结构为 Segment 数组 + HashEntry 数组 + 链表 。
• 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容，它的冲突会转化为链表。
• 但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

• Java8 的 ConcurrentHashMap 相对于 Java7 来说变化比较大，ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。
  
  本文是阅读学习JavaGuide的总结笔记，详细请参考原文链接