Repository navigation
Hashtable
- Review JDK HashMap implementation. In particular lookup, insertion, load factor and resizing
- Implement a open addressing hash table or a closed addressing with dynamic array and benchmark it against a
java.util.HashMap.
A good hash function is essential for the lookup performance of a hash table. Generally a good hash function should provide a uniform distribution of hash values. If all keys are known a perfect hash function won't cause any key collision.
hash = hashfunc(key)
index = hash % bucket_size
The hash value will be mapped to an index of a hash table bucket by using the modulo operator. If bucket size is power of 2 the modulo operator can be replaced with masking (hash & (bucket_size-1)) to improve performance
It's the number of entries (n) divided by the number of buckets (k) in hash table. load_factor = n / k
Providing that the hash function is good the load factor affects the performance of the hash table. A very high load factor will degrade performance making the table slow. Very low load factor is also not desired as the table occupies unnecessary memory.
The collision resolution can be addressed with two methods. Closed addressing uses a separate data structure (to the bucket/array) to store values with the same key hash value. On the other hand open addressing relies exclusively to one data structure (bucket) to address collision. It requires an addressing (probing) algorithm which is used to both resolve the collision by mapping collided keys to an index of the bucket and perform lookup.
- Separate chain with linked list
- Low referential locality (CPU cache friendly)
- Memory efficient
- Separate chain with list head cells
- Low referential locality thought better than linked list
- Less memory efficiency
- Separate chain with dynamic array
- High referential locality (and TLB - translation lookaside buffer)
- A drawback of open addressing hash tables is that high load factor substantially degrades performance.
- The have high locality reference as all entries are stored in the bucket/array
Probing algorithms:
- Linear
- Quadratic
- Double hashing
Since load factor affects performance any decent hash table implementation should support resizing of its bucket. There usually entails the creation of a larger bucket when the load factor exceeds a specified threshold and the copy of all entries from the old to the new bucket. Based on the performance requirements there are 2 methods of doing this:
- Copy of all entries: On every insertion we check the load factor. Once it exceeds the maximum threshold we create the new bucket and copy all entries. The time required for this operation depends on the number of entries. The higher the number of entries the more time it takes to complete the resizing.
- Incremental resizing: For time-critical/real-time application incremental resizing might be a better option. During resizing we create the new bucket but we don't copy all entries. Instead on subsequent insertions we always use the new bucket and gradually move the entries to the new bucket till the old bucket is empty