hash tables the new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods the reduction in space is accomplished by exploiting the possibility that small fraction of errors of commission may be tolerable in some applications -"space/time trade-offs in hash coding with allowable errors, bloom hash table is data structure used to store keysoptionallywith corresponding values insertsdeletes and lookups run in ( time on average the underlying idea is is to store keys in an array key is stored in the array locations ("slots"based on its "hash codethe hash code is an integer computed from the key by hash function if the hash function is chosen wellthe objects are distributed uniformly across the array locations if two keys map to the same locationa "collisionis said to occur the standard mechanism to deal with collisions is to maintain linked list of objects at each array location if the hash function does good job of spreading objects across the underlying array and take ( time to computeon averagelookupsinsertionsand deletions have ( /mtime complexitywhere is the number of objects and is the length of the array if the "loadn/ grows largerehashing can be applied to the hash table new array with larger number of locations is allocatedand the objects are moved to the new array rehashing is expensive ( ( mtimebut if it is done infrequently (for examplewhenever the number of entries doubles)its amortized cost is low hash table is qualitatively different from sorted array--keys do not have to appear in orderand randomization (specificallythe hash functionplays central role compared to binary search trees (discussed in )inserting and deleting in hash table is more efficient (assuming rehashing is infrequentone disadvantage of hash tables is the need for good hash function but this is rarely an issue in practice similarlyrehashing is not problem outside of realtime systems and even for such systemsa separate thread can do the rehashing hash function has one hard requirement--equal keys should have equal hash codes this may seem obviousbut is easy to get wronge by writing hash function that is based on address rather than contentsor by including profiling data softer requirement is that the hash function should "spreadkeysi the hash codes for subset of objects should be uniformly distributed across the underlying array in additiona hash function should be efficient to compute common mistake with hash tables is that key that' present in hash table will be updated the consequence is that lookup for that key will now faileven though it' still in the hash table if you have to update keyfirst remove itthen update itand finallyadd it back--this ensures it' moved the correct array location as ruleyou should avoid using mutable objects as keys