几天前我开始阅读有关实现各种数据结构的内容，然后转向哈希表并卡在了一个特定的点上。
我对哈希表如何实现的理解: key K 被传递给哈希函数 H，后者返回 K 的哈希版本，HK。 HK 可能至少应该是一个 uint32_t 来解决冲突，我们有一个大小为 X 的数组，该项目存储在该数组的索引 HK 中..但是，这是否需要至少一个长度为 uint32_t 的预分配数组(或者 H 的返回值是什么)？假设我们不将数据本身存储在该数组中，而是将 ptr 存储到数据，那么我们需要一个长度为 uint32_t 的 ptr_t 数组。这看起来很浪费，在 64 位上这意味着内存使用: 2^32 * 8 = 34359738368 字节或 ~32GB 仅用于指向数据的数组，这显然不是它在现实生活中的实际实现方式..
那么我错过了什么？
最佳答案
这取决于实现。可以通过三种基本方法完成此操作:
1) 使用小散列。因此，不是使用 32 位哈希，而是使用 8 位哈希。
2) 使用多级散列。因此，例如，12 位散列可以确定条目进入哪个“桶”，但仅当完整的 32 位散列匹配时才会发生冲突。每个桶都存储在链表或类似结构中。 (也许针对在其中搜索完整的 32 位散列进行了优化。)
3) 使用稀疏数组。这些数据结构不需要为未填充的槽实际存储空格。 (在实践中，它可能是完全不同的东西，例如一棵树，但它就像一个具有高效搜索的稀疏数组。)
关于c++ - 实现哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8937705/