8

我正在使用用 C 语言编程的微控制器进行电子项目。

我需要将一些 ID 及其相关信息存储在闪存 (SD) 中。这些 ID 长 16 个字节，因此有 2^128 个可能的值。尽管它们是 16 个字节，但只会使用 50000 个（唯一）值。在 SD 中存储所有可能的 (2^128) ID 在物理上是不可能的。

我只能存储 50000 个使用过的值，但是我必须遍历所有（最坏的情况）它们才能找到我需要的值。此外，必须为它们中的每一个计算一个 16 字节的值比较，这使得它非常慢。

所以我想我需要某种（哈希？）函数，将 2^128 值映射到 50000（将 16 个字节映射到 2 个字节）。很明显，一些原始值将映射到相同的值/索引。这个想法是，当我得到一个 ID 时，我应用一个哈希函数，它给我一个介于 0 和 ~50000 (0-65535) 之间的索引。使用该索引，我可以直接访问存储 ID 及其相关信息的 SD 扇区。正如我已经指出的那样，该索引将引用内存中的位置，由于某些不同的 ID 映射到相同的索引值，因此各种 ID 将共存。我必须找到正确的 ID，但它只需要几个比较而不是 50000 个原始 ID。

任何想法/意见将不胜感激。

提前致谢。

4

4 回答 4

1

当然 Mat's 很好，但是，通过使用素数应该会导致更少的碰撞 where uuid[x] == uuid[y](and x!=y)

uint32_t uuid[4];

uint16_t hash = 0;
for(i = 0; i < 4; i++)
{
   // hash *= 31; //next line does this, note 31 is a prime
   hash = (hash << 5) - hash;
   hash += (uuid[i] & 0xffff) ^ (uuid[i] >> 16);
}

或者这个版本更好，因为它减少了前 16 位和后 16 位的异或匹配的冲突。

uint16_t hash = 0;
for(i = 0; i < 4; i++)
{
   hash = (hash << 5) - hash; //(*=31)
   hash += uuid[i] & 0xffff;
   hash = (hash << 5) - hash; //(*=31)
   hash += uuid[i] >> 16;
}
于 2013-02-13T13:19:48.323 回答
1

由于 ID 长 16 个字节，我猜它存储在 ASCII 字符串中，所以 ELFhash 可能有效。

int ELFhash(char *key) {
    unsigned long h = 0;
    while(*key) {
        h = (h << 4) + *key++;
        unsigned long g = h & 0xf0000000L;
        if (g) h ^= g >> 24;
        h &= -g;
    }
    return h & M;
}

其中 M 是小于 65536 或 50000 的素数。

很多ID字符串的前缀很可能是相同的，因为它们代表特定的meaaing，所以你应该更加小心防止冲突，否则链表会很长。

于 2013-02-13T16:08:58.197 回答
1

只需使用 16 MSB 的实际 ID。这很愚蠢，但是有了您的详细信息，它将起作用。

于 2013-02-13T11:36:49.740 回答
0

假设您的 128 位值中的位是“均匀分布的”，您可以简单地执行以下操作：

 uint32_t uuid[4];

 uint16_t hash = 0;
 for(i = 0; i < 4; i++)
 {
     hash ^= (uuid[i] & 0xffff) ^ (uuid[i] >> 16);
 }

可能还有其他更聪明的方法，但是这种方法非常简单，并且可能效果很好。

于 2013-02-13T11:28:55.413 回答