Python的字典与散列表

老齐

发布于 2021-03-11 15:15:19

4.7K0

发布于 2021-03-11 15:15:19

文章被收录于专栏：老齐教室

说明： 本文是上一篇《Python的可散列对象》的续篇，两者都是对《Python大学实用教程》和《跟老齐学Python：轻松入门》有关字典内容的进阶知识。

与本书相关的更多内容，请访问：https://www.itdiffer.com

散列表

了解了散列函数之后，就可以看看散列表是什么了。散列表是一种数据结构，它存储的是键值对（key-value）。

在散列表中，每个键值对的键必须是可散列的，这是因为存储的键值对通过使用其键的散列值进行索引。如果查询散列表中的某个元素，其查询速度与表中所存储的键值对数量无关，不论表的长度增加10倍还是10万倍，查询某个特定元素的速度都不会受到影响。

散列表是怎么实现的呢？一种经典的做法是通过一个可变容器存储数据和索引，并通过键的散列值建立索引，借此可以查询到特定的数据。形象地说，是创建一个大桶（bucket），里面放很多小桶。每个小桶都由键的散列值建立索引，小桶中装的就是数据。

在下面的示例中，演示用Python实现散列表，从中可以理解散列表的基本余力。当然，在真正的编程中，不需要自定义这种散列表对象，因为Python中的字典类型对象就能实现。

import pprint

class Hashtable:
    def __init__(self, elements):
        self.bucket_size = len(elements)
        self.buckets = [[] for i in range(self.bucket_size)]
        self._assign_buckets(elements)

    def _assign_buckets(self, elements):
        for key, value in elements:
            hashed_value = hash(key)
            index = hashed_value % self.bucket_size
            self.buckets[index].append((key, value))

    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        bucket = self.buckets[index]
        for key, value in bucket:
            if key == input_key:
                return(value)
        return None

    def __str__(self):
        return pprint.pformat(self.buckets) # 返回一个可打印的对象

if __name__ == "__main__":
     capitals = [
        ('France', 'Paris'),
        ('United States', 'Washington D.C.'),
        ('Italy', 'Rome'),
        ('Canada', 'Ottawa')
    ]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")

注意观察第10行开始的for循环语句，在第11行，计算每个可散列元素的键的散列值，用它计算一个索引值（第12行），将此索引值作为self.buckets容器（bucket，也有直接译为“桶”）的索引（第13行），并向该索引对应的数据结构（列表）中增加数据(key,value)。

如果将前面提到过的环境变量PYTHONHASHSEED的值设置为46

^{[5]}

，就会得到下面的输出结果。有两个空容器，另外两个容器中分别存储了两个键值对数据。

[[('United States', 'Washington D.C.'), ('Canada', 'Ottawa')],
 [],
 [],
 [('France', 'Paris'), ('Italy', 'Rome')]]
The capital of Italy is Rome

注意，如果不设置PYTHONHASHSEED 的值，会得到与上述显示不一样的值。

在这个示例中，用Python创建了一个散列表，以元组为元素的列表作为输入。在初始化的时候，以输入对象的长度创建一个列表容器，然后将输入的数据存储到此容器中。

然而，如你在输出中所见，在输出结果中，有两个空列表，有另外两个列表中分别存储了不同的两个数据，这是什么原因？是因为在这个Python散列表中出现了散列碰撞。

使用Python标准库中的hash()函数计算散列值，出现碰撞是在所难免的。为此可以用扩大容器的容量（即长度），从而降低出现碰撞的概率，但是不能根本杜绝。

另外，容器的数量扩大，也会浪费更多的空间。下面的示例做了一点修改，在第4行，将self.bucket_size变为原来的2倍了。

hl_lines=”3” 
class Hashtable: 
    def __init__(self, elements): 
        self.bucket_size = len(elements) * 2 
        self.buckets = [[] for i in range(self.bucket_size)] 
        self._assign_buckets(elements)

再次执行程序，得到了下面的结果，仍然没有解决碰撞问题，并且已经有五个空容器了。

[[],
 [],
 [],
 [('Canada', 'Ottawa')],
 [],
 [],
 [('United States', 'Washington D.C.'), ('Italy', 'Rome')],
 [('France', 'Paris')]]
The capital of Italy is Rome

如果有两个散列碰撞，它们会被放入同一个容易。既然碰撞在所难免，那么在实现哈希表的时候，就要解决这个问题。通常的解决方法有两种：

开放式寻址法（open addressing）
分离链接法（separate chaining）

分离链接法在上面的示例中已经实现过了，在示例中，其实使用的是一个嵌套列表，如果要查询指定的值，需要对整个列表全部扫描。由此可见，分离链接法是在一个容器中用另外一种数据结构创建一系列的数据对象。

使用开放式寻址方法，如果某个索引下的容易中已有数据，则只要找到一个新的容器即可，所以要判断容器中是否已经有数据，并且要能找到新的容易。在原有的Hashtable类中修改_assign_buckets()方法，代码如下。

    def _assign_buckets(self, elements):
        self.buckets = [None] * self.bucket_size

        for key, value in elements:
            hashed_value = hash(key)
            index = hashed_value % self.bucket_size

            while self.buckets[index] is not None:
                print(f"The key {key} collided with {self.buckets[index]}")
                index = (index + 1) % self.bucket_size

            self.buckets[index] = ((key, value))

上面代码中，第2行，首先把大容器中设置了默认值None，然后在第8行用while循环，检查某索引的列表内是否已经存储了数据。

之后，还需要修改get_value方法，有必要检查索引对应的数据是否为None。

    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        while self.buckets[index] is not None:
            key,value = self.buckets[index]
            if key == input_key:
                return value
            index = (index + 1) % self.bucket_size

前面的示例中，“Italy”键与“France”键的散列值冲突，按照修改之后的方法，这两个键就不会存储到同一个容器（列表）中，而是将“Italy”为键的数据存储到下一个“桶”里面。

The key Italy collided with ('France', 'Paris')
[None,
 None,
 ('Canada', 'Ottawa'),
 None,
 ('France', 'Paris'),
 ('Italy', 'Rome'),
 None,
 ('United States', 'Washington D.C.')]
The capital of Italy is Rome

在开放式寻址法中，如果要删除散列表中的元素，只能执行逻辑删除，而不是物理删除。因为如果删除正好是发生了散列冲突的数据，那么与其对应的另外一个数据，就没办法找到了。

例如，前面在示例中，“Italy”与先前插入的元素（“France”）冲突，于是将它存储到索引值加一后的下一个“桶”里面，如果物理删除“France”元素，将无法找到“Italy”无法访问。

因此，在使用开放式寻址策略时，要删除元素，必须用一个哑值（dummy value，即虚拟数据）替换其存储区，这样解释器就可以根据冲突的这个位置检索到下一个位置。

字典：Python散列表的应用

现在，我们已经了解了哈希表的基本含义，下面来看一下它在Python语言中最重要的应用：字典。Python中的字典是使用散列表和“开放式寻址”冲突解决方法构建的。

在Python的基本知识中，我们知道字典是“键-值对”的集合

^{[3]}

，因此要定义字典，必须提供一个用逗号括起来的大括号内的键-值对列表，如以下示例所示：

>>> chess_players = {
...    "Carlsen": 2863,
...    "Caruana": 2835,
...    "Ding": 2791,
...    "Nepomniachtchi": 2784,
...    "Vachier-Lagrave": 2778,
... }

这里所创建的字典chess_players中包括五个键值对：世界排名前五的国际象棋棋手名称及其得分。

要检索特定值，只需要使用方括号指定键即可：

>>> chess_players["Nepomniachtchi"]
2784

If you try to access a non existing element, the Python interpreter throws a Key Error exception:

如果访问不存在的元素，Python解释器将抛出Key Error异常：

>>> chess_players["Mastromatteo"]
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
KeyError: 'Mastromatteo'

字典内的元素，可以用.items()方法生成可迭代对象：

>>> for (k, v) in chess_players.items():
...     print(k,v)
... 
Carlsen 2863
Caruana 2835
Ding 2791
Nepomniachtchi 2784
Vachier-Lagrave 2778

另外，如果使用字典的.keys()和.values()两个方法，可以分别得到字典的键和值所生成的对象（在参考文献[3]中，对这类对象有特别说明），也是可迭代的。

>>> chess_players.keys()
dict_keys(["Carlsen", "Caruana", "Ding", "Nepomniachtchi", "Vachier-Lagrave"])
>>> chess_players.values()
dict_values([2863, 2835, 2791, 2784, 2778])

字典是可变对象，可以增加键值对。

>>> chess_players["Grischuk"] = 2777
>>> chess_players
{'Carlsen': 2863, 'Caruana': 2835, 'Ding': 2791, 'Nepomniachtchi': 2784, 'Vachier-Lagrave': 2778, 'Grischuk': 2777}

注意，字典中键值对的键，必须是可散列对象，因为字典是基于散列表而创建的。如果键不是可散列的，Python会爆出TypeError异常。

>>> my_list = ["Giri", "Mamedyarov"]
chess_players[my_list] = 2764
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

如果要删除字典的键值对，可以使用del语句，注意，这不是函数。

>>> del chess_players["Grischuk"]
>>> chess_players
{'Carlsen': 2863, 'Caruana': 2835, 'Ding': 2791, 'Nepomniachtchi': 2784, 'Vachier-Lagrave': 2778}

删除元素的语句，并不不会执行物理删除，它只是将语句中的“键”替换为虚拟值，这就是前面提到的开放寻址法所起的作用。但是，在实际操作总，由于解释器会为处理所有这些复杂问题，我们不用去关心，给我们的感觉就是“删除”了那个指定的键值对。

探寻所以然

字典是散列表，那么它在后台是如何运行的？下面就在前面“知其然”基础上，了解一些“所以然”的内容。

特别提醒，此处我们的所有讨论，都是基于Python的最新版本，因为Python 3.6开始，字典已经发生了很大变化，并且变得更小，更快，甚至功能更强大，因为它现在已经能够实现“插入排序”了

^{[6]}

。

下面创建一个空字典，并检查它的大小，会发现这个空字典占据了240bytes的内存。

>>> import sys
>>> my_dict = {}
>>> sys.getsizeof(my_dict)
240

空字典占据240bytes的内存，但是，如果增加了数据，会发现，它所占内存并没有变化。

>>> my_dict["a"] = 100
>>> sys.getsizeof(my_dict)
240

这是为什么呢？因为从Python 3.6开始，字典中值存储在不同的数据结构中，而字典仅包含指向实际值存储位置的指针。此外，当创建一个空字典时，它同时创建一个Python散列表，其中包含8个存储容器，长度只有240个字节，因此字典中增加了第一个元素后，根本没有改变其大小。

下面尝试增加更多的元素，会发现字典所占内存空间（即字典大小）在增长。

>>> for i in range(20):
...     my_dict[i] = 100
...     print(f"elements = {i+1} size = {sys.getsizeof(my_dict)}")
... 
elements = 1 size = 240
elements = 2 size = 240
elements = 3 size = 240
elements = 4 size = 240
elements = 5 size = 240
elements = 6 size = 368
elements = 7 size = 368
elements = 8 size = 368
elements = 9 size = 368
elements = 10 size = 368
elements = 11 size = 648
elements = 12 size = 648
elements = 13 size = 648
elements = 14 size = 648
elements = 15 size = 648
elements = 16 size = 648
elements = 17 size = 648
elements = 18 size = 648
elements = 19 size = 648
elements = 20 size = 648

如上运行结果所示，在插入第六个元素（第10行）和第十一元素（第15行）之后，字典变大了，并非连续变大。这又是什么原因呢？这是为了使Python散列表更快并减少冲突，所以当字典充满三分之二时，解释器会调整字典的大小

^{[7]}

。

现在，将上面所创建字典中的元素都删除了，再看一看该字典的大小。

>>> keys = list(my_dict.keys())
>>> for key in keys:
...     del my_dict[key]
...
>>> my_dict
{}
>>> sys.getsizeof(my_dict)
648

与没有删除前比较，发现居然大小没变。之所以如此，就是由于字典的内存占用非常小，并且在使用字典时删除操作并不频繁，因此与每次删除后动态调整字典大小，解释器更愿意浪费一点空间。但是，如果通过调用.clear()方法清空字典，由于它是批量删除，因此释放了空间，并且最小达到72个字节。

>>> my_dict.clear()
>>> sys.getsizeof(my_dict)
72

结论

本文主要介绍了Python散列表及其在字典对象类型中的具体应用，从而更深入了解了字典的特点。

这篇文章的内容重点参考了Raymond Hettinger在2017年Pycon大会上的演讲

^{[8]}

，Raymond Hettinger 是Python的核心开发者，为Python的发展做出了重大贡献。

参考文献

[1]. http://thepythoncorner.com/dev/hash-tables-understanding-dictionaries/

[2]. https://www.ruanyifeng.com/blog/2011/08/what_is_a_digital_signature.html

[3]. Python大学实用教程. 齐伟. 北京：电子工业出版社

[4]. https://docs.python.org/3.3/using/cmdline.html#envvar-PYTHONHASHSEED

[5]. https://stackoverflow.com/questions/30585108/disable-hash-randomization-from-within-python-program

[6]. “插入顺序”在Python 3.6中实现，被Guido在Python 3.7中正式认可：https://mail.python.org/pipermail/python-dev/2017-December/151283.html

[7]. https://mail.python.org/pipermail/python-list/2000-March/048085.html

[8]. https://pyvideo.org/pycon-us-2017/modern-python-dictionaries-a-confluence-of-a-dozen-great-ideas.html

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-22，如有侵权请联系 cloudcommunity@tencent.com 删除

容器

本文分享自老齐教室微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度