如何使用包含任意字符的字符串列表作为键？

Question

基本上，我“理解”使用其他容器作为键时的模糊性——你是比较引用还是比较里面的值（还有比较多深度）。

那么，难道你不能专门为列表定制一个比较/hash操作符吗？因为在我的应用中，我希望通过字符串的值来比较字符串列表（当然还有相对的顺序）。

那么，我该如何为这种列表编写一个自定义的哈希呢？换句话说，我该如何将列表转换为字符串，而不引入模糊性（因为分隔符可能是字符串的一部分）？

关于这个问题：https://wiki.python.org/moin/DictionaryKeys
那里直接说了列表不能用作字典的键；

简单来说，列表不能用作字典键的原因是，列表没有提供有效的哈希方法。当然，显而易见的问题是，“为什么不呢？”

所以我写这个是想问有没有办法让列表变得可哈希；以及我该如何制作一个令人满意的哈希方法。

---

举个例子，看看下面的代码：

namelist = sorted(["Jan", "Frank", "Kim"])
commonTrait = newTraits()
traitdict = {}
traitdict[namelist] = commonTrait;

//later I wish to retrieve it:
trait = traitdict[sorted(["Jan", "Frank", "Kim"])]

在这个直接使用中，我心里想的“列表的顺序”其实并不重要（上面的代码只是为了确保如果列表内容相同，它们总是相等，所以进行了排序）。

Answer 1

如果你想用一组字符串作为字典的键，有两种明显的选择：如果顺序很重要，就用tuple：

>>> d[tuple(['foo', 'bar'])] = 'baz'
>>> d['foo', 'bar']
baz
>>> d['bar', 'foo']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: ('bar', 'foo')

如果顺序不重要，就用frozenset：

>>> d[frozenset(['foo', 'bar'])] = 'baz'
>>> d[frozenset(['bar', 'foo'])]
'baz'
>>> d[frozenset(['bar', 'foo', 'bar'])]
'baz'

如果数量重要但顺序不重要，可以用sorted和tuple：

>>> d[tuple(sorted(['foo', 'bar']))] = 'baz'
>>> d[tuple(sorted(['bar', 'foo']))]
'baz'
>>> d[tuple(sorted(['bar', 'foo', 'bar']))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: ('bar', 'bar', 'foo')

和 Perl 的哈希表或 JavaScript 的对象属性不同，在 Python 中你不需要把字典的键转换成字符串。

---

关于可变的list不能作为哈希键的问题：Python 的字典是用哈希表结构实现的。它对键有一些具体的要求和假设：

1. 键需要实现一个__hash__方法，这个方法返回一个整数
2. 这些整数的输出范围应该尽可能广泛且均匀分布。
3. 同一个对象的__hash__方法返回的数字不能改变
4. a == b意味着a.__hash__() == b.__hash__()

列表不能用作字典的键，因为：

>>> [].__hash__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'NoneType' object is not callable

list类无法提供一个__hash__方法，来同时满足所有这些要求，特别是a == b需要意味着a.__hash__() == b.__hash__()。

（它*可以提供一个实现，让每个列表都返回0，这样在某种情况下是可以工作的，但这就完全否定了哈希的使用，因为所有列表都会被映射到字典的同一个位置，哈希代码会违反第二条规则）。

而且也无法为列表创建一个__hash__方法：

>>> [].__hash__ = lambda x: 0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object attribute '__hash__' is read-only

---

当然，我们可以看看如果list有__hash__方法会发生什么——我们可以创建一个列表的子类，并在其中提供__hash__；哈希代码的明显实现就是tuple()：

>>> class hashablelist(list):
...     def __hash__(self):
...         return hash(tuple(self))
... 
>>> x = hashablelist(['a', 'b', 'c'])
>>> y = hashablelist(['a', 'b', 'd'])
>>> d = {}
>>> d[x] = 'foo'
>>> d[y] = 'bar'
>>> d.items()
[(['a', 'b', 'c'], 'foo'), (['a', 'b', 'd'], 'bar')]
>>> y[2] = 'c'
>>> d.items()
[(['a', 'b', 'c'], 'foo'), (['a', 'b', 'c'], 'bar')]
>>> del d[x]
>>> del d[y]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: ['a', 'b', 'c']
>>> d.items()
[(['a', 'b', 'c'], 'bar')]
>>> x in d
False
>>> y in d
False
>>> x in d.keys()
True
>>> y in d.keys()
True

代码显示，我们最终得到了一个损坏的字典——即使在.keys()、.values()和.items()中可以看到['a', 'b', 'c'] -> 'bar'这个键值对，但我们无法直接通过键访问或删除它。