Hash Tables
From
(Difference between revisions)
(Created page with 'Hashing is called a ''Key to Address'' system. Objects (records) are stored in a table, and each object stored occupies a slot in the table. The location of the slot is called th...') |
(→Hash Table Behavior) |
||
| Line 7: | Line 7: | ||
<br/> | <br/> | ||
<pre> | <pre> | ||
| - | FUNCTION | + | FUNCTION hash( key ) |
RETURN (key % M); | RETURN (key % M); | ||
ENDFUNCTION | ENDFUNCTION | ||
</pre> | </pre> | ||
Revision as of 18:11, 28 March 2009
Hashing is called a Key to Address system. Objects (records) are stored in a table, and each object stored occupies a slot in the table. The location of the slot is called the address of the object. The address of an object is obtained using a function called a hash function. Each object has an associated key. The hash function takes the key as a parameter and returns the address of the object.
Hash Table Behavior
A good hash function should distribute the objects throughout the table with equal probability. A good hash function should minimize collisions. In addition, a good hash function should be easy to calculate.
For example, a simple hash function for a table of size M is:
FUNCTION hash( key )
RETURN (key % M);
ENDFUNCTION
