集合与映射

复习

　　哈希表是很强大的底层工具，但直接拿它写代码，还是太“原始”了。实际使用时，我们更常用两个建立在它之上的抽象：集合和映射。

　　集合（set）关注的，是“某个元素在不在里面”。它通常支持：

　　它有几个重要特性：元素不重复，也不关心顺序。 重复加入同一个元素，集合里仍然只有一份。

　　集合特别适合去重和判断存在性。比如“统计一篇文章里出现了哪些不同的单词”，用集合就再自然不过——重复出现的自然被合并。

　　映射（map，也叫字典）保存的是键到值的对应关系。它通常支持：

　　现实中的例子到处都是：电话簿里“姓名 → 号码”，配置表里“设置项 → 取值”，缓存里“请求 → 结果”。只要能想到“用一个东西查另一个东西”，背后往往就是一个映射。

　　映射也可以理解成“带标签的集合”：每个键唯一，但都能对应一个值。

　　集合和映射都只是抽象，具体用什么实现，可以选：

　　这就回到了那个熟悉的判断：你需要快，还是需要有序？

　　这也再次说明：抽象数据类型定好了“能做什么”，而选哪种实现，取决于你的具体需求。接下来的章节，我们就会走进“有序”那一派的核心结构——树。

思考题 1

　　集合和映射在“存什么”上有什么不同？

思考题 2

　　如果需要按键有序遍历，哈希表还合适吗？

　　集合只存“元素本身”，关心的是“在不在”；映射存的是“键到值”的对应关系，关心的是“某个键对应什么值”。可以理解为映射是给每个唯一键又附加了一个值。

　　不合适。哈希表的元素按哈希值散落，本身不维持任何顺序，无法按键有序遍历。这种需求更适合用平衡树等有序结构，它们能在 O(log n) 操作的同时保持有序。

设计师 | 南国微雪