字典、集合与哈希表

前言

不同于其他数据结构，字典和集合的内部结构都是一张哈希表。

对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。

而对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。

‍

哈希表结构的变化

老版本 Python 的哈希表结构如下所示：

--+-------------------------------+
  | 哈希值(hash)  键(key)  值(value)
--+-------------------------------+
0 |    hash0      key0    value0
--+-------------------------------+
1 |    hash1      key1    value1
--+-------------------------------+
2 |    hash2      key2    value2
--+-------------------------------+
. |           ...
__+_______________________________+

不难想象，随着哈希表的扩张，它会变得越来越稀疏。例如这样一个字典：

{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}

那么它会存储为类似下面的形式，这样的设计结构显然非常浪费存储空间：

entries = [
['--', '--', '--']
[-230273521, 'dob', '1999-01-01'],
['--', '--', '--'],
['--', '--', '--'],
[1231236123, 'name', 'mike'],
['--', '--', '--'],
[9371539127, 'gender', 'male']
]

为了提高存储空间的利用率，现在的哈希表除了字典本身的结构，会把索引和哈希值、键、值单独分开：

Indices
----------------------------------------------------
None | index | None | None | index | None | index ...
----------------------------------------------------

Entries
--------------------
hash0   key0  value0
---------------------
hash1   key1  value1
---------------------
hash2   key2  value2
---------------------
        ...
---------------------

那么，刚刚的这个例子，在新的哈希表结构下的存储形式，就会变成下面这样：

indices = [None, 1, None, None, 0, None, 2]
entries = [
[1231236123, 'name', 'mike'],
[-230273521, 'dob', '1999-01-01'],
[9371539127, 'gender', 'male']
]

我们可以很清晰地看到，空间利用率得到很大的提高。

‍