依赖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在我的主要用例中，是一个 2D 列表，有 6 行和 7 列。

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

BoardState两个不同的对象（内部有不同的boards）在 ing 后产生相同值的可能性有多大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)]

（正如我之前提到的，我使用 result from 进行索引hash()以节省内存，因为我以后不再使用BoardState对象。）

---

更新现在我想知道使用board_state.board索引的字符串表示是否可以很好地解决我的问题。

Answer 1

简短的回答：使用hashlib代替。

\n\n

hash如果您的程序无法处理冲突或者您想要保存哈希值或使用多重处理，则不应依赖此方法。

\n

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

\n

作为一个轶事：我最近运行了hash人类8.7e6手动创建的独特的短字符串。64 位哈希的冲突次数的数学期望为4e-6。我得到了 32。有趣的事实：hash(chr(9786)) == hash(chr(58)+chr(38))(\'\xe2\x98\xba\' 与 \':&\' 冲突)（从 Python3.8.10 开始）。

\n

加密函数的抗hashlib冲突能力更强。类似的东西甚至可能比转换为元组更快。hashlib.sha256(pickle.dumps(my_obj,1))

\n\n

如果内存问题是散列的原因，那么首先应该考虑用较少的字节数来表示数据。__slots__首先想到的事情是指定和减少嵌套对象的数量。然而，对于小对象来说，这将是一场艰苦的战斗，因为每个 python 对象都需要大量的脚手架。

\n

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

\n