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

10 浏览
0 Comments

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

基本上，我“理解”使用其他容器作为键的模糊性。-你是比较引用还是比较其中的值（以及深度是多少）。

那么，你能专门定义一个列表并创建自定义的比较/哈希操作符吗？我知道在我的应用程序中，我希望通过字符串的值（当然还有相对顺序）来比较字符串列表。

那么，我应该如何为这些类型的列表编写自定义哈希函数？或者换一种方式，我如何将列表转换为字符串，而不会引入分隔符的模糊性（该分隔符可能是字符串的一部分）！

关于这个问题：https://wiki.python.org/moin/DictionaryKeys

在那里直接说列表不能被用作字典的键；

也就是说，列表不能用作字典键的简单答案是，列表没有提供有效的哈希方法。当然，最明显的问题是，“为什么不能呢？”

因此，我写这篇文章来询问是否有办法使列表可哈希化；以及如何编写令人满意的哈希方法。

作为为什么我希望这样做的示例，请参见下面的代码：

namelist = sorted(["Jan", "Frank", "Kim"])
commonTrait = newTraits()
traitdict = {}
traitdict[namelist] = commonTrait;
//稍后我希望检索它：
trait = traitdict[sorted(["Jan", "Frank", "Kim"])]

在我直接使用的这个例子中，我考虑到列表的“排序”实际上并不重要（排序只是上述代码中进行的操作，以确保如果它们包含相同的内容，列表将始终相等）。

0

1 答案

0 Comments

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

如果需要使用一个字符串的集合作为字典的键，有两个明显的选择：如果顺序重要，使用元组：

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

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

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

如果计数重要但顺序不重要，使用排序后的元组：

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

与Perl的哈希表或JavaScript的对象属性不同，您不需要在Python中将字典键转换为字符串。

现在，关于可变列表不可哈希的问题：Python字典实现使用哈希表结构。它明确要求并假设键满足以下条件：

- 键实现了返回整数的__hash__方法

- 整数应该在输出范围内尽可能广泛分布，并均匀映射

- __hash__方法对于相同的对象返回一个不变的数值

- a == b意味着a.__hash__() == b.__hash__()

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

>>> [].__hash__()
Traceback (most recent call last):
  File "", line 1, in 
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 "", line 1, in 
AttributeError: 'list' object attribute '__hash__' is read-only

当然，我们总是可以看看如果列表具有__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 "", line 1, in 
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()中可见。

0