Hash Tables

From

---

Revision as of 18:10, 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 int h( int key )
    RETURN (key % M);
ENDFUNCTION