我对哈希表的理解是，它们使用哈希函数将键与内存中的位置相关联，并在内存中预先分配了"桶"总数。目标是有足够的存储桶，我不必使用链接，从而将我理想的O(1)访问时间复杂性减慢到n/m x O(1)其中 n 是要存储的唯一键的数量，m 是存储桶的数量。
因此，如果我有 1000 个唯一项目要存储，我将需要不少于1000个存储桶，也许还需要更多，以最大程度地减少必须使用链式链表的可能性。如果不是这种情况，我们预计平均哈希表会有很多很多冲突。现在，如果我们有 1000 个预分配的存储桶，这意味着我有 1000 字节的已分配内存，分布在我的内存周围。因此，我的哈希表中的每个唯一键都会导致内存碎片，从而碎片化我的 RAM。
这是否意味着哈希表的使用基本上可以保证导致与唯一键数量成正比的碎片量？此外，这似乎表明，如果您知道将有多少个唯一键，则可以使用一些统计信息来选择存储桶的数量，从而大大减少碎片。是这样吗？
分配的1000字节内存，分布在我的内存周围
不，您有一个包含 1000 个条目的数组(其大小几乎可以肯定大于每个条目 1 个字节(。
如果每个条目都足够大，可以就地处理非冲突情况，则在发生冲突之前不需要额外的动态分配。 (例如，您可能使用联合和 1 位标志来指示此条目是独立存储桶还是指向链表的指针。
如果不是，那么当你写一个条目时，需要为它分配空间，并在表数组本身中存储一个指针。 (例如，具有小键但大值的键值哈希表(。 空哈希表仍然可以充满 NULL 指针。
您可能仍然希望它包含指针和哈希值的结构(对于单成员存储桶(。 然后，如果完整哈希值与查询不匹配，则可以拒绝绝对不存在的查询，而无需其他级别的间接寻址;例如，对于 32 位或 64 位哈希，它比索引 1024 个条目表的 10 位多得多。
为了减少整体碎片，您可以使用平板分配器或其他技术从从全局分配器获得的连续块中雕刻节点。 让哈希表维护自己的私有自由列表可以帮助链接列表节点的空间局部性，因此它们至少不会分散在许多不同的虚拟页面(TLB 未命中(中，希望不是 DRAM 页面(甚至更慢的缓存未命中(。