Kim*_*-wu 5 c++ algorithm hash hashtable hashmap
几天前，我开始阅读有关实现各种数据结构的文章，并开始研究哈希表，并陷入了一个特定的点。
我对哈希表如何实现的理解：将密钥 K 传递给哈希函数 H，该函数返回 K 的哈希版本 HK。HK 可能至少应该是一个 uint32_t 来解决冲突，我们有一个大小为 X 的数组，该项目存储在该数组的索引 HK 中。但是，这是否需要一个至少为 uint32_t 长度的预分配数组（或者 H 的返回值是什么）？假设我们不将数据本身存储在该数组中，而是将 ptr 存储到数据中，那么我们需要一个长度为 uint32_t 的 ptr_t 数组。这似乎很浪费，在 64 位上这意味着内存使用量：2^32 * 8 = 34359738368字节或~32GB只是用于数据的ptr数组，这显然不是它在现实生活中的实际实现方式。
那么我错过了什么？
这取决于实施。可以通过三种基本方法来完成此操作：
1) 使用小的哈希值。因此，我们不使用 32 位哈希，而是使用 8 位哈希。
2) 使用多级散列。因此，例如，12 位哈希可以确定条目进入哪个“桶”，但只有在完整的 32 位哈希匹配时才会发生冲突。每个桶都存储在链表或类似的结构中。（也许是为了搜索其中的完整 32 位哈希而优化的。）
3）使用稀疏数组。这些数据结构不需要实际存储未填充槽的空白空间。（实际上，它可能是完全不同的东西，例如树，但它的作用就像具有高效搜索的稀疏数组。）