Page 447 - 《软件学报》2025年第7期

3368 软件学报 2025 年第 36 卷第 7 期

  2 d
 ∑ 
   

Pr(Y ⩽ i) = 1− 1− p j   (8)
  
j∈[0,i]
此处, 由于 Y 是离散变量且为整数, 根据 Pr(Y ⩽ i) 的解析式, 可以求解 Pr(Y = i) 的解析式:

Pr(Y = i) = Pr(Y ⩽ i)−Pr(Y ⩽ i−1)
  2 d   2 d
 ∑   ∑ 
       

= 1− 1− p j −1+ 1− p j  



     
j∈[0,i] j∈[0,i−1]
  2 d   2 d
 ∑   ∑ 
       
= 1− p j − 1−   (9)




  p j
   
j∈[0,i−1] j∈[0,i]
根据期望的定义, 可得:

∑
E(Y) = i·Pr(Y = i)
i∈[0,n]
∑
= i·(Pr(Y ⩽ i)−Pr(Y ⩽ i−1))
i∈[0,n]
∑
= n·Pr(Y ⩽ n)− Pr(Y ⩽ i)
i∈[0,n−1]
     2 d
 ∑     ∑  
    
 2 d      
 



= n− 1−(1− p i )  +...+  − 1− p i 
 
  1 

      
i∈[0,0] i∈[0,n−1]
  2 d   2 d
 ∑   ∑ 
   
   


= 1− p i +...+ 1−   (10)


  p i
   
i∈[0,0] i∈[0,n−1]
d = 0, 哈希索引单元的空间为 0 比特.
这里先检查最简单的情况

  2 0   2 0
 ∑   ∑ 
       


E(Y) = 1− p i +...+ 1− p i  


     
i∈[0,0] i∈[0,n−1]
= n−(np 0 +(n−1)p 1 +...+ p n−1 )
( ( ) )
n
i
= n− n p (1− p) n−i
i
(( ) )
n
i
= n−n p (1− p) n−i
i
(( ) )
n−1
i
= n−n(1− p) p (1− p) (n−1)−i
i
= n−n(1− p)
= np (11)
下面检查 d = 1 的情况, 即哈希索引单元的空间为 1 比特时:

  2 1   2 1
 ∑   ∑ 
   
   


E(Y) = 1− p i +...+ 1−   (12)


  p i
   
i∈[0,0] i∈[0,n−1]
∑ ∑ ∑
这里需要简单分析 p j 函数的特性. 首先, p j 取值是 [0,1], 并且整体是递增的, 即 1− p j
j∈[0,i] j∈[0,i] j∈[0,i]
( ) 2 ( ) 2
∑ ∑ nc
整体是递减的. 此外, 1− p j =(1−p 0 )(1−p 0 ). 可得, 1− p i =(1− p 0 )(1− p 0 ) ≈ (1−p 0 )np=(1−p 0 ) .
j∈[0,0] i∈[0,0] 2 e
  2 1    
 ∑  ∑  ∑   ∑ 
     
  2 1    





E(Y) = 1− p i +...+(1− p i ) ⩽ 1− p i +...+ 1− p i (1− p 0 ) ⩽ np(1− p 0 ) (13)




  
     
i∈[0,0] i∈[0,n−1] i∈[0,0] i∈[0,n−1]
同理, 当哈希索引单元的空间增加到 d 个比特时, 可以得到 Y 的期望值如下: