Database Reference
In-Depth Information
Figure A2-5.
Converting Alphanumeric Keys to Numeric
A2.3 Collision Resolution
As mentioned earlier, when hash functions are applied, collisions are likely to occur.
Three collision resolution techniques are prevalent:
linear probing
,
synonym chaining
,
and
rehashing
.
A2.3.1 Linear Probing
The linear probing strategy prescribes that whenever a collision occurs, the empty
location that is closest to the hash address is found and used. If the end of the table is
reached, wrap-around is allowed. Figure
A2-6
illustrates this. In the figure, collision has
been resolved for nodes D, E, and G.
Figure A2-6.
Illustrating Linear Probing
