Hash Maps (Maps)

Abstract

The Map ADT (often called an associative array) allows us to map keys to their corresponding values. While a standard Hash Table checks for the presence or absence of a key, a Hash Map associatively pairs each key with a distinct value record, enabling fast average constant-time storage, retrieval, and removal based on key queries.

• Category: Key-Value Storage Structure
• Stores: Associative pairs of hashable key identifiers linked to variable value payloads.
• Built on top of: Arrays, Hash Tables, and Collision Resolution frameworks.
• Typical use cases: Database index records, grade books, caching systems, representing one-to-many relationship maps.

---

Core Structure

A Hash Map utilizes an underlying backing array of entries where each slot stores a key and its value together as a unified pair. Keys must be hashable and support an equality test to handle uniqueness checks and bucket routing.

Index Mapping (via H(key) % m)
[ Index 0 ] ---> | Key: "Kammy"  | Value: 'A' |
[ Index 1 ] ---> | Key: "Alicia" | Value: 'C' |
[ Index 2 ] ---> NULL

Key Idea

When we find, insert, or remove elements in a Hash Map, the operational routing algorithms mirror those of a standard Hash Table exactly, but everything is processed strictly with respect to the key. Once the target key’s slot is located, the associated value payload is exposed.

---

Structural Properties

• Invariant: Every stored value is structurally bound to a unique key identifier. Duplicate keys cannot point to multiple independent primary entries simultaneously within the base map structure.
• Overwriting Behavior: Attempting to insert a key that already exists will not abort the operation. Instead, the original value associated with that key is overwritten by the new input value.
• Order Guarantee: Does NOT guarantee consistent element ordering. Iterating through a Hash Map yields elements in an unstable sequence determined entirely by hash distributions and collision arrangements.

---

Data Structure Operations

Insert(key, value)

Hashes the key to resolve its backing array index, replacing the old value with the new value if the key already exists.

• Time Complexity: $O(1)$ average; $O(N)$ worst-case under severe clustering.

Algorithm 5 Hash Map Insertion (Collision-Free Paradigm)

procedure Insert($key, value, arr$)

$index \gets$ HashFunction($key$)

$returnVal \gets \text{NULL}$

if $arr[index].key == key$ then

$returnVal \gets arr[index].value$

$arr[index] \gets \langle key, value \rangle$

return $returnVal$

Find(key)

Traverses the probe sequence or chain corresponding to the key’s hash index and returns the associated value if found.

• Time Complexity: $O(1)$ average case.

Algorithm 6 Hash Map Find

procedure Find($key, arr$)

$index \gets$ HashFunction($key$)

if $arr[index].key == key$ then

return $arr[index].value$

else

return $\text{NULL}$

Remove(key)

Locates the key inside the map, isolates its associated value payload for output preservation, and deletes the element entry.

• Time Complexity: $O(1)$ average case.

Algorithm 7 Hash Map Removal

procedure Remove($key, arr$)

$index \gets$ HashFunction($key$)

$returnVal \gets \text{NULL}$

if $arr[index].key == key$ then

$returnVal \gets arr[index].value$

Delete($arr[index]$)

return $returnVal$

---

C++ Language Implementation Detail

In the C++ Standard Template Library (STL), the primary implementation of a Hash Map is std::unordered_map, which relies on Separate Chaining for collision management.

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
 
int main() {
    // Initializing a Hash Map
    std::unordered_map<std::string, std::string> gradeBook = {
        {"Kammy", "A"},
        {"Alicia", "C"}
    };
 
    // Inserting a new pair
    gradeBook.insert({"Bob", "B"});
 
    // Querying using the bracket operator
    std::cout << gradeBook["Kammy"] << std::endl; // Outputs: A
}

Duplicate Insertion Deviation

C++ deviates slightly from the traditional Map ADT specification during duplicate handling. When inserting a duplicate element using unordered_map::insert(), the container protects the original value and ignores the overwrite. To force a replacement value update, you must use the assignment bracket operator instead (gradeBook["Key"] = newValue).

---

Structuring One-to-Many Relationships

Hash Maps are often deployed to manage one-to-many relationship structures by mapping discrete keys onto a collection container value, such as a vector or an inner nested Hash Table.

// Mapping drawer labels to a vector of office items
std::unordered_map<std::string, std::vector<std::string>> desk = {
    {"pens", {"favPen", "redPen"}},
    {"personal papers", {"schedule"}}
};
 
// Modifying the nested vector collection value dynamically
desk["personal papers"].push_back("taxDocument");

Cascading Time Complexity Risks

When wrapping collection structures inside map values, the cost of accessing a nested item requires adding the find complexity of that inner collection container. For an unsorted backing vector containing $n$ elements, locating a nested target adds an internal $O(n)$ linear lookup cost. If absolute constant-time access is required across all nested values, use an std::unordered_set as the value type instead of a vector.

---

Related Notes

• Hash Functions
• Collision Resolution Strategies
• Closed Addressing (Separate Chaining)