依赖Python哈希函数存在碰撞风险吗？

Question

在我的程序中，我需要存储与许多（数十万、百万）游戏板状态相关的数据。为此，我使用一个字典。

class BoardState(object):
    def __init__(self, ...):
        # ...
        self.board = [ [ None ] * self.cols for _ in xrange(self.rows) ]

    def __hash__(self):
        board_tuple = tuple([ tuple(row) for row in self.board ])
        return hash(board_tuple)

    # ...

self.board是一个二维列表，在我的主要用例中，有6行7列。

一开始我使用BoardState对象对dict进行索引。但是由于我不会将存储在dict中的BoardState对象用于未来的查找之外的其他目的，因此我注意到可以通过使用hash(board_state)进行索引来节省内存（这个版本使用的内存少了4倍）。

两个不同的BoardState对象（内部具有不同的board）在hash后产生相同值的概率是多少？

为了澄清一下，这是我如何从dict中存储和检索值的：

board_state = BoardState(...)
my_values[hash(board_state)] = { ... }
...
other_val_with_board_state = source_function()
retrieved = my_values[hash(other_val_with_board_state)]

如我之前提到的，我使用hash()返回值作为索引来节省内存，因为我后面不会使用BoardState对象。

---

更新：现在我在考虑是否使用board_state.board的字符串表示作为索引是解决我的问题的好方法。

- Luke

---

现在我明白你想做什么了...很难说，可能会发生碰撞。如果你想要更安全，应该在hashlib中使用更高级的哈希算法。或者定义自己的哈希算法，以确保与棋盘配置相关的唯一结果。 - Simone Zandara

相关帖子 https://dev59.com/fmox5IYBdhLWcg3wtmrh#9010557 - Reti43

@Reti43 是的，有点麻烦。但我不想浪费内存空间来存储仅用于其 eq 方法的对象。 - Luke

你也可以直接使用元组的元组（board_tuple）作为字典键，而不是它的哈希值。如果唯一有趣的部分是board_tuple，则无需创建新类。 - Rob

@Rob Board 列表/元组是状态的关键，但还有像行和列这样的辅助变量，以及对状态进行操作的方法。是的，我也可以使用那个元组作为索引，但字符串可能会占用更少的内存空间。 - Luke

Answer 1

简短回答：使用hashlib代替。

---

如果你的程序无法处理碰撞或者想要保存哈希值或使用多进程，就不应该依赖于hash。

Python哈希函数将映射数据转换为64位（int范围内）的数据。对哈希的最基本分析是将其视为生日问题。关于此有一个很好的SO答案和一个详细的维基页面。典型的引用语是“如果元素少于数十亿个，则无需担心”。然而，这是非常简单化的观点。

作为一个轶事：我最近对由人手工创建的8.7e6个短字符串运行了hash。64位哈希的碰撞数的数学期望是4e-6。但我得到了32个。有趣的是：hash(chr(9786)) == hash(chr(58)+chr(38))（'☺'与':&'相冲突）（截至Python3.8.10）。

来自hashlib的加密函数对于碰撞更加抵抗。像hashlib.sha256(pickle.dumps(my_obj,1))这样的东西甚至可能比转换为元组更快。

---

如果内存使用是哈希的原因，首先应该考虑在一开始用更少的字节表示数据。指定__slots__和减少嵌套对象的数量是首要考虑的事情。然而，对于小型对象，由于每个Python对象所需的脚手架数量，这将是一场艰苦的战斗。

以国际象棋为例，完整状态可以用24字节或更舒适地用32字节（64个单元格中的每个都需要4位来表示其内容）存储。我们在Python中能得到的最好结果是使用bytes，它将占用65位（33字节的服务信息），并需要额外的操作将两个4位块推入一个单独的字节中。另一个选择可能是bitarray.frozenbitarray，它需要112字节来存储相同数量的有用信息（80字节的信息）。但是，它仍然比元组中的元组要好，其中每个元组需要40字节的脚手架。

- Dimitry

Answer 2

虽然我不确定在哈希后获得相同值的机会有多大，但可能是可能的，并且可能会引起问题。

话虽如此，如果您不使用存储在字典中的BoardState对象以外的任何目的，那么您是否可以向BoardState类添加一个id属性，在__init__上生成唯一的（即设置为全局计数器，每创建一个新的BoardState对象就增加1）？然后，您可以将id用作字典的键进行未来查找，避免任何潜在的冲突问题。

- kdawg

---

我不能这样做，因为未来可能会创建相同的BoardState，但不会具有相同的id。 - Luke

如果具有相同配置的2个BoardState对象是相同的，为什么您会担心碰撞？我不太理解您的用例。 - Simone Zandara

@xbirkettx 我在询问两个不同的6x7的棋盘（2D列表/元组）是否可能具有相同的哈希值。顺便说一句，如果你没有在评论中提到我的名字，我就不会收到通知，因为这不是我的回答。 - Luke

@Luke，你已经重新定义了你的哈希表，但是你还在使用字典进行查找吗？如果是这样，你就不必担心碰撞问题。 - Simone Zandara

@xbirkettx 但我是通过哈希查找的。因此，这两个状态的值将在它们之间共享。 - Luke

Answer 3

为了了解碰撞的风险，我们需要查看哈希函数的实现。主要思想是从一个空间开始，假设为A（变量board_tuple可能采用的所有形式），通过哈希函数H到达另一个空间B（哈希函数的结果）。

碰撞的风险来自两个方面：

1. 空间的大小：如果您有2个`board_tuple`可能性，而B的大小为10⁶，则很少会发生碰撞。另一方面，如果您可以有1000个`board_tuple`，并且H导致B的空间为16，则几乎肯定会发生碰撞。 2. 哈希函数本身。如果哈希函数是h(x) = 2，则总会发生碰撞。

但是不要太担心，哈希函数都是精心制作的，我几乎可以确定它们正在使用一些经典策略来智能地处理碰撞：

1. 重新运行哈希函数，直到没有碰撞为止。 2. 将作为相同哈希结果的元素数组存储，而不是发生碰撞。

- MathiasDesch

---

很抱歉，您并没有回答问题。您只是描述了一些关于哈希的事实，然后得出结论，我们应该查看Python的哈希实现来确定碰撞可能发生的频率和方式。这正是问题所询问的内容。此答案及其中的链接更详细地介绍了具体情况。 - Reti43