Approximate average storage utilization of bucket methods with arbitrary fanout
Chuan-Heng Ang, Hanan Samet · Nordic journal of computing · 1996
The approximate average storage utilization of bucket methods with fanout of n, assuming a uniform distribution of data, is shown to depend only on the fanout and not on any other factors such as the directory structure. It obeys the formula (ln n)/(n - 1). The analysis makes use of a generalization of previously published methods for n = 2 and n = 4 and its predictions match these results. The formula is applicable to methods that are based on digital searching (e.g., tries) or balancing rather than comparison-based methods. The formula is also used to detect an erroneous statement about the average storage utilization of a ternary system in [12].