Some Aspects of Order Preserving Extendible Hashing

摘要

The method of extendible hashing is analyzed as to the effects of non-uniformity and non-randomness in the hashing function. Expected and worst case performance results are derived for storage and access costs. The results are applicable to any key-to-address transformation utilizing a similar directory mechanism. The effect of bucket size is also analyzed.