关于算法系列，在前面已经整理过大O表示法和排序算法相关的文章，今天接着上次的话说一说散列表（Hash Table，也叫哈希表），顺便穿插和另外两种基本的数据结构，数组和链表比较；并在最后介绍良好的散列函数——SHA函数的使用。这三种基本数据结构，可简可繁，在写代码时候都是比较频繁使用的，那我们先从散列表开始入手。

散列表是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。散列表是最有用的基本数据结构之一，我们需要总结散列表：实现、冲突和散列函数。

实现

举个例子：为了查找电话薄中某人的号码，可以创建一个按照人名首字母顺序排列的表，即建立人名x到首字母F(x)的一个函数关系。在首字母为p的表中查找姓”彭”的电话号码，那么就可以直接调用这样的函数关系，查找的就快很多。这里使用人名作为了关键字，也就是键（Key）；”取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。

1
2
3
4
5
6

# 使用dict创建散列表phone_list
In [1]: phone_list = dict()
In [2]: phone_list["pross"] = 15013637180
# 映射关系输出
In [3]: print(phone_list["pross"])
15013637180

在代码中，散列表是由键和值组成，在散列表phone_list中，键为姓名，值为电话号码。散列表将键映射到值。为了对比性能，我们先介绍下数组。

数组

在计算机科学中，数据数据结构(array date structure)，简称为数组；是由相同类型的元素的集合所组成的数据结构，分配一块连续的内存来存储，可以利用元素的索引可以计算出该元素对应的存储地址。

还是举个例子：现在有个需求，要编写一个管理待办事项的应用程序，需要将这些待办事项存储在内存中，如果我们选用数组来存储，那么意味着所有的待办事项在内存中都是相连的。

1
2
3
4
5
6
7
8
9

# 定义数组
In [7]: do_list_tup = ()
In [8]: do_list_tup = ('1.doing homework','2.have dinner')
# 输出索引为1的待办事项
In [9]: print(do_list_tup[1])
2.have dinner
# 输出所有待办事项
In [10]: print(do_list_tup)
('1.doing homework', '2.have dinner')

如果现在我要先玩滑板，在写作业呢？那么就需要把后面的每一个待办事项都得挪一个位置才行，如果待办事项有很多很多，这种操作就有点麻烦了。接下来，我们得继续看看链表(Linked list)。

链表

链表中的元素可以存储在任何地方，链表的每个元素都存储了下一个元素的地址，从而使一系列的随机内存地址串在了一起。这就很方便的上面出现的问题了：直接在前面插入玩滑板，链表会存储一个标记表示下一个待办事项是写作业。

1
2
3
4
5
6
7
8
9
10
11

# 定义列表
In [11]: do_list = []
In [12]: do_list = ['1.doing homework','2.have dinner']
# 取出索引为1的元素
In [13]: print(do_list[1])
2.have dinner
# 插入插入待办事项
In [15]: do_list.insert(0,'3.Skateboarding')
# 输出
In [16]: print(do_list)
['3.Skateboarding', '1.doing homework', '2.have dinner']

链表的优势在插入元素方面，数组的优势在于查找，散列表的优势又是什么呢？

性能比较

在这里对这三种基本数据结构做一个对比总结，还记得前面说过的大O表示法么？

在平均情况下，散列表执行各种操作的时间都为O(1)，O(1)被称为常量时间。简单的查找的运行时间为线性时间，二分查找的速度更快，所需要的时间为对数时间，在散列表中查找所花费的时间是常量时间。这意味着无论散列表包含一个元素还是一亿个元素，从其中获取数据所需要的时间都是相同；其实从数组中获取一个元素所需要的时间也是固定的。

我们来将散列表同数组，链表来比较一下：

在平均情况下，散列表的查找速度和数组一样快，而插入和删除速度与链表一样快，在最糟的情况下，散列表的各种操作的速度都很慢。因此在使用散列表时，需要避开最糟糕的情况，也就是需要避开冲突。

冲突

散列表中存在冲突，什么冲突？就是散列函数不可能总是将不同的键均匀的映射到数组的不同的位置。拿在开头举的一个例子，为了查找电话薄中某人的号码，我们创建一个按照人名首字母顺序排列的表，以p开头姓名存储到对应的散列表位置中，但是以p开头的姓名也不是只有一个，就需要给多个键分配到了同一个位置，这样就会造成冲突。

最简单的是：如果两个键映射到同一个位置，就在这个位置存储一个链表。这样pross和paul都会映射到同一个位置，在访问以p开头的姓名时，速度依然很快。但需要查询pross的电话号码时，速度就慢一些；如果散列表存储的链表很长，散列表的速度也将急剧的下降。

处理冲突比较好的办法有：较低的填充因子和良好的散列函数。

填充因子

散列表的填充因子很容易计算：

        $$填装因子 = \frac{散列表包含的元素数}{位置总数}$$    

散列表使用数组来存储数据，因此需要计算数组中被占用的位置数，填装因子大于1，意味着元素超过了位置总数。一旦填充因子开始增大，就需要在散列表中添加位置，也就是调整长度(resizing)，长度增加，填装因子就变低，发生的冲突的可能性越小，散列表的性能也就越高。

一个不错的经验规则是：一旦填充因子大于0.7，就需要调整列表的长度。

调整长度的时间开销很大。

良好的散列函数

一个糟糕的散列函数就会让值扎堆，导致大量的冲突；选择一个良好的散列函数，能够让数组中的值呈均匀分布，解决冲突。这里介绍SHA函数，这也是扩展知识中的心动之处。

安全散列算法（英语：Secure Hash Algorithm，缩写为SHA）是一个密码散列函数家族（SHA-0，SHA-1，SHA-2，SHA-3），能计算出一个数字消息所对应到的，长度固定的字符串的算法（又称消息摘要）。且若输入的消息不同，它们对应到不同字符串的机率极高。

SHA是一个散列函数，它生成一个散列值，用于创建散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另外一个字符串，对于每个字符串，SHA生成的散列值极大可能不同。

1
2
3
4
5
6
7

In [20]: import hashlib
# 使用sha256
In [21]: hash = hashlib.sha256()
In [22]: hash.update('pross'.encode('utf-8'))
In [24]: hash.hexdigest()
Out[25]: '58f8b4db8a8d80bc485de70a57912ddcf8a2fa93e698e2ce346f9f54d859af5f'
...

扩展：密钥导出和扩展算法是为安全密码散列设计的，类似hashlib.sha256()这种简单算法不能有效抵御暴力破解，一个好的密码散列函数必须是可调节的，耗时的，并包含盐。

1
2
3
4
5
6

In [26]: import hashlib
# 密钥导出，pbkdf2_hmac(hash_name, password, salt, iterations, dklen=None)提供了使用PKCS#5填充的pbkdf2算法，使用HMAC作为伪随机函数
In [27]: dk = hashlib.pbkdf2_hmac('sha256',b'pross',b'salt',1000)
In [28]: import binascii
In [29]: binascii.hexlify(dk)
Out[29]: b'07c8f073bc2484c6163cd7c44d8d35f0b6ffc16e3b907df16bf8d292ccd176f9'

字符串hash_name是HMAC的哈希摘要算法的所需名称，例如：sha1或sha256；password和salt为字节的缓冲区，所以应该将password限制在合理的长度（1024）；iterations的数量基于散列算法和计算能力来选择。截至2013年，建议至少100,000次迭代的SHA-256；dklen是导出密钥的长度，如果dklen=None，则使用散列算法hash_name的摘要大小，例如，64为SHA-512的摘要大小。

快乐的时光总是短暂的，散列表及其各种天马行空的扩展知识就介绍到这。

完。