6

正如标题所暗示的，我有一个关于更改集合中的对象以使它们变得完全相同的问题（在集合的眼中）。只是好奇。

我问这个关于 Python 的问题，但如果它是可推广的，请随意这样做。

如果我在 Python 中理解正确，则Set可迭代对象将通过使对象的哈希相等来确定对象是否“相等”。所以对于对象a和b这将是：

hash(a) == hash(b)

对于您制作的任何对象，您都可以根据自己的喜好覆盖标准哈希函数, 。__hash__

假设您创建了一个散列函数，它接受对象中的几个或所有对象，并使用散列的组合作为自己的（例如，通过对它们进行 ORing）。

现在，如果您在单个 Set 中有几个最初不同的对象，然后遍历该 Set 并更改其中的对象以使其内部对象匹配，那么 Set 会发生什么？他们会全部留在那里，还是会被踢出，还是我们需要等到对 Set 执行操作？还是我们在某个地方提出了一些错误？

4

4 回答 4

6

考虑这个测试：

class A:
    def __init__(self, h):
        self.h = h

    def __hash__(self):
        return self.h

x = A(1)
y = A(2)

a = {x, y}

print x in a, y in a
print a

print "----"

x.h = 2

print x in a, y in a
print a

结果：

True True
set([<__main__.A instance at 0x10d94fd40>, <__main__.A instance at 0x10d94fd88>])
----
False True
set([<__main__.A instance at 0x10d94fd40>, <__main__.A instance at 0x10d94fd88>])

如您所见，第一个对象x仍然存在，但in操作员报告它不存在。为什么会这样？

据我了解，Set 对象是使用哈希表实现的，而哈希表通常具有如下结构：

 hash_value => list of objects with this hash value
 another_hash_value => list of objects with this hash value

当一个 Setin响应请求时，它首先计算参数的哈希值，然后尝试在相应的列表中找到它。我们的集合a最初是这样的：

  1 => [x]
  2 => [y]

现在，我们更改x的哈希并询问集合是否存在对象。该集合计算哈希值（现在是2）尝试x在第二个列表中定位并失败 - 因此False。

为了让事情更有趣，让我们做

a.add(x)
print x in a, y in a
print a

结果：

True True
set([<__main__.A instance at 0x107cbfd40>, 
     <__main__.A instance at 0x107cbfd88>, 
     <__main__.A instance at 0x107cbfd40>])

现在我们在集合中有两次相同的对象！如您所见，没有自动调整，也没有错误。Python 是一种成年人的语言，它总是假设你知道自己在做什么。

于 2013-11-13T12:13:28.223 回答
5

不允许以更改其哈希值的方式修改集合的成员。

在 Python 中，您只能将可散列对象存储在集合中。从文档（强调我的）：

如果一个对象的哈希值在其生命周期内永远不会改变（它需要一个__hash__()方法），并且可以与其他对象进行比较（它需要一个__eq__()or__cmp__()方法），那么它就是可哈希的。比较相等的可散列对象必须具有相同的散列值。

哈希性使对象可用作字典键和集合成员，因为这些数据结构在内部使用哈希值。

Python 的所有不可变内置对象都是可散列的，而没有可变容器（例如列表或字典）是可散列的。默认情况下，作为用户定义类实例的对象是可散列的；它们都比较不相等（除了它们自己），它们的哈希值是它们的id().

如果您违反此合同（正如您在问题中提出的那样），该系列将无法完成其工作，并且所有赌注都将取消。

修改集合成员的正确方法是删除、更改和重新添加。这将像您期望的那样运行。

[集合] 将通过相等的哈希值来确定对象是否“相等”

这不太正确。比较散列不能用于确定对象是否相等。它只能用于确定对象不相等。这是一个微妙但重要的区别。

于 2013-11-13T12:07:21.227 回答
2

首先，set需要的元素是hashable：

集合的元素必须是可散列的。

虽然hashable意味着：

如果一个对象的哈希值在其生命周期内永远不会改变，那么它就是可哈希的 [...]

因此，只要您不以使其哈希值（其__hash__方法的结果）保持不变的方式更改对象，一切都很好。

在 Python 中，不可变对象被认为是可散列的，而可变对象则不是：

Python 的所有不可变内置对象都是可散列的，而没有可变容器（例如列表或字典）是可散列的。

于 2013-11-13T12:07:28.087 回答
0

将散列或运算组合在一起会产生一个特别糟糕的散列函数，因为您会倾向于设置更多位的值。尽管如此，集合和字典还是使用哈希表作为哈希表。预计会发生冲突，并且对具有相同哈希值的对象执行更深入的比较。但是，如果哈希函数不好，您确实会失去哈希表的优势 - O(1) 查找。

同样正如其他答案所涵盖的，集合应该只包含不可变的值。将对象插入集合后更改其哈希值会破坏集合类型的条件，并且检查对象是否在集合中，甚至从集合中删除对象等操作都会失败。但是，我希望您仍然可以通过遍历集合来找到它。

于 2013-11-13T12:13:59.560 回答