当比较内存对于管道状态之类的东西更好时，为什么我们使用哈希？

Question

当人们使用 Vulkan 等图形 API 制作渲染器时，常见的做法是对管道对象状态进行哈希处理，以便重用已创建的渲染器，而不是在已经存在相同的渲染器时不必要地创建新的渲染器。散列虽然理想地应该为不同的字节/数据数组产生不同的值，但不能保证不发生冲突，因此两个不同的字节集可以产生相同的散列值。直接比较两个字节数组不会在确保数据相同方面出现误报。当将数据从一个位置发送到另一个位置时（例如通过互联网），无法与原始/源数据进行比较，因为您没有它，但是在创建渲染器并比较两个管道状态时，您确实拥有两组数据，那么为什么不进行内存比较而不是散列更好呢？

Answer 1

主要优化是找到匹配的管道，而不是单个内存比较的成本。

如果您依赖线性内存比较，那么您需要搜索可用管道的整个列表，以找到与当前状态匹配的管道。这是一个

O(num_of_pipelines)

列表搜索，每次比较都有

O(sizeof_pipeline)

内存比较。所以总复杂度是

O(num_pipelines) * O(sizeof_pipeline)

。

使用哈希映射，您需要支付

O(sizeof_pipeline)

成本来生成初始哈希，但是使用良好的哈希和哈希映射数据结构，您应该接近

O(1)

查找（如果您有良好的哈希函数和足够的根箱） ）。因此，成本是一次哈希生成和一次比较，除非发生冲突，所以“大 O”成本是

O(sizeof_pipeline)

。

鉴于游戏的状态和着色器数量是有限的，通常也可以证明您的游戏内容集不会发生冲突，因此您甚至可以在大多数情况下避免实际的逐字节比较.

Answer 2

虽然直接内存比较可以为您提供精确匹配，但使用散列有很多优点，如下所示。

• 与散列相比，逐字节比较效率低下。这是因为哈希函数能够以更快的速度处理数据并产生相对较小的输出，而与输入的大小无关。
• 哈希时使用的存储较少，因为只需要存储哈希值而不是整个数据集，从而节省大量内存。这在处理大型数据集时尤其重要。
• 查找时间显着加快。