Skip to main content

集合和映射

集合是承载元素的容器。映射（map）数据结构就是为此而设计的。映射用来存放键/值对。

前言​

集合是承载元素的容器。映射（map）数据结构就是为此而设计的。映射用来存放键/值对。

正文​

Set 集合​

  • 集合的特点是：元素不重复，无下标。

  • 集合的典型应用：客户统计、词汇量统计。

  • 二分搜索树是非常好的实现集合的底层数据结构。

  • 二分搜索树实现的集合时间复杂度平均为O(log n),链表实现的集合时间复杂度为O(n)。

  • 多重集合中的元素可以重复

  • 集合分类集合分类集合类型特性底层数据结构的实现
    有序集合元素具有顺序性基于搜索树的实现
    无序集合元素没有顺序性基于哈希表的实现
  • 集合的时间复杂度 (h 表示树的高度)操作链表实现的集合二分搜索树实现的集合二分搜索树平均
    增 addO(n)O(h)O(log n)
    查 containsO(n)O(h)O(log n)
    删 removeO(n)O(h)O(log n)

Map 映射​

  • 映射主要是一对一间的对应关系。存储(键，值)数据对的数据结构(Key, Value), 根据键(Key)，寻找值(Value)。在其他语言中有着其他名称，如 Python 的字典 dict。

  • 二分搜索树是非常好的实现映射的底层数据结构。

  • 映射集合中的键可以重复

  • 映射分类映射分类映射类型特性底层数据结构的实现
    有序映射键具有顺序性基于搜索树的实现
    无序映射键没有顺序性基于哈希表的实现
  • 映射的时间复杂度 (h 表示树的高度)操作链表实现的映射二分搜索树实现的映射二分搜索树平均二分搜索树最差
    增 addO(n)O(h)O(log n)O(n)
    查 containsO(n)O(h)O(log n)O(n)
    改 setO(n)O(h)O(log n)O(n)
    查 getO(n)O(h)O(log n)O(n)
    查 containsO(n)O(h)O(log n)O(n)

Set 集合与 Map 映射间的关系​

  • 其实集合与映射两者很大程度是相同的。如果将映射的值 Value 统一设置 NULL，在这样看来映射也可以包装成集合。