字典是一种支持基于关键码的数据存储与检索的数据结构, 也称就查找表, 映射, 关联表等.

1. 字典的线性表实现

  • 使用一个数组来保存字典的 key, 如果我们不考虑重复问题, 每次添加新的 key 都是在末尾添加, 这样都是 O(1), 而在查找方面, 需要遍历所有的值, 所以是 O(n), 删除操作也是一样需要 O(n). 基于这种表的字典:
    • 数据结构和算法简单, 检索方便
    • 检索效率低, 当表很大时, 检索很耗时
    • 删除操作也很耗时, 删除后还需要移动后面的数据
  • 依旧使用的一个数组来实现. 不过我们会保持数组(key)处于一个有序的状态. 这样检索和删除时, 使用二分查找, 查找效率是 O(logN), 而在删除或者添加数据时, 为保证数组总是有序, 我们可能需要移动整个数组, 所以最差是 O(n). 这种实现方法也不适合经常添加, 删除数据, 而如果一次生成, 多次查找, 效率就很高了

不管我们是使用数组或者链表来实现线性表, 其表现是一样的

  • 在非有序实现中, 在表头插入时依旧是 O(1), 删除操作依旧顺序扫描整个表, 为 O(n)
  • 在有序实现中, 查找和插入都是 O(n). 因为链表都是得从表头开始查找

2. 基于散列表的实现

2.1 简述

如果我们数据在计算机存储方式是连续的, 那么我们只要知道一个数据的下标, 那么我们查找数据时总是 O(1), 而如果这个下标正好是我们的 key 值的话, 那么这个字典的查找就很快了.

基于这种想法, 带来的问题有:

  • 数据的 key 的不一定是整数
  • 即使 key 是整数, 可能也是很大的整数, 比如 18 位的身份证号就可能有 1018 个数(不考虑非法数值情况)

解决问题的方法是, 定义一个函数 h(key), 函数参数为 key 值, 然后我们总是能得到一个较小的整数值. 这个函数称之为 hash 函数, 或者散列函数

2.2 冲突问题

一般来说, key 的值是不确定性的, 可能会很大. 这就决定了, 如果我们在设计 hash 函数时产生的下标范围过小时, 在大量的 hash(key) 计算后, 总有可能得到相同的下标值. 比如我们采用 mod 100 来计算下标, 如果 key 的范围是 10000 甚至以上, 总会有相同的下标产生. 这时我们就称之为产生了冲突.

如果冲突过多, 会导致哈希表查找效率下降. 但如果要完全无冲突, 就得使用一个很大的表. 我们需要一个负载因子系数来衡量这种情况.

负载因子 𝜶 = 散列表中实际数据大小 n / 散列表的存储大小 m

一般我们都会取 0.70, 0.75 左右的值, 也就是说, 表中数据存储的了 70% 左右就考虑扩容

2.3 散列函数

散列函数的设计优劣会影响散列表的性能, 在设计散列函数时, 应当考虑以下几点

  • 函数的值要在设计的散列表下标范围内, 如果总是超出, 我们只能扩大散列表, 不然这下标是无意义的
  • 函数的值最好能均匀的分布在散列表中, 这说明更不容易产生的冲突
  • 函数的计算方式要简单快速. 这很明显, 如果 hash 比查找的时间长的多, 还不如直接查找来的快

如果我们知道 key 的范围或者一些相似的特征集合, 就能设计出最适合的散列函数, 甚至还可能不出现冲突. 不过只对特定的值, 一般我们面对的 key 值都是变化多端的

  1. 数字分析法

    在给定的关键集合中, 分析出一些数字出现的频率, 从中选出分布情况较好的若干数字作为散列函数的值. 从这需要我们事先知道会出现的值的范围, 否则不能使用.

    比如给出若干 000125672, 000125873, 000125776, 000125472, 000125379, 000125672 这些个数字, 可以统计出个位和百位的集合像, 62, 73, 76, 42, 39, 62 是不太重复的, 这样我们就可以取 100 内作为下标的散列表

  2. 折叠法 将较长的关键码切分为几段, 通过某种运算将它们合并, 比如加法, 二进制运算等.

    比如有 1456268793, 分成 1 + 456 + 268 + 793 = 1518, 去掉进位后为 518, 这样就把 10 位数散列到了 [0, 999] 区间内

  3. 中平方法 先求出关键码的平方, 然后取出中间的几位作为散列值

    比如有 1456268793, 平方后是 2120718797465676849, 从中取出连续的三位数作为散列值, 比如万位开始的 768

  4. 除余法 关键码是整数时, 用关键码除以散列表的大小 m, 得到的余数即是对应的下标(key mod m). 由于计算机是二进制运算, 所以我们常取 m 的大小为 2n.

  5. 基数转换法 把数转换成其他进制数, 然后再使用除余法

2.4 冲突的解决

  • 开地址法: 开地址法最主要的思想就是, 当冲突发生时, 就在散列表中的下一个为空的地方来放. 查找下一个空槽的方法也有多种, 像线性查找, 就是按顺序一个一个查找过去, 直到找到一个为空的槽. 这导致了当我们的散列表冲突比较多时, 查找会越来越长, 并且数据会比较集中在一个地方. 还有一种方法, 就是隔几个槽来放置而不是挨着放, 比如产生冲突时, 隔 3 个查找位置, 这样能稍微使数值平均分布些
  • 溢出区方法: 设置一个溢出存储区, 一般是一个线性表. 当发生冲突时, 就把这个冲突的后来者放入来溢出存储区中. 然后在查找的时候, 查找到的是原先的冲突项, 如果槽是空说明值不存在. 如果是非空, 对比其中的数值标志, 不相同的话, 说明先前有过冲突, 再去溢出区查找, 直到找到或者找不到. 使用这种方法, 当溢出区增大时, 散列表性能会线性下降
  • 桶散列: 我们假定散列中都有自己一个指针指向一个链表, 当发生冲突时, 我们就把新来的 key 加到指针指向的链表中, 这样我们在查找时, 如果链表长度不是 1, 那么按顺序遍历链表即可.

3. 集合

3.1 简单线性表实现

使用线性表, 也就是数组, 链表之类的来实现集合, 简单, 快捷, 这两种实现性能一致的

  • in 操作: 因为要遍历整个表, 所以是 O(n)
  • add 操作: 因为首先要判断添加的值是否在集合中, 所以是 O(n), 虽然添加那步只是 O(1)
  • remove: 总是先要 in 操作
  • 交集, 并集, 差集这样操作会导致 O(n<sup>2</sup>), 因为总是要遍历两个集合所有元素

如果我们让线性表总是保持其有序, 这样在查找的时候使用二分查找可以使用之降到 O(logN)

3.2 散列表实现

我们可以使用散列表来实现集合, 这样查找操作就变成了 O(1). 在交集, 并集, 差集操作中, 只要 O(m + n)

4. Python 中的 dict 和 set

在 CPython 中这两者都是使用散列方法实现的

  • dict 类型的 key 是一个不可变对象, 不可变对象都实现了 hashable 方法. 值可以是任意对象
  • 创建空或者很小的字典时, 初始容量为 8
  • 当负载因为超过 2/3 时自动扩大表的容量, 如果容量不大, 按 4 倍来扩大. 当容量超过 50000 时, 按 2 倍扩大

5. 二叉排序树

  • 二叉排序树的左子树上的值总是小于(有需要的话也可以等于根)
  • 二叉排序树的右子树上的值总是大于(有需要的话也可以等于根)
  • 根结点左边的总是结右边的值小, 也就是说结点的左右子树是有大小关系的, 跟堆使用的不一样, 堆使用的二叉树不要求左右再边的关系
  • 二叉排序树不一定是满二叉树, 由于值大小的分布不确定性造成的

根据二叉排序树的几个性质:

  1. 我们使用中序遍历(左-根-右)便能得到一个升序的序列