When Hashes Collide
Basic strategies for handling hash collisions
Issue: 10.3 (March/April 2012)
Author: JC Cruz
Article Description: No description available.
Article Length (in bytes): 17,347
Starting Page Number: 39
RBD Number: 10308
Resource File(s): None
Related Link(s): None
Known Limitations: None
Excerpt of article text...
Regardless of what algorithm is used, all hash functions will suffer at least one collision. So today, we take a close look at a hash collision and understand why it happens. Then we study some basic strategies to manage a collision.
Collection of Hash
In a previous article (RSD 8.4, May/June 2010), we studied how a general-purpose hash function reduces a data item into an integer value. We learned the traits of a good hash function and ways to test for those traits.
There are many ways we can use hash functions, too many to be listed in detail. One use is to mark each data item stored in a collection. Each item gets a unique id, making it easy for us to do queries, inserts and edits. Again, there are many types of collection structures, but the one we will focus on is the hash table.
The hash table
A hash table arranges its data as "columns" of keys and values (Figure 1). In the value column are the data items, in the keys column the hashes for each item. The key column is always sorted, while the value column is not.
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.