hash table 关于负载因子
hash table about the load factor
我正在研究算法 class 的散列 table，我对负载因子感到困惑。
为什么负载因子 n/m 很重要，'n' 是元素的数量，'m' 是 table 槽的数量？
另外，当所有元素都存储在一个槽中时，为什么这个负载因子等于 n(j) 的预期长度，即散列中槽 j 处的链表 table？
散列 table 的关键 属性 是查找元素所需的 预期常数时间 。*
为了实现这一点，散列 table 的实现者必须确保每个对散列 table returns 的查询都低于某个 fixed步数。
如果你有一个带 m 个桶的散列 table 并且你无限期地添加元素（即 n>>m），那么列表的大小也会增长，你不能保证查找的预期恒定时间，但您宁愿获得线性时间（因为 运行 您需要遍历不断增加的链表的时间将超过查找存储桶的时间）。
那么，我们怎样才能做到列表不增长呢？那么，您必须确保列表的长度受某个 固定常量 的限制 - 我们如何做到这一点？好吧，我们必须添加额外的桶。
如果哈希 table 实现良好，则用于将元素映射到桶的哈希函数应该将元素 均匀地 分布在桶中。如果哈希函数这样做，那么列表的长度将大致相同。
如果元素分布均匀，其中一个列表有多长？显然，我们将元素总数除以桶数，即 负载因子 n/m（元素数 per bucket = expected/average 每个列表的长度）。
因此，为了确保恒定的时间查找，我们要做的是跟踪负载因子（再次：列表的预期长度），这样，当它超过 固定常量时 我们可以添加额外的桶。
当然，还有更多的问题接踵而至，比如如何重新分配你已经存储的元素，或者你应该添加多少个桶。
要带走的重要信息是，需要负载因子来决定何时向散列table添加额外的桶——这就是为什么它不是仅 'important' 但 至关重要 .
当然，如果将所有元素都映射到同一个桶中，那么每个列表的平均长度就没有多大价值了。如果您在桶中均匀分布，所有这些东西才有意义。
*请注意 预期 - 我怎么强调都不为过。典型的听到"hash table have constant look up time"。他们不！最坏的情况总是 O(n)，你不能让它消失。
添加到现有答案中，让我快速推导一下。
考虑在 table 中任意选择的桶。如果将 ith 元素插入此元素，则令 X_i 为等于 1 的指标随机变量，否则为 0。
我们要找E[X_1 + X_2 + ... + X_n].
根据线性期望，这等于 E[X_1] + E[X_2] + ... E[X_n]
现在我们需要求出E[X_i].的值 这就是根据期望值的定义(1/m) 1 + (1 - (1/m) 0) = 1/m。因此，将所有 i's 的值相加，我们得到 1/m + 1/m + 1/m n 次。这等于 n/m. 我们刚刚找到 插入随机桶的预期元素数 ，这是负载因子。
我正在研究算法 class 的散列 table，我对负载因子感到困惑。 为什么负载因子 n/m 很重要，'n' 是元素的数量，'m' 是 table 槽的数量？ 另外，当所有元素都存储在一个槽中时，为什么这个负载因子等于 n(j) 的预期长度，即散列中槽 j 处的链表 table？
散列 table 的关键 属性 是查找元素所需的 预期常数时间 。*
为了实现这一点，散列 table 的实现者必须确保每个对散列 table returns 的查询都低于某个 fixed步数。
如果你有一个带 m 个桶的散列 table 并且你无限期地添加元素（即 n>>m），那么列表的大小也会增长，你不能保证查找的预期恒定时间，但您宁愿获得线性时间（因为 运行 您需要遍历不断增加的链表的时间将超过查找存储桶的时间）。
那么，我们怎样才能做到列表不增长呢？那么，您必须确保列表的长度受某个 固定常量 的限制 - 我们如何做到这一点？好吧，我们必须添加额外的桶。
如果哈希 table 实现良好，则用于将元素映射到桶的哈希函数应该将元素 均匀地 分布在桶中。如果哈希函数这样做，那么列表的长度将大致相同。
如果元素分布均匀，其中一个列表有多长？显然，我们将元素总数除以桶数，即 负载因子 n/m（元素数 per bucket = expected/average 每个列表的长度）。
因此，为了确保恒定的时间查找，我们要做的是跟踪负载因子（再次：列表的预期长度），这样，当它超过 固定常量时 我们可以添加额外的桶。
当然，还有更多的问题接踵而至，比如如何重新分配你已经存储的元素，或者你应该添加多少个桶。
要带走的重要信息是，需要负载因子来决定何时向散列table添加额外的桶——这就是为什么它不是仅 'important' 但 至关重要 .
当然，如果将所有元素都映射到同一个桶中，那么每个列表的平均长度就没有多大价值了。如果您在桶中均匀分布，所有这些东西才有意义。
*请注意 预期 - 我怎么强调都不为过。典型的听到"hash table have constant look up time"。他们不！最坏的情况总是 O(n)，你不能让它消失。
添加到现有答案中，让我快速推导一下。
考虑在 table 中任意选择的桶。如果将 ith 元素插入此元素，则令 X_i 为等于 1 的指标随机变量，否则为 0。
我们要找E[X_1 + X_2 + ... + X_n].
根据线性期望，这等于 E[X_1] + E[X_2] + ... E[X_n]
现在我们需要求出E[X_i].的值 这就是根据期望值的定义(1/m) 1 + (1 - (1/m) 0) = 1/m。因此，将所有 i's 的值相加，我们得到 1/m + 1/m + 1/m n 次。这等于 n/m. 我们刚刚找到 插入随机桶的预期元素数 ，这是负载因子。