散列表

  散列表中文又译为哈希表,散列表是一种通过将键(key)映射为值(value)从而实现快速查找的数据结构。哈希表的输入城可以是非常大的范围,但是输出城是固定范围,假设为 $s$。

  散列表的性质:

  1. 典型的散列表都拥有无限的输入值域。
  2. 输入值相同时,返回值一样。
  3. 输入值不同时,返回值可能一样,也可能不一样。
  4. 不同输入值得到的散列值,整体均匀的分布在输出域 $s$ 上。(重要)

  其中 1~3 点性质是散列表的基础,第 4 点是评价一个散列表优劣的关键,比如 “aaa1”、“aaa2”、“aaa3”,虽然相似,但计算出的哈希值差异巨大。

散列表实现方式

散列函数+链表构成的数组

  实现散列表的方法有很多种,第一种也是最常见的方式是:使用散列函数和一个链表构成的数组来实现散列表。

  当插入键(字符串或几乎其他所有数据类型)和值时,我们按照如下方法操作:

  1. 首先,计算键的散列值。键的散列值通常为 int 或者 long 型。请注意,不同的两个键可以有相同的散列值,因为键的数量是无穷的,而 int 型的总数是有限的。
  2. 之后,将散列值映射为数组的索引。可以使用类似于 hash(key) % array_length 的方式完成这一步骤,不同的两个散列值则会被映射到相同的数组索引。
  3. 此数组索引处存储的元素是一系列由键和值为元素组成的链表。请将映射到此索引的键和值存储在这里。由于存在冲突,我们必须使用链表:有可能对于相同的散列值有不同的键,也有可能不同的散列值被映射到了同一个索引。

  通过键来获取值则需重复此过程。首先通过键计算散列值,再通过散列值计算索引。之后,查找链表来获取该键所对应的值。

  如果冲突发生很多次,最坏情况下的时间复杂度是O(N),其中N是键的数量。但是,我们通常假设一个不错的实现方式会将冲突数量保持在最低水平,在此情况下,时间复杂度是$O(1)$。

平衡二叉搜索树

  该方法的查找时间是O(logN)。该方法的好处是用到的空间可能更少,因为我们不再需要分配一个大数组。还可以按照键的顺序进行迭代访问,在某些时候这样做很有用。

References

  1. 《程序员面试金典》