Review of Hashing - Database Systems - page 460

A hash function takes a key value, applies an algorithm to determine its location.
Mathematically, we represent this as follows (Figure A2-1 ):
Figure A2-1. Basic Concept of Hashing
The hash function maps key values from a relatively large domain to a relatively
smaller range of address locations. Because of this, collision may occur and must be
resolved. Collision occurs when two or more keys map to the same address, as illustrated
in Figure A2-2 .
Figure A2-2. Illustrating Collision
Since two records cannot be stored in the same location, the collision must be
resolved. Various collision resolution techniques have been proposed. These will be
discussed shortly.
A2.2 Hash Functions
A good hash function should exhibit two important features: Firstly, it should be easy
and fast to compute. Secondly, it must attempt to scatter the key values (random or
non-random) evenly over the address space. Various hash functions have been proposed
and tested with varying results. Among the commonly discussed hash functions are the
following: absolute addressing, direct table lookup, division-remainder, mid-square,
folding, and truncation. We will briefly discuss each technique.