A hash table (hash map) is a data structure which implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

散列函数

散列函数是这样的函数，无论你给它什么数据，它都会给你一个数字。用专业的话说，“散列函数将输入映射到数字。”

  1. 散列函数总是将同样的输入映射到相同的索引。
  2. 散列函数总是将不同的输入映射到不同的索引。（有问题，暂且先这样理解）
  3. 散列表知道数组有多大，只返回有效的索引。

任何一门优秀的语言都提供了散列表的实现，python提供的散列表的实现为字典。可以通过dict来创建散列表。像之前leetcode中的Two Sum，最快捷的方法就是使用dict。

1
2
3
4
#第一种创建方法
hash_table = dict()
#第二种创建方法
hash_table = {}

应用

散列表的用途十分广泛，下面介绍一下它的用途。

将散列表用于查找

散列表常被用于大海捞针式的查找。例如，我们常见的DNS解析（将网址映射到IP地址），散列表就是实现这种功能的方式之一。

散列表用于查找,大致分为两个步骤：

  1. 创建映射
  2. 查找

    防止重复

  3. 创建映射
  4. 检查是否重复

    将散列表用作缓存

    缓存是一种常用的加速方式，所有的大型网站都使用缓存，而缓存的数据就是存储在散列表中的。

当URL不在缓存中时，才让服务器做处理，并将生成的数据存储到缓存中，再返回它。

1
2
3
4
5
6
7
8
9
cache = {}

def get_page(url):
  if cache.get(url):
    return cache[url]
  else:
    data = get_data_from_server(url)
    cache[url] = data
    return data

冲突

这里我们没有讨论散列表内部的原理，但是我们依旧需要考虑散列表的性能，我们需要搞清楚什么是冲突。

之前谈到散列函数总是将不同的输入映射到不同的索引，这句话实际上是有问题的。因为这只是最理想的情况，实际上散列函数可能将不同的输入映射到同一个索引。这种情况就是冲突。处理冲突的方法有很多，最简单的办法就是：如果两个键映射到了同一个位置，就在这个位置存储一个链表，但是链表很长依然会影响散列表的性能。
因此，需要记住：

  1. 散列函数很重要；
  2. 如果散列函数很好，这些链表就不会很长。

    性能

    在平均情况下，散列表执行各种操作的时间都为O(1)，O(1)被称为常量时间。
    在最糟情况下，散列表所有操作的运行时间都为O(n)，—线性时间，这就比较慢了。

所以，避开最糟情况很重要，为此我们需要：

  1. 较低的填装因子
  2. 良好的散列函数

填装因子

填装因子=散列表包含的元素数/位置总数

填装因子是用来度量散列表中有多少位置是空的。大于1意味着元素数量超过位置数，需要在散列表中添加位置，这被称为调整长度（resizing）。

填装因子越低，发生冲突的可能性越小，散列表的性能越高，一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

调整散列表的长度开销很大，所以最好不要频繁这样操作。但平均而言，即便考虑调整长度所需的时间，散列表操作所需的时间仍为O(1)。

良好的散列函数

良好的散列函数，让数组中的值呈均匀分布。糟糕的散列函数让值扎堆，导致大量冲突。

SHA就是一种良好的散列函数，之后将会做详细的介绍。

参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著