重要的集合接口以及实现类参考下图
classDiagram class Collection {<<interface>>} class List {<<interface>>} class Set {<<interface>>} class Map { <<interface>> entrySet()* keySet()* values()* } Collection <|-- List Collection <|-- Set List <|.. ArrayList List <|.. LinkedList List <|.. Vector Set <|.. HashSet Map <|.. HashMap Map <|.. TreeMap Map <|.. Hashtable Map <|.. ConcurrentHashMap HashMap <|.. LinkedHashMap Set <-- Map Collection <-- Map |
|
接口
- 接口四个：Collection、List、Set、Map，它们的关系：
- Collection 是父接口，List 和 Set 是它的子接口
- Map 接口与其它接口的关系
- Map 调用 entrySet()，keySet() 方法时，会创建 Set 的实现
- Map 调用 values() 方法时，会用到 Collection 的实现
List 实现（常见三个）
- ArrayList 基于数组实现
- 随机访问（即根据索引访问）性能高
- 增、删由于要移动数组元素，性能会受影响
- 【进阶】但如果增、删操作的是数组尾部不牵涉移动元素
- LinkedList 基于链表实现
- 随机访问性能低，因为需要顺着链表一个个才能访问到某索引位置
- 增、删性能高
- 【进阶】说它随机访问性能低是相对的，如果是头尾节点，无论增删改查都快
- 【进阶】说它增删性能高也是有前提的，并没有包含定位到该节点的时间，把这个算上，增删性能并不高
- Vector 基于数组实现
- 相对于前两种 List 实现是线程安全的
- 【进阶】一些说法说 Vector 已经被舍弃，这是不正确的
Set 实现
- HashSet 内部组合了 HashMap，利用 Map key 唯一的特点来实现 Set
- 集合中元素唯一，注意需要为元素实现 hashCode 和 equals 方法
- 【进阶】Set 的特性只有元素唯一，有些人说 Set 无序，这得看实现，例如 HashSet 无序，但TreeSet 有序
Map 实现（常见五个）
- HashMap 底层是 Hash 表，即数组 + 链表，链表过长时会优化为红黑树
- 集合中 Key 要唯一，并且它需要实现 hashCode 和 equals 方法
- LinkedHashMap 基于 HashMap，只是在它基础上增加了一个链表来记录元素的插入顺序
- 【进阶】这个链表，默认会记录元素插入顺序，这样可以以插入顺序遍历元素
- 【进阶】这个链表，还可以按元素最近访问来调整顺序，这样可以用来做 LRU Cache 的数据结构
- TreeMap 底层是红黑树
- Hashtable 底层是 Hash 表，相对前面三个实现来说，线程安全
- 【进阶】它的线程安全实现方式是在 put，get 等方法上都加了 synchronized，锁住整个对象
- ConcurrentHashMap 底层也是 Hash 表，也是线程安全的
- 【进阶】它的 put 方法执行时仅锁住一个链表，并发度比 Hashtable 高
- 【进阶】它的 get 方法执行不加锁，是通过 volatile 保证数据的可见性
P.S.
- 未标注的是必须记住的部分
- 标注【进阶】的条目是该集合比较有特色的地方，回答出来就是加分项，不过也根据自己情况来记忆
