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