根据 __hash__ 设置更改隐式顺序？
Set changes implicit order based on __hash__?
我刚刚在 Python3 中观察到 Set 的一个有趣行为，我想知道为什么。
鉴于 class:
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, when the static set method is unchanged, creating each element in the set from 1 through 9, just as before?
此方法未更改，但使用 Tab 个对象调用内置 set。
而且由于 __hash__ 方法已经改变，set 可能会改变你不应该依赖的内部顺序。
在你的情况下，打印时排序是可行的：
"|%s|" % "|".join([str(tab) for tab in sorted(self.tabs,lambda t:(t.label, t.up)])
或者不用 lambda，定义一个 __lt__ 方法，这样 sort 就可以比较对象
why did the implicit ordering change
因为 set 在 CPython 中实现为 hashtable。所以：
- 项目存储在
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 的实际实现细节感兴趣，可以使用我在 :
中为 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>
我刚刚在 Python3 中观察到 Set 的一个有趣行为，我想知道为什么。
鉴于 class:
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, when the static
setmethod is unchanged, creating each element in the set from 1 through 9, just as before?
此方法未更改，但使用 Tab 个对象调用内置 set。
而且由于 __hash__ 方法已经改变，set 可能会改变你不应该依赖的内部顺序。
在你的情况下，打印时排序是可行的：
"|%s|" % "|".join([str(tab) for tab in sorted(self.tabs,lambda t:(t.label, t.up)])
或者不用 lambda，定义一个 __lt__ 方法，这样 sort 就可以比较对象
why did the implicit ordering change
因为 set 在 CPython 中实现为 hashtable。所以：
- 项目存储在
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 的实际实现细节感兴趣，可以使用我在
%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>