The height and size of random hash trees and random pebbled hash trees

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; inde pendently and identically distributed random variables taking values that a re uniformly distributed on [0, 1]. Place the X-i's in n equal-sized bucket s as in hashing with chaining. For each bucket with at least two points, re peat 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 --> 1 in probability. In the random pebbled hash tree, we remove one point randomly and place it in the present node (as wi th the digital search tree modification of a trie) and perform the bucketin g step as above on the remaining points (if any). With this simple modifica tion, [GRAPHICS] in probability. We also show that the expected number of nodes in the rando m hash tree and random pebbled hash tree is asymptotic to 2.3020238 ... n a nd 1.4183342 ... n, respectively.