Discussion on Hash Tables
Explore the fundamentals of hash tables and hashing methods. Understand chaining, open addressing, perfect hashing, and practical hash functions to optimize data storage and collision resolution in Java applications.
We'll cover the following...
Additional notes
Hash tables and hash codes represent an enormous and active field of research that is just touched upon in this chapter. The online Bibliography
on
A variety of different hash table implementations exist. The one we discussed before in this chapter is known as hashing with chaining (each array entry
contains a chain (List) of elements). Hashing with chaining dates back to
an internal IBM memorandum authored by H. P. Luhn and dated January
1953. This memorandum also seems to be one of the earliest references
to linked lists.
An alternative to hashing with chaining is the use of open addressing schemes, where all data is stored directly in an array. These schemes include the LinearHashTable structure. This idea was also
proposed, independently, by a group at IBM in the 1950s. Open addressing schemes must deal with the problem of collision resolution: the case
where two values hash to the same array location. Different strategies
exist for collision resolution; these provide different performance guarantees and often require more sophisticated hash functions than the ones
described here.
Yet another category of hash table implementations are the so-called
perfect hashing methods. These are methods in which find(x) operations
take ...