algorithm - 用于存储由唯一的 8 位十六进制标识的对象的数据结构，用于快速插入和查找

Question

我有一堆具有唯一 8 位十六进制标识符 ex[fd4786ac] 的对象，我需要快速构建和查找它们。删除不是优先事项。这些十六进制值当前存储为字符串。

考虑了 trie(或 trie 的某些变体)、跳跃列表和哈希表的某些变体。在 AVL 树上使用跳过列表会更好，因为这些字符串很可能是连续的但不能保证并且树会经常重新平衡。如果其他数据结构更适合我的需要，我对它们持开放态度。

Answer 1

一个不错的选择是将您的 key 转换为 32 位整数，然后使用哈希表。

如果您只想为这个用例编写自己的代码，那么:

• 不要一直散列键或存储散列值，而是使用双射散列函数并使用散列而不是键。
• 由于您的 key 非常小，您可能应该使用开放寻址——它会节省空间并且速度更快。维基百科会给你很多探测方案的选择。我目前喜欢罗宾汉哈希:https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/