Hashing is another approach to searching. The idea of hashing is to store keys in an array of length m. keys are stored in array locations based on the "hash code" of the key. The hash code is an integer computed from the key by a hash function. If the hash function is chosen well, the keys are distributed across the array locations uniformly randomly.
There is always the possibility of two keys mapping to the same location, in which case a "collision" is said to occur. The standard mechanism to deal with collisions is to maintain a linked list of keys at each location. Look ups, inserts, and deletes take O(1+n/m) complexity, where n is the number of keys. If the "load" n/m grows large, the table can be rehashed to one with a larger number of locations; the keys are moved to the new tables. Rehashing is expensive.
One disadvantage of hashing is the need for a good hash function.
Here below is lecture which discuss hashing in details.
There is always the possibility of two keys mapping to the same location, in which case a "collision" is said to occur. The standard mechanism to deal with collisions is to maintain a linked list of keys at each location. Look ups, inserts, and deletes take O(1+n/m) complexity, where n is the number of keys. If the "load" n/m grows large, the table can be rehashed to one with a larger number of locations; the keys are moved to the new tables. Rehashing is expensive.
One disadvantage of hashing is the need for a good hash function.
Here below is lecture which discuss hashing in details.
No comments:
Post a Comment