如何使用字符串列表[可能包含任何字符]作为键？

Question

基本上我"理解"使用其他容器作为键的歧义. - 您是比较参考还是比较其中的值(以及深度).

那你不能专门化一个列表并制作一个自定义比较/哈希运算符吗？正如我在我的应用程序中所知,我希望通过字符串的值(以及当然的相对顺序)来比较字符串列表.

那么我该如何为这些列表编写自定义哈希呢？或者换句话说 - 如何在不导致引入分隔符的情况下对字符串进行字符串化(分隔符可能是字符串的一部分)？

关于这个问题:https://wiki.python.org/moin/DictionaryKeys
在那里直接说不能使用列表;

也就是说,为什么列表不能用作字典键的简单答案是列表不提供有效的哈希方法.当然,显而易见的问题是,"为什么不呢？"

所以我写这个问题,如果有办法让列表可以清除; 以及如何制作一个令人满意的Hash方法.

---

作为我想要这个的原因的一个例子,请参阅下面的代码:

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

如果您需要使用字符串集合作为字典键,则有2个明显的选择:如果顺序很重要,请使用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中对字典键进行字符串化.

现在,关于mutable 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的实现,然后它会正常工作,但它会完全反驳哈希的使用,因为所有列表都将映射到字典中的相同插槽,因为哈希代码会打破规则2).

也无法__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__方法会发生什么- 我们创建一个list的子类并__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

代码显示我们只是设法得到一个破坏的字典 - 没有办法['a', 'b', 'c'] -> 'bar'直接通过密钥访问或删除该对,即使它是可见的.keys(),.values()和.items().