闭地址哈希表空间需求及对应开地址负载因子计算问题

定义与前提 #

• 设闭地址哈希表的数组大小（哈希表大小）为 m，已插入条目数为 n，负载因子 α = n/m，因此 n = α·m
• 内存单位：1个内存“字”
• 闭地址哈希表空间组成：
  • 链表引用数组：每个引用占1字，总空间为 m×1
  • 链表节点：每个节点存1个键+1个链表引用，共2字，n个节点总空间为 n×2
• 开地址哈希表为键数组：每个键占1字，数组总空间等于闭地址哈希表的总空间

闭地址哈希表总空间计算 #

总空间公式推导：
总空间 S = 数组空间 + 链表节点空间 = m + 2n
代入 n = α·m，得：
S = m + 2α·m = m(1 + 2α)

针对不同负载因子计算：

• 当 α = 0.5 时：
  S = m(1 + 2×0.5) = 2m
• 当 α = 1.0 时：
  S = m(1 + 2×1.0) = 3m
• 当 α = 2.0 时：
  S = m(1 + 2×2.0) = 5m

对应开地址哈希表的负载因子计算 #

开地址哈希表的数组大小 m' = S（与闭地址总空间相同），开地址负载因子 α' = n/m'

代入 n = α·m 和 m' = m(1+2α)，得：
α' = (α·m) / (m(1+2α)) = α/(1+2α)

针对不同负载因子计算：

• 当 α = 0.5 时：
  α' = 0.5/(1+2×0.5) = 0.25
• 当 α = 1.0 时：
  α' = 1.0/(1+2×1.0) ≈ 0.333
• 当 α = 2.0 时：
  α' = 2.0/(1+2×2.0) = 0.4

内容的提问来源于stack exchange，提问作者Affectionate Mango