SeniorCodeRareNot answered yet
Implement a hash function and collision handling
Implement the FNV-1a hash for strings and a hash table that resolves collisions by separate chaining.
Requirements:
each bucket a chain of entries.
a threshold such as 0.75.
fnv1a: a fast non-cryptographic hash with good distribution.- The table supports
insert,find,erase; one bucket per hash slot, - Keep average operations O(1): rehash (grow) when the load factor exceeds
uint64_t fnv1a(const std::string& s) {
// your code here
}
template<typename K, typename V>
class HashMap {
public:
void insert(const K& key, const V& val); // your code here
std::optional<V> find(const K& key) const; // your code here
bool erase(const K& key); // your code here
};Write the implementation.
A good hash function distributes keys uniformly and is fast to compute. FNV-1a and djb2 are classic non-cryptographic hashes. Collision resolution: separate chaining (linked list per bucket) or open addressing (linear/quadratic probing, double hashing). std::unordered_map uses separate chaining in most implementations.
- ✗Using a bad hash function that clusters values — leads to O(n) lookups in the worst case
- ✗Not handling growing the table (rehashing) when load factor exceeds threshold
- ✗Using a cryptographic hash (SHA, MD5) for a hash table — far too slow
- →What is the load factor and how does it affect performance?
- →Compare open addressing and separate chaining for cache performance.
Contents
Task
Implement a hash table with separate chaining and the FNV-1a hash function for strings.
Key points
- FNV-1a: fast, good distribution, simple implementation.
- Separate chaining: each bucket is a linked list — simple but poor cache locality.
- Rehash when load factor > 0.75 to keep average O(1) operations.
- Open addressing (linear probing) is cache-friendlier but harder to implement correctly.
Contents
