c - 16 位唯一键到 8 位数组索引（完美哈希）

Question

我有一组由 uint16_t 唯一标识的结构。这些结构永远不会超过 256 个（由于我不会进入的原因，必须使用 uint16_t 来识别结构）。

我想通过指针数组存储这些结构。由于不会有超过 256 个结构，我想静态分配一个大小为 256 的结构指针数组。不过，为此，我需要一个函数来将 uint16_t 唯一地映射到 uint8_t。

鉴于我将在运行时知道所有键（尽管在运行前我不会知道），是否存在一种算法，它通常会给我一个唯一的映射（即完美的哈希）？

需要注意的是，我使用的系统有 16 位地址。因此，出于效率原因，我不想使用任何大于 uint16_t 的类型。

标签： chashmapembeddedperfect-hash

Answer 1

鉴于我将在运行时知道所有键（尽管在运行前我不会知道），是否存在一种算法，它通常会给我一个唯一的映射（即完美的哈希）？

鉴于您要映射多达 256 个（16 位）值，原则上您可以使用许多映射。但是，如果要支持的键不相关，则任何计算映射的算法都需要所有 256 个键或它们的函数作为参数。例如，在评论中，讨论了 256^次多项式的概念，参数将是多项式的系数。

现在考虑由于映射需要 256 个参数，它也会以某种方式使用所有这些参数。那么，如何才能有效地计算具有这些一般特征的东西呢？

我看到的不相关键的最佳解决方案是将所有键放入一个数组中，对它们进行排序，然后使用排序后的数组中每个键的索引作为所需的哈希值。（因此，在这种情况下，参数本身就是键。）您可以通过二进制搜索相当有效地计算这些索引。假设您在程序期间存储排序后的数组，我认为您无法比这更有效地进行任何此类计算，而且它足够简单，您可以确信它的正确性。

这假设您在需要对其中任何一个进行散列之前知道所有密钥。如果不是这种情况，那么至少您可以使用未排序的数组和线性搜索（尽管也可能存在中间方法）。线性搜索可能看起来不是特别有效，但平均而言，它不会比涉及 256 个参数的纯算术计算差。