散列的 unordered_map

Question

从某些来源^，我得到了一个长度为 20 (SHA-1) 的哈希缓冲区，用于特定数据（比如文件或字节块）。如果给定的哈希值（将其视为字符串，而不是哈希）是没有在地图中找到，那么我会拉更多的信息，然后将这个散列这一信息。要说清楚：

• unordered_map<Hash_of_20_Bytes, Information>

这是我的地图。键是一个 20 字节的缓冲区，Information是一些包含详细信息的结构。因此，如果源 ^给了我一些散列，我会在此信息映射中查找该散列并适当地使用/生成。

关键是，就我而言，给定的 20 字节散列保证没有任何冲突。但是，unordered_map仍会计算密钥的 (FNV) 哈希值（密钥本身就是哈希值！）。我不能指示集合类不要生成散列，而是使用具有唯一键本身的键（以确保 O(1)）？

我不确定是否也unordered_map计算整数的散列（即减少额外计算的需要）。

一种方法是使用pair<20-byte, Info>自身的向量，并进行二分搜索。然而，只是为了避免哈希计算的惩罚（通过哈希容器），它会导致保持向量排序的更多惩罚）。

Answer 1

散列器std::unordered_map必须满足散列概念。所以它必须返回 a std::size_t，这极不可能超过 20 个字节。

因此，不可能为这个 20 字节散列提供身份散列器，因此即使保证 20 字节散列没有冲突，除非它可以可靠地减少到 32 位空间（或者更确切地说是一个sizeof(std::size_t)空间）在没有碰撞的情况下，这种情况和这个容器的碰撞将是不可避免的。