问在计算散列表项的空间消耗时负载因子的作用

EN

在开放寻址中，您有一个固定大小的插槽数组，将元素分配到其中.这只是一个普通的数组，有元素的空间和(可选的)一些控制位，用来标记哪些插槽是满的，哪些是空的。

假设我们有一个带有s槽的表，并且我们希望将n个元素分配到表中。这意味着α=n/ s，元素数除以槽数。然后整个表的空间使用是sM，因为有s个插槽，每个插槽使用M字节。因此，如果我们想计算每个元素使用的内存，我们要计算sM /n=M/ (n / s) =M/α，这是公式的来源。从直觉上讲，这是有道理的。如果表中有单个元素，负载因子为1/s，而总内存( Ms )除以元素数(1)，则另一方面，如果表已满载(n = s)，则α=1，总内存(Ms)除以元素数等于M。

通过查看每个桶的内存量并将其乘以桶的数量，您的计算就处于正确的轨道上。如果将M视为每个元素的大小，而s作为插槽的数目，则最终得到了Ms的总空间使用量(没有必要在其中添加M项，这样做实际上给出了错误的单位:M有单元“每个元素”，Ms有单位“字节”，因此不应该将它们加在一起)。