hash - 散列是比较两个 32x64 二维数组的好方法吗？

Question

我正在尝试在嵌入式设备上实现康威的生命游戏。我只有 1kb 的 RAM 可以玩，总共有 2048 个单元，等于 512 字节。我将一次计算下一代 8x8 单元，这样我就不必在任何时候将两代存储在 RAM 中。

但是，我还想做的是检测 GoL 何时陷入循环/静态状态。当我在 PC 上创建模型时，我只是存储了最后的第 10 代和第 100 代，并将当前代与它进行比较。我不能用 1kb 的 RAM 做到这一点，我想做的只是计算最后 x 代的哈希并将其与当前一代的哈希进行比较。

XTEA 或 SHA1 有一些非常简单的实现，但我不确定散列是否真的适合这个目的，因为我需要确定两代中的每个单独的单元格是否相等。你会推荐什么？

谢谢，

乔

编辑：只是想，我实际上可以计算匹配的数量，如果它达到某个阈值，然后假设它处于循环中，这对于每千代左右重复的模式来说效果不佳。

Answer 1

我认为这是一个相当不错的选择。哈希冲突的概率非常低，因此它可以作为您的应用程序接受，它不是核反应堆。

Answer 2

我决定只买一个具有更多 RAM 的设备，但我观察到的一件事是，如果有一个模式，那么每 x 代都会匹配相同的模式，而如果它只是随机哈希冲突，那么它不会。因此，如果我们有以下几代人：

123*
231
312
123*
231
312
123*

每 3 代匹配 123 个。哈希冲突不会发生这种情况。

其他答案是正确且有价值的，但这是唯一可以解决问题的答案。我不确定回答您自己的问题时的礼仪是什么，所以如果我不应该将此标记为答案，那么请不要投反对票，只需给我发消息，我会重新分配正确的答案。

谢谢，

乔

Answer 3

散列可以很好地判断事物何时不相等。如果哈希值相等，那么您仍然需要（应该）进行单独比较。