我刚刚在 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__ 中的更改引起的。)
请您参考如下方法:
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>
