Hash Tables

From

(Difference between revisions)
Jump to: navigation, search
(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 int h( int key )
+
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
Personal tools
MediaWiki Appliance - Powered by TurnKey Linux