Hash Tables

From

Revision as of 18:10, 28 March 2009 (view source) 209.237.84.181 (Talk) (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...') ← Older edit		Revision as of 18:11, 28 March 2009 (view source) 209.237.84.181 (Talk) (→Hash Table Behavior) Newer edit →
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