集合是承载元素的容器。映射（map）数据结构就是为此而设计的。映射用来存放键/值对。
前言
集合是承载元素的容器。映射（map）数据结构就是为此而设计的。映射用来存放键/值对。
正文
Set 集合
集合的特点是：元素
不重复，无下标。集合的典型应用：
客户统计、词汇量统计。二分搜索树是非常好的实现集合的底层数据结构。二分搜索树实现的集合时间复杂度平均为O(log n),链表实现的集合时间复杂度为O(n)。多重集合中的元素可以重复集合分类 集合分类 集合类型特性 底层数据结构的实现 有序集合 元素具有顺序性 基于搜索树的实现 无序集合 元素没有顺序性 基于哈希表的实现 集合的时间复杂度(h 表示树的高度)操作 链表实现的集合 二分搜索树实现的集合 二分搜索树平均 增 add O(n) O(h) O(log n) 查 contains O(n) O(h) O(log n) 删 remove O(n) O(h) O(log n)
Map 映射
映射主要是一对一间的对应关系。存储(键，值)数据对的数据结构(Key, Value), 根据键(Key)，寻找值(Value)。在其他语言中有着其他名称，如 Python 的字典 dict。
二分搜索树是非常好的实现映射的底层数据结构。映射集合中的键可以重复映射分类 映射分类 映射类型特性 底层数据结构的实现 有序映射 键具有顺序性 基于搜索树的实现 无序映射 键没有顺序性 基于哈希表的实现 映射的时间复杂度(h 表示树的高度)操作 链表实现的映射 二分搜索树实现的映射 二分搜索树平均 二分搜索树最差 增 add O(n) O(h) O(log n) O(n) 查 contains O(n) O(h) O(log n) O(n) 改 set O(n) O(h) O(log n) O(n) 查 get O(n) O(h) O(log n) O(n) 查 contains O(n) O(h) O(log n) O(n)
Set 集合与 Map 映射间的关系
- 其实集合与映射两者很大程度是相同的。如果将映射的值 Value 统一设置 NULL，在这样看来映射也可以包装成集合。