本文内容整理自JavaGuide

集合概述

Java 集合概览

Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collecton接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

四者区别

• List: 有序的、可重复
• Set: 无序的、不可重复
• Queue: 确定先后顺序，存储的元素是有序的、可重复
• Map: key-value

集合框架底层数据结构总结

Map

• HashMap：数组+链表+红黑二叉树
• LinkedHashMap：底层和 HashMap一样，不过增加了一条双向链表 （能够按照添加的顺序遍历）
• Hashtable： 数组+链表 （线程安全）
• TreeMap：红黑树 （元素有序）
• ConcurrentHashMap: jdk1.7为分段的数组+链表，1.8为数组+链表+红黑二叉树（线程安全）

List

• Vector：Object[] 数组 （线程安全）
• Arraylist： Object[] 数组 （线程不安全）
• LinkedList： 双向链表 （线程不安全）

Set

• HashSet : 基于 HashMap 实现
• LinkedHashSet: 内部是通过 LinkedHashMap 来实现的
• TreeSet: 红黑树

Queue

• PriorityQueue: Object[] 数组来实现二叉堆 （线程不安全）
• ArrayQueue: Object[] 数组 + 双指针

（Queue是单端队列，Deque 是双端队列，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。）

如何选用

对于Map：需要排序时选择 TreeMap, 不需要排序时就选择 HashMap, 需要保证线程安全就选用 ConcurrentHashMap，需要记录插入顺序就用LinkedHashMap.

RandomAccess 接口

ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的

PriorityQueue

优先队列

• 线程不安全
• O(logn) 的时间复杂度内插入元素和删除堆顶元素。
• 不支持存储 NULL 和 non-comparable 的对象
• 底层实现：二叉堆，默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

对比

ArrayDeque 与 LinkedList

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
• rrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
• 选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

HashMap 和 Hashtable

• HashMap 是非线程安全的，HashTable 是线程安全的（HashTable 基本被淘汰，不要在代码中使用它）
• 底层数据结构不同。
• 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
• 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。

HashMap 和 TreeMap

• 实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力
• 实现SortMap接口让 TreeMap 有了对集合中的元素根据键排序的能力
• 相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

ConcurrentHashMap 和 Hashtable

两个都是线程安全的：

• 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
• 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。
• Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

HashSet 如何检查重复

• hashcode不同则不同，插入；相同则调用equals()，如果equals()相同则不插入。

HashMap

put()过程：

• HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值
• 然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度）
• 如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀

HashMap 多线程操作导致死循环问题

1.7主要原因在于并发下的 Rehash （扩容操作）会造成元素之间会形成一个循环链表，同时会造成数据丢失的情况。
（JDK1.7的扩容操作，重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是形成死循环的关键点）

不过jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

总结

• HashMap 的底层是个 Node 数组（Node<K,V>[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。
• 增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：
  • 拿到 key 的 hashCode 值；
  • 将 hashCode 的高位参与运算，重新计算 hash 值；
  • 将计算出来的 hash 值与 “table.length - 1” 进行 & 运算。
• HashMap 的默认初始容量（capacity）是 16，capacity 必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * load factor。
• HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。
• 导致 HashMap 扩容后，同一个索引位置的节点重 hash 最多分布在两个位置的根本原因是：
  • table的长度始终为 2 的 n 次方；
  • 索引位置的计算方法为 “(table.length - 1) & hash”。HashMap 扩容是一个比较耗时的操作，定义 HashMap 时尽量给个接近的初始容量值。
• HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。
• 当同一个索引位置的节点在增加后达到 9 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。
• 当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。
• HashMap 在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。1.8之后扩容不需要再重新计算哈希

遍历方式

• 使用迭代器（Iterator）EntrySet 的方式进行遍历；
• 使用迭代器（Iterator）KeySet 的方式进行遍历；
• 使用 For Each EntrySet 的方式进行遍历；
• 使用 For Each KeySet 的方式进行遍历；
• 使用 Lambda 表达式的方式进行遍历；
• 使用 Streams API 单线程的方式进行遍历；
• 使用 Streams API 多线程的方式进行遍历。

entrySet 的性能比 keySet 的性能高出了一倍之多，因此我们应该尽量使用 entrySet 来实现 Map 集合的遍历。

使用注意

• 判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。
• 在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。
• 不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。
• 使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。
• 使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法， 它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

Collections.synchronizedList

SynchronizedList 就是在 List的操作外包加了一层synchronize同步控制。

List list = Collections.synchronizedList(new ArrayList());
      ...
  synchronized (list) {
      Iterator i = list.iterator(); // Must be in synchronized block
      while (i.hasNext())
          foo(i.next());
  }

Iterator<E> iterator();这个方法没有加锁，不是线程安全的，所以如果要遍历，还是必须要在外面加一层锁。

使用Iterator迭代器的话，似乎也没必要用Collections.synchronizedList的方法来包装了——反正都是必须要使用Synchronized代码块包起来的。

所以总的来说，Collections.synchronizedList这种做法，适合不需要使用Iterator、对性能要求也不高的情况。