我们如何编写一个函数 'f' 来返回一个整数，使得 'f(x) == f(y)' 当且仅当 'x' 和 'y' 相同?

Question

要求

我们可以编写一个函数f它：

• 将单个参数作为输入。
• 返回一个整数
• 具有当且仅当x与y完全相同或x是y的副本时f(x) == f(y)的属性。

我们说">x与y完全相同"或x是y的副本"，如果至少满足以下条件之一：

1. id(x) == id(y)返回True
2. repr(x) == repr(y)返回True
3. x is y返回True
4. y is x返回True
5. x == copy.deepcopy(y)返回True
6. y == copy.deepcopy(x)返回True

我意识到我们的函数f永远不会万无一失，但请假设没有人会用一个非常奇怪的__eq__方法来定义一个新类。

还假设没有对手会用真正奇怪的__copy__方法或某种病态__deepcopy__()来定义一个新类。

定义f的一次尝试

我定义函数f的微弱尝试如下所示：

pi = lambda k_1, k_2: (1/2)*(k_1 + k_2)(k_1 + k_2 + 1)+k_2
def f(x:object) -> int:
"""
Based on something called "Cantor's pairing function"
from the field of mathematics. 
"""   
k_1 = hash(x)
k_2 = hash(type(x))
if k_1 < 0 or k_2 < 0:
raise NotImplementedError()
return pi(k_1, k_2)

我的解决方案中的缺陷

存在一些问题：

• 我担心两个不同的对象将具有相同的哈希值。例如，也许hash([1, 2]) == hash([2, 3]).两个列表[1, 2]和[2, 3]不同，但可能具有不同的哈希值。如果我错了，请随时纠正我。
• 我的解决方案仅在hash()返回非负整数时才有效。

id(x) == id(y)与x == y

x == y按x.__eq__(y)实现

请注意，对象的id通常与该对象副本的id不同。通常，对象和对象的副本通常驻留在不同的内存地址。

以下代码演示了__eq__()和id()之间的区别：

x = [1, 2, 3]
y = [1, 2, 3]
print("id(x)".ljust(15), id(x))
print("id(y)".ljust(15), id(y))
print("x is x".ljust(15), x is x)
print("x is y".ljust(15), x is y)
print("x == x".ljust(15), x == x)
print("x == y".ljust(15), x == y)

我们有：

id(x)           2531180442688
id(y)           2531180443264
x is x          True
x is y          False
x == x          True
x == y          True

有点担心，但不要太担心定制__repr__或__eq__

我意识到我们的函数f永远不会万无一失，但请假设没有人会用非常奇怪的__eq__、__hash__方法或__eq__方法来定义一个新类。

例如，有人可以(理论上)定义以下内容：

import random
class NoNoNo:
def __init__(self, *args):
self.myVal = random.randint(1, 9)
def __eq__(self, other):
return False
def __repr__(self):
return "$"

从NoNoNo类实例化的对象永远不会彼此相等。

import copy
x = NoNoNo()
y = copy.deepcopy(x)
print("x == y?", "Yes" if x == y else "No") # prints "x == y? No"   

此外，repr(x)始终与repr(y)相同

import copy
x = NoNoNo()
y = NoNoNo() # `y` IS VERY DIFFERENT FROM `x`
print("repr(x) == repr(y)?", "Yes" if repr(x) == repr(y) else "No") # prints "repr(x) == repr(y)? Yes"   

Answer 1

如果我正确理解了你的问题，这意味着最弱的条件是条件 [2]，这就是我们在实现函数时想要瞄准的条件。(我希望条件不是错误添加的)。

以下函数有意义吗？

def f(x):
return functools.reduce(lambda x,y: x *256 + y, repr(x).encode('latin1'))

Answer 2

我将仅限于repr(x) == repr(y)的情况。这涵盖了除深拷贝基础之外的所有内容，假设repr是确定性的。然后它基本上归结为以独特的方式将字符串压缩为单个整数。这(嗯，它是相反的)被称为通用代码。

一种方法是获取字符串并将其转换为字节。记下字符串的长度l。检查表示l需要多少位。然后，输出那么多1位，后跟一个0。然后l本身以二进制编码，最后是字节，比如说，小端编码。

def encode(s):
bytes = s.encode("utf-8")
l = len(s)
b = l.bit_length()
ones = (1 << b) - 1
lshift = l << (b + 1)
bytesshift = (int.from_bytes(bytes, "little") << (2*b + 1))
return ones | lshift | bytesshift
def decode(n):
b = 0
while n % 2:
b += 1
n >>= 1
n >>= 1
l = n & ((1 << b) - 1)
n >>= b
return n.to_bytes(l, "little").decode("utf-8")

Answer 3

我认为这在实现上是不可行的。对于任意类型，任何类型的配对函数都会导致大量的整数来表示除最简单的结构之外的所有内容。

理想情况下，您必须将数据类型和数据配对在一起才能获得唯一的整数。数据需要转换为所有可能的数据输入集合所特有的整数，实际上，该整数会变得非常大，非常快。与数据类型整数表示配对，大多数时候您最终会得到一个巨大的数字。

如果要处理负哈希值，可以查看使用有符号康托尔配对函数。但是，您仍然会有哈希冲突。

我能看到的最好的方法是否只是将数据结构的哈希与数据本身连接起来，但您也可以保持对象原样。这也可能导致数据类型之间的哈希冲突，但除非您使用大量类型，否则不太可能。您也可以使用完美的哈希，但必须事先定义允许的数据类型集。