What is HashMap Insert?
HashMap is a data structure that stores key-value pairs using a hash function to compute an index into an array of buckets. It provides average O(1) time complexity for insert, search, and delete operations.
Insert Operation
Computes hash of key, finds bucket index, stores key-value pair.
- Start with empty HashMap of size 8
- Insert ("name", "Alice") → hash("name") = 3 → store at index 3
- Insert ("age", 25) → hash("age") = 5 → store at index 5
- Insert ("city", "NY") → hash("city") = 3 → collision! chain at index 3
- Time Complexity (Average): O(1)
- Time Complexity (Worst): O(n)
- Space Complexity: O(n)
Time Complexity Analysis
Collision Handling
- Chaining: Each bucket holds a linked list of entries that hash to the same index
- Open Addressing: Find next empty slot using linear/quadratic probing
Real-world Applications
- Caching and memoization
- Database indexing
- Counting frequency of elements
- Two Sum and similar interview problems
- Symbol tables in compilers
HashMap is one of the most important data structures in programming, widely used in interview problems and real-world applications for its constant-time average performance.