hashing the more surprising result is that the expected size of the directory (in other words is ( + / /mif is very smallthen the directory can get unduly large in this casewe can have the leaves contain pointers to the records instead of the actual recordsthus increasing the value of this adds second disk access to each search operation in order to maintain smaller directory if the directory is too large to fit in main memorythe second disk access would be needed anyway summary hash tables can be used to implement the insert and contains operations in constant average time it is especially important to pay attention to details such as load factor when using hash tablessince otherwise the time bounds are not valid it is also important to choose the hash function carefully when the key is not short string or integer for separate chaining hashingthe load factor should be close to although performance does not significantly degrade unless the load factor becomes very large for probing hashingthe load factor should not exceed unless this is completely unavoidable if linear probing is usedperformance degenerates rapidly as the load factor approaches rehashing can be implemented to allow the table to grow (and shrink)thus maintaining reasonable load factor this is important if space is tight and it is not possible just to declare huge hash table other alternatives such as cuckoo hashing and hopscotch hashing can also yield good results because all these algorithms are constant timeit is difficult to make strong statements about which hash table implementation is the "best"recent simulation results provide conflicting guidance and suggest that the performance can depend strongly on the types of items being manipulatedthe underlying computer hardwareand the programming language binary search trees can also be used to implement insert and contains operations although the resulting average time bounds are (log )binary search trees also support routines that require order and are thus more powerful using hash tableit is not possible to find the minimum element it is not possible to search efficiently for string unless the exact string is known binary search tree could quickly find all items in certain rangethis is not supported by hash tables furthermorethe (log nbound is not necessarily that much more than ( )especially since no multiplications or divisions are required by search trees on the other handthe worst case for hashing generally results from an implementation errorwhereas sorted input can make binary trees perform poorly balanced search trees are quite expensive to implementso if no ordering information is required and there is any suspicion that the input might be sortedthen hashing is the data structure of choice hashing applications are abundant compilers use hash tables to keep track of declared variables in source code the data structure is known as symbol table hash tables are the ideal application for this problem identifiers are typically shortso the hash function can be computed quicklyand alphabetizing the variables is often unnecessary