这里不仅是说面试。在实际开发中，背诵一些基本操作也很有用。有查文档的时间，一些更复杂的思路就会被打断。这一点我亲有体会…
List/Set/Map/Queue
基础数据结构。尤其是前三个，所有面试都会问，除非和Java没关系。
List
就是列表。直觉上很容易理解。
常见实现
| 实现 | 底层 | 查询 | 插入/删除 | 是否线程安全 | 适用场景 |
|---|---|---|---|---|---|
ArrayList ⭐ | 动态数组 | O(1) | 尾部 O(1)，中间 O(n) | 否 | 默认首选 |
LinkedList | 双向链表 | O(n) | 已知位置附近 O(1) | 否 | 经常头尾插入删除 |
Vector | 动态数组 | O(1) | O(n) | 是（同步） | 老代码，不推荐 |
Stack | 继承 Vector | O(1) | O(1) | 是 | 已过时，推荐 Deque |
无脑使用ArrayList是一个好习惯，对大脑有好处。不过，对于经常需要插入/删除数据的情况，LinkedList则更胜一筹。
常用方法
Collection的方法（适用于List/Set/Queue等）
l.add("A") — 添加元素
l.remove("A") — 成功返回true，不存在返回false
l.contains("B") — 判断是否存在
l.size() — 获取元素个数
l.isEmpty() — 是否为空
l.clear() — 清空
l.iterator() — 获取一个迭代器
增强for
for (int i : l) {
System.out.println(s);
}
Iterator
Iterator<Integer> it = c.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
List的方法
l.get(0) — 获取某个index的元素
l.set(0, "C") — 设置某个index的元素
l.add(1, "D") — 在某个位置插入元素，指定的index会变为这个元素，原先所在的元素后移
l.remove(1) — 删除某个index的元素
l.indexOf("A") — 查找某个元素第一次出现的index，如果没有，返回-1
l.subList(1, 3) — 获取子列表，左闭右开（包括左不包括右）
l.sort(null) — 原地排序（小到大），传入Comparator.reverseOrder()可以实现大到小
Set
Set是“集合”，其中所有元素都是独一无二的。它常被用于确认某个元素是否存在的场景。大部分时候，顺序不重要。
Set 没有 index。
常见实现
| 实现 | 底层 | 排序 | 查询 |
|---|---|---|---|
HashSet ⭐ | HashTable | 无序 | O(1) |
LinkedHashSet | Hash + LinkedList | 保留插入顺序 | O(1) |
TreeSet | 红黑树 | 自动排序 | O(log n) |
EnumSet | Bit Vector | Enum 顺序 | O(1) |
TreeSet会自动排序，而LinkedHashSet只会保留插入顺序。
HashSet内部是完全无序的。
常用方法
由于没有索引，Set自己的常用方法很少。主要参考Collection的那些方法。
TreeSet提供一些额外方法，了解即可：
first()
last()
higher()
lower()
ceiling()
floor()
Map
我不知道怎么翻译这个词。某些编程语言会把这种结构叫做“字典”，或者俗称“哈希表”–但这就和具体实现挂上钩了。
这是一个很符合直觉的“键值对”结构。在逻辑上，列表可以说是此种结构–它们的Key只能是数字，并且从0往下排。但Map十分自由。可以使用任何值作为键，只需要它们是可哈希的（有合法的hashCode()和equals()实现）。
某些人可能会想起数学上的映射关系。
常见实现
| 实现 | 底层 | 顺序 | 查询 |
|---|---|---|---|
HashMap ⭐ | HashTable | 无序 | O(1) |
LinkedHashMap | Hash + LinkedList | 插入顺序 | O(1) |
TreeMap | 红黑树 | Key 自动排序 | O(log n) |
Hashtable | HashTable | 无序 | O(1) |
ConcurrentHashMap | 并发 Hash | 无序 | O(1) |
看到了吗，它和Set的实现非常类似！其实它们也共享了一些底层规律–
因为Map的键是唯一的，这一点和Set非常相似。它甚至可以看作一种带附加信息（也就是Value）的Set。
和Set相似，TreeMap可以对键进行排序，LinkedHashMap保留键值对插入的顺序，而HashMap内部是无序的。
ConcurrentHashMap很不一样。它是线程安全的。Hashtable是一个历史遗留类，它同样线程安全，但加锁方式粗暴，常导致性能问题。应避免使用。
另外，为了在并发环境下避免歧义，同时防止手动检查null的竞态条件问题，ConcurrentHashMap和Hashtable的键和值都不能为null。
常用方法
m.put("Lucy", 95) — 加入元素
m.get("Tom") — 获取元素，如果不存在返回null
m.remove("Tom") — 删除元素
m.containsKey("Tom") — 判断Key
m.containsValue(90) — 判断Value
m.keySet() — 获取key的集合
m.values() — 获取Collection<V>
遍历Entry
for (Map.Entry<String, Integer> e : m.entrySet()) {
System.out.println(e.getKey());
System.out.println(e.getValue());
}
m.forEach((k, v) -> {
System.out.println(k);
System.out.println(v);
})
Queue
队列是一种先进先出(FIFO)数据结构。
常见实现
| 实现 | 底层 | 特点 |
|---|---|---|
LinkedList | 双向链表 | FIFO |
ArrayDeque ⭐ | 循环数组 | 最推荐 |
PriorityQueue | 二叉堆 | 优先级队列 |
ConcurrentLinkedQueue | 无锁链表 | 并发 |
ArrayBlockingQueue | 数组 | 阻塞队列 |
LinkedBlockingQueue | 链表 | 阻塞队列 |
LinkedList由于其特性，可以直接用于队列，不会有性能问题。
ArrayDeque是大多数情况下的选择。它的性能通常比LinkedList更好。
PriorityQueue不是FIFO的，数据出队时总会按照一个从小到大的顺序。学过数据结构的人可能会联想到堆，对，它就是。
常用方法
q.peek() — 查看队首（将要被弹出的值）
q.poll() — 弹出队首，队列为空返回null
q.add(30) — 往队尾添加值，失败抛异常
q.offer(30) — 往队尾添加值，失败返回false而非抛异常
发表回复