The Height and Size of Random Hash Trees and Random Pebbled Hash Trees
Luc Devroye · SIAM Journal on Computing · 1999
The random hash tree and the N-tree were introduced by Ehrlich in 1981. In the random hash tree, n data points are hashed to values X 1 , . . . , X n , independently and identically distributed random variables taking values that are uniformly distributed on [0,1]. Place the X i 's in n equal-sized buckets as in hashing with chaining. For each bucket with at least two points, repeat the same process, keeping the branch factor always equal to the number of bucketed points. If H n is the height of tree obtained in this manner, we show that H n /log 2 n \to 1 in probability. We also show that the expected number of nodes in the random hash tree and random pebbled hash tree is asymptotic to 2.3020238 . . . n and 1.4183342. . . n, respectively.