( ( ( ( ( figure extendible hashingafter insertion of and directory split ( ( ( ( ( ( figure extendible hashingafter insertion of and leaf split these possibilities suggest that it is important for the bits to be fairly random this can be accomplished by hashing the keys into reasonably long integer--hence the name we close by mentioning some of the performance properties of extendible hashingwhich are derived after very difficult analysis these results are based on the reasonable assumption that the bit patterns are uniformly distributed the expected number of leaves is ( /mlog thus the average leaf is ln full this is the same as for -treeswhich is not entirely surprisingsince for both data structures new nodes are created when the ( )th entry is added