Java Reference
In-Depth Information
Position 4
-->
Position 5
-->
Position 6
-->
Position 7
--> cow
Position 8
--> shark
Position 9
-->
Position 10
-->
Position 11
-->
Position 12
--> fish
Position 13
--> cat
Position 14
-->
Position 15
--> dog tortoise
Position 16
--> horse
Position 17
--> flamingo
Position 18
-->
Position 19
--> pelican
Position 20
--> parrot lion
Position 21
-->
Position 22
-->
Observe that for some indices of the array, there have been two strings assigned
to that array cell. For example the dog and tortoise have been both assigned
to index 15, while parrot and lion have been assigned to index 20. This is
what is called ollision phenomenon. For strings, we just solved this problem by
concatenating strings stored at the same position (for illustration purpose). In
the ideal case, if no collision happens, we can insert a new string in constant
time, and search for a given string in constant-time too. This hashing technique
is therefore ecient compared to arrays/lists data-structures. This explains
why hashing is often used in real-world applications (and standardized in Java
API packages). Let us now see how to resolve the collision problems by using
two different strategies: (1) the open address method, and (2) the chained list
method.
7.8.1 Open address hashing
Let us resolve hashing collisions using the open address scheme. The method
consists of first computing the array index of the hashed string. Then two cases
occur:
- Either the hash table cell at that index is free, and then we store the string
there, or
- There is already a string stored at that index. Then we proceed starting from
that index to search for the first free position of the hash table by iteratively
incrementing the index. We eventually find that position and store the string
there.
 
Search WWH ::




Custom Search