【进击面试_01】Java 集合

1.1 List

1.1.1 ArrayList

ArrayList 是最常用的 List 实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足需要扩容时，就要将旧的数组复制到新的数组中。当从 ArrayList 的中间位置插入或者删除元素时，对数组进行复制、移动需要的代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

ArrayList 是线程不安全的，只能用在单线程环境下，多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类获取。ArrayList 实现了 RandomAccess 接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了 Cloneable 接口，能被克隆，实现了 Serializable 接口，支持序列化，能够通过序列化传输。

ArrayList 提供了三个构造方法，可以使用空参构造生成的一个初始容量为 10 的集合；也可以传递一个初始容量，构造一个指定容量的集合；还可以传递一个 Collection，并转化为数组后赋给 ArrayList 实现类。

ArrayList 在每次增加元素时，都要调用 ensureCapacityInternal 方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的 1.5 倍，如果设置的新容量还不够，则直接将新容量设置为传入的参数，而后用 Arrays.copyof() 方法将元素拷贝到新的数组。

1.1.2 Vector

Vector 与 ArrayList 一样，也是通过数组实现的，默认大小为10。不同的是方法中加了锁机制，是线程安全的，即某一时刻只有一个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问 ArrayList 慢。

1.1.3 LinkedList

LinkedList 是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

LinkedList 是线程不安全的，只在单线程下适合使用。LinkedList 同时实现了 List 接口和 Deque 接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，还可以看作一个栈(Stack)。实现了 Serializable 接口，因此它支持序列化，能够通过序列化传输，实现了 Cloneable 接口，能被克隆。LinkedList 提供了两个构造方法，空参构造不用多说，有参构造接收一个 Collection，先调用空参构造创建一个空的链表然后将 Collection 中的数据追加到链表后。

1.1.4 ArrayDeque

ArrayDeque 是一个基于数组实现的双端队列，官方更推荐其用于栈或队列。ArrayDeque 底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组，即数组的任何一点都可能被看作起点或者终点。另外，该容器不允许放入 null。

ArrayDeque 是线程不安全的，当多个线程同时使用的时候，需要手动同步；ArrayDeque 实现了 Deque 接口，可以作为栈或队列；实现了 Cloneable 接口，可以进行克隆；实现了 Serializable 接口，可以进行序列化。需要注意的是 ArrayDeque 默认容量为 16，在扩容时默认扩容为现有容量的 2 倍。

1.2 Set

1.2.1 HashSet

哈希表里存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序，而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的 hashcode 方法来获取的，HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法如果 equls 结果为 true，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。哈希值相同但 equals 为 false 的元素是怎么存储呢，就是在同样的哈希值下顺延，即挂在上一个后面。

阅读源码可以发现，HashSet 仅仅是对 HashMap 做了一层包装，只使用了 Map 的 key，value 使用一个 Object 对象来填充。

1.2.2 LinkHashSet

HashSet 还有一个子类 LinkedHashSet，LinkedHashSet 集合也是根据元素的 hashCode 值来决定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。也就是说，当遍历 LinkedHashSet 集合里的元素时，LinkedHashSet 将会按元素的添加顺序来访问集合里的元素。 LinkedHashSet 需要维护元素的插入顺序，因此性能略低于 HashSet 的性能，但在迭代访问 Set 里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。虽然 LinkedHashSet 使用了链表记录集合元素的添加顺序，但 LinkedHashSet 依然是 HashSet，因此它依然不允许集合元素重复(由哈希表保证唯一性，链表保证存取一致)。

1.2.3 TreeSet

TreeSet 是 SortedSet 接口的实现类，底层是二叉树，可以对对象元素进行排序，因此确保集合元素处于有序状态。如果把一个对象添加到 TreeSet 时，则该对象的类必须实现 Comparable 接口，重写 comparaTo() 方法否则程序将会抛出异常。TreeSet 也可以保存对象元素的唯一性(并不是一定保证唯一性，需要根据重写的 comparaTo() 方法来确定)

1.3 Map

1.3.1 HashMap

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。

在 JDK 1.8 以前，HashMap 还采用的是数组链表的形式存储，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的链表部分就麻烦了，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，JDK 8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以 1.8 以后采用数组链表红黑树形式存储。链表元素少时依旧使用链表，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以将时间复杂度降低为 O(logN)。

1.3.2 ConcurrentHashMap

整个 ConcurrentHashMap 由一个个 Segment 组成(Segment 有部分、片、段的意思，所以技术上将其其描述为分段锁)。简单来说，ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 Segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。再具体到每个 Segment 内部，其实每个 Segment 很像 HashMap，不过它要保证线程安全。

JDK1.8 中的 ConcurrentHashMap 选择了与 HashMap 相同的底层实现数组链表红黑树；在锁的实现上，抛弃了原有的 Segment 分段锁，采用 CAS synchronized 实现更加细粒度的锁。将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点，就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。

1.3.3 其他 Map

☞ TreeMap

TreeMap 实现了 SortedMap 接口，也就是说会按照 key 的大小顺序对 Map 中的元素进行排序，key 大小的评判可以通过其本身的自然顺序，也可以通过构造时传入的比较器进行排序。TreeMap 底层通过红黑树实现，时间复杂度为 log(n)。

☞ LinkHashMap

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 iterator 遍历 LinkedHashMap时，先得到的记录肯定是先插入的。

☞ Hashtable

从 Hashtable 的类名上就可以看出它是一个古老的类，它的命名甚至没有遵守 Java 的命名规范，现在 Hashtable 本身已经淡出了我们的视野。Hashtable 很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，但是并发性不如 ConcurrentHashMap，因为ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。

1.4 红黑树

1.4.1 什么是红黑树

普通的二叉查找树在进行插入和删除等可能会破坏树的平衡的操作时，可退化成链表，此时的增删查效率都会比较低下。为了避免这种情况，就出现了自平衡的二叉查找树——红黑树。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。简单来说，红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质： ♞ 性质1：每个节点要么是黑色，要么是红色。 ♞ 性质2：根节点是黑色。 ♞ 性质3：每个叶子节点(NIL)都是黑色。 ♞ 性质4：每个红色结点的两个子结点一定都是黑色。 ♞ 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。黑子结点肯定有两个子结点。

有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成，且任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量等于黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。