为什么小负载因子哈希表的大 O 复杂度为 O(1)？
Why is the Big-O complexity for Small Load Factor HashTables O(1)?
我无法理解使用负载因子对哈希表的链式和开放式寻址进行大 O 分析。
据我了解：
LoadFactor = (# of entries in HashTable)/(# of "slots" in HashTable) = (n/m)
因此，LoadFactor 反映了输入哈希表的数据正在使用多少哈希表。
对于链式哈希表，最坏情况下的时间复杂度为 O(n)，因为所有元素散列到哈希表中最后一个槽的数据分布不均匀将问题简化为在链表中搜索大小为 n.
对于开放寻址的哈希表，最坏情况下的时间复杂度为 O(n)，因为再次将所有元素散列到一个 hashCode 的数据的非均匀分布将导致所有元素被连续输入。因此，问题简化为在大小为 n 的数组中进行搜索。
对于最坏的情况，我假设 n>m。
现在对于小负载因子，链式和开放寻址哈希表都将产生 O(1)。
我看不出 n>m 和 n 之间的区别
为什么会这样？
小负载因子哈希 tables 的预期情况时间复杂度为 O(1)，因为访问哈希 table 中的项目的时间不依赖于散列 table.
中的项目
当 n 远小于 m（桶数）时，很可能每个键都已散列到一个唯一的桶中。随着 n 的增加，冲突的可能性（两个键散列到同一个桶）增加。当n > m时，然后Pigeonhole principle，保证至少有两个key会散列成相同的值。
所以当n远小于m时，碰撞的可能性更小，所以预期的查找时间是O(1)。随着项目数量的增加，您将花费更多时间来解决冲突。
经验证据表明您不希望负载系数超过 0.75。可能接近 0.70。当 n > 0.70*m 时，散列 table 变得非常低效。当然，实际数字会因您的数据而异，但这是一个很好的经验法则。
Birthday problem 显示了碰撞率如何随着 n 接近 m 而增加。当您在 table 中插入项目数的平方根时，遇到单个碰撞的可能性接近 50%。如果您要创建一个大小为 365 的散列 table 并开始插入项目，那么当您仅插入 25 个项目时，您看到散列冲突的可能性高于 50%。 （这是假设一个好的散列函数。一个糟糕的散列函数会增加整体碰撞的可能性。）
我无法理解使用负载因子对哈希表的链式和开放式寻址进行大 O 分析。
据我了解：
LoadFactor = (# of entries in HashTable)/(# of "slots" in HashTable) = (n/m)
因此，LoadFactor 反映了输入哈希表的数据正在使用多少哈希表。
对于链式哈希表，最坏情况下的时间复杂度为 O(n)，因为所有元素散列到哈希表中最后一个槽的数据分布不均匀将问题简化为在链表中搜索大小为 n.
对于开放寻址的哈希表，最坏情况下的时间复杂度为 O(n)，因为再次将所有元素散列到一个 hashCode 的数据的非均匀分布将导致所有元素被连续输入。因此，问题简化为在大小为 n 的数组中进行搜索。
对于最坏的情况，我假设 n>m。
现在对于小负载因子，链式和开放寻址哈希表都将产生 O(1)。
我看不出 n>m 和 n 之间的区别
为什么会这样？
小负载因子哈希 tables 的预期情况时间复杂度为 O(1)，因为访问哈希 table 中的项目的时间不依赖于散列 table.
中的项目当 n 远小于 m（桶数）时，很可能每个键都已散列到一个唯一的桶中。随着 n 的增加，冲突的可能性（两个键散列到同一个桶）增加。当n > m时，然后Pigeonhole principle，保证至少有两个key会散列成相同的值。
所以当n远小于m时，碰撞的可能性更小，所以预期的查找时间是O(1)。随着项目数量的增加，您将花费更多时间来解决冲突。
经验证据表明您不希望负载系数超过 0.75。可能接近 0.70。当 n > 0.70*m 时，散列 table 变得非常低效。当然，实际数字会因您的数据而异，但这是一个很好的经验法则。
Birthday problem 显示了碰撞率如何随着 n 接近 m 而增加。当您在 table 中插入项目数的平方根时，遇到单个碰撞的可能性接近 50%。如果您要创建一个大小为 365 的散列 table 并开始插入项目，那么当您仅插入 25 个项目时，您看到散列冲突的可能性高于 50%。 （这是假设一个好的散列函数。一个糟糕的散列函数会增加整体碰撞的可能性。）