HashMap
Implemented a templated chaining-based hash table supporting dynamic resizing, insertion, lookup, deletion, and iteration
About This Project
This project involved building a fully functional hash map using separate chaining with a custom singly linked list structure. The design required managing dynamic memory, implementing a custom iterator, handling resizing and rehashing, and ensuring average-case constant-time performance for lookups and updates. The implementation focused on correctness, efficiency, and robust handling of hash collisions.
Key Features
- Implemented a templated chaining hash map using singly linked lists
- Supported insertion, deletion, lookup, updating, and iteration over key-value pairs
- Designed a dynamic resizing mechanism with rehashing to maintain performance
- Created a custom iterator supporting begin(), end(), and operator++
- Ensured efficient handling of hash collisions using separate chaining
- Implemented load factor monitoring and automatic table expansion
Technologies Used
- IDE: VSCode
- C++
Challenges & Learnings
Challenges:
The most challenging part was implementing rehashing correctly while maintaining stable iteration behavior and avoiding memory leaks. Designing the iterator to traverse buckets and linked lists seamlessly required careful control of pointer movement and edge-case handling.
What I Learned:
Through this project, I deepened my understanding of hashing, collision resolution, and average-case vs. worst-case performance. I gained practical experience with dynamic memory management, iterators, templating, and designing data structures that balance efficiency and correctness.
