python - 基于 __hash__ 设置更改隐式顺序？

Question

我刚刚在 Python3 中观察到 Set 的一个有趣行为，我想知道为什么。

给定类:

class Tab:

    @staticmethod
    def set(size):
        return set(map(lambda label: Tab(label), range(1, size + 1)));

    def __init__(self, label):
        self.label = label
        self.up = True

    def __eq__(self, other):
        if not isinstance(other, Tab):
            return NotImplemented
        return self.label == other.label

    def __hash__(self):
        return hash(self.label)

    def __str__(self):
        return str(self.label)

当我调用 Tab.set(9) 时，我得到一组选项卡，当通过以下方式表示为字符串时:

"|%s|" % "|".join([str(tab) for tab in self.tabs])

生成:

|1|2|3|4|5|6|7|8|9|

但是，如果我只修改 __eq__ 和 __hash__ 以合并 up 属性:

def __eq__(self, other):
    if not isinstance(other, Tab):
        return NotImplemented
    return self.label == other.label and self.up == other.up

def __hash__(self):
    return hash((self.label, self.up))

集合的隐式排序发生变化，字符串表示形式变为:

|9|8|7|6|5|4|3|2|1|

我知道集合没有顺序。但是，当静态 set 方法不变时，为什么隐式排序发生了变化，就像以前一样从 1 到 9 创建集合中的每个元素？

而且，我可以做些什么来保留隐式排序，以便我的集合看起来是有序的，就像以前一样？ (请注意，更改是由 __hash__ 而不是 __eq__ 中的更改引起的。)

Answer 1

why did the implicit ordering change

因为 set 被实现为 hashtable在 CPython 中。所以:

• set 中项目存储的位置取决于项目的(截断的)哈希值(并且在某种程度上扩展了插入顺序，因为该位置可能已被占用)。
• 项目的哈希值取决于 __hash__该项目的方法。

如果您遍历 set，您将逐个槽遍历哈希表(不包括丢失的条目)。因此，通过更改哈希，您可以更改顺序。

在你的例子中，哈希是不同的，因为你改变了 __hash__ 方法的实现，所以顺序是不同的:

>>> [hash(tab) for tab in Tab.set(9)]  # first code
[1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> [hash(tab) for tab in Tab.set(9)]  # second code
[3713072971709512581, 3713088127104978631, 3713071889183430056, 3713087044578896106, 3713083796991988331, 3713082714465905806, 3713085962048483481, 3713084879522400956, 3713081631935493181]

what might I do to preserve the implicit ordering so my set appears to be in order, just as before

如果您希望对它们进行排序，我的建议是不要使用set - 使用有序集合，仅举一个例子:list。也有高效的方法remove duplicates from a list and preserving the order .

但如果你想保留 set 并希望它们按 label 属性排序，你也可以使用 sorted:

sorted(tab.set(9), key=lambda t: t.label)

>>> [str(t) for t in sorted(Tab.set(9), key=lambda t: t.label)]
['1', '2', '3', '4', '5', '6', '7', '8', '9']

---

使用 Cython 检查 CPython 3.7.4 哈希表

注意:这是检查实现细节，可能会因版本而异。 Cython 代码甚至可能不适用于不同的 CPython 版本。 不要从字面上理解它们，也永远不要依赖它们。

如果您对 CPython 的实际实现细节感兴趣，可以使用我在 this answer to "Updating a set while iterating over its elements" 中为 Jupyter 编写的这个 Cython 助手:

%load_ext Cython
%%cython

from cpython cimport PyObject, PyTypeObject
cimport cython

cdef extern from "Python.h":
    ctypedef Py_ssize_t Py_hash_t

    struct setentry:
        PyObject *key
        Py_hash_t hash

    ctypedef struct PySetObject:
        Py_ssize_t ob_refcnt
        PyTypeObject *ob_type
        Py_ssize_t fill
        Py_ssize_t used
        Py_ssize_t mask
        setentry *table
        Py_hash_t hash
        Py_ssize_t finger

        setentry smalltable[8]
        PyObject *weakreflist

cpdef print_set_table(set inp):
    cdef PySetObject* innerset = <PySetObject *>inp
    for idx in range(innerset.mask+1):
        if (innerset.table[idx].key == NULL):
            print(idx, '<EMPTY>')
        else:
            print(idx, innerset.table[idx].hash, <object>innerset.table[idx].key)

这将打印内部哈希表，每一行包含槽号、哈希和存储的项目。

第一种情况:

>>> print_set_table(Tab.set(9))
0 <EMPTY>
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8
9 9 9
10 <EMPTY>
11 <EMPTY>
[...]
30 <EMPTY>
31 <EMPTY>

第二种情况:

>>> print_set_table(Tab.set(9))
0 <EMPTY>
[...]
4 <EMPTY>
5 3713072971709512581 9
6 <EMPTY>
7 3713088127104978631 7
8 3713071889183430056 8
9 <EMPTY>
10 3713087044578896106 6
11 3713083796991988331 3
12 <EMPTY>
13 <EMPTY>
14 3713082714465905806 2
15 <EMPTY>
[...]
24 <EMPTY>
25 3713085962048483481 5
26 <EMPTY>
27 <EMPTY>
28 3713084879522400956 4
29 3713081631935493181 1
30 <EMPTY>
31 <EMPTY>