Hash Function
three primary requirements in implementing a good hash function for a given data type
- deterministic: equal keys must produce the same hash value
- efficient to compute
- uniformly distribute the keys
Hashing with separate chaining : hash to find the list that could contain the key, then sequentially search through that list for the key.
Hashing with linear probing: Another approach to implementing hashing is to store N key-value pairs in a hash table of size M > N, relying on empty entries in the table to help with with collision resolution.
Collision Resolution
Java Implementation
When an element is added to the Hashtable, the element is placed into a bucket based on the hash code of the key. Each bucket can have multiple records which are organized in a particular order.
Two factors affecting performance
initial capacity and load factor
Smaller load factors cause faster average lookup times at the cost of increased memory consumption.