Java集合类是JDK学习中的一个经典切入点，也是让初学者最初感受到Java魅力的地方之一，你一定不会忘记不需要关心大小的ArrayList，不用自己实现的Queue，和随处可见的HashMap。面试中，对Java基础的考察中，集合类和String相关是两个重点，这里集中整理了关于集合类的一些知识点。
集合类的结构
要求手绘结构图，同时抛出一些简单的线索勾引面试官提问（比如讲HashMap的HashTable的区别）。
image.png
XX和XX的区别
ArrayList & Vector & LinkedList
- 实现方式：
- ArrayList、Vector 基于数组实现
- LinkedList 基于链表实现
- 同步问题：
- ArrayList、LinkedList 不是线程安全的
- Vector 是线程安全的，实现方式是在方法上加 synchronized 关键字进行修饰
- 适用场景和性能消耗：
- ArrayList 和 Vector 基于数组实现，所以随机位置增、删是 O(n) 的时间复杂度，另外可能会出现扩容的问题，也是 O(n) 的时间复杂度
- LinkedList 不会出现扩容的问题，所以比较适合随机位置增、删。但是其基于链表实现，所以在定位时需要线性扫描，会消耗 O(n) 的时间复杂度
- 扩容：
- ArrayList默认初始容量为10，每次扩容为原来的1.5倍
- Vactor默认初始容量为10，默认每次扩容为原来的2倍（可通过capacityIncrement设置）
HashMap & HashTable
- HashMap是非线程安全的，HashTable是线程安全的
- 扩容机制相同
HashMap & TreeMap
- HashMap实现了Map接口，不保障元素顺序。实现原理balabala
- TreeMap实现了SortedMap接口，是一个有序的Map。内部采用红黑树实现，红黑树是一种维护有序数据的高效数据结构，但具体算法没有掌握
HashMap & LinkedHashMap
- HashMap是无序的；如果希望容器按照自定义顺序遍历可使用TreeMap；如果希望按照插入顺序遍历，可使用LinkedHashMap
- LinkedHashMap是HashMap的一个子类，与HashMap相比，在Entry中增加了before、after两个引用，利用双向链表维护插入顺序
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
HashSet & HashMap
- HashMap实现了Map接口，原理balabala
- HashSet实现了Set接口，实质上封装了一个HashMap。在HashSet封装的HashMap中，entry.key为HashSet的元素（从而保证元素的唯一），entry.value统一指向一个static final的Object对象
参考：
本文链接：Java集合类综合
作者：猴子007
出处：https://monkeysayhi.github.io
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布，欢迎转载，演绎或用于商业目的，但是必须保留本文的署名及链接。
