We use hash tables to track the counts of the elements in O(1) time. Thats beautiful when you are trying to count the word frequencies in a large text file or dealing with unicode characters.
In these examples you can’t know the boundaries of the data that you are dealing with. But if we know the data boundary, for example if you are trying to count the letter frequency in a string, using an unordered_map<char,int> works in O(1) time complexity, simply using an array consisting of 26 elements would work better. When using unordered_map, the CPU runs a hash function, computes modulo arithmetic against bucket count, and resolves collisions across linked lists. Plus, every unique key triggers a separate heap allocation (new Node), increasing heap fragmentation. On the other hand, std::array<int, 26> lives entirely on the stack, indexing costs few CPU cycles.
this code snippet simply increments the character c’s count stored in a fixed array consisting 26 elements. The c - ‘A’ part is to calculate the offset from the ASCII value. (count of the letter A is in the count[0]…)
void increment_array(std::array<int, 26>& count, char c) {
count[c - 'A']++;
}and this is the x86_x64 assembly output of the snippet:
increment_array(std::array<int, 26>&, char):
movsx rsi, sil ; // Extend the c into 64-bit int.
add DWORD PTR [rdi-260+rsi*4], 1 ; // adding +1 to the value in memory (++ operation)
ret0 function call, 0 branching , everything done in just a couple of CPU cycles.
and this is the unordered_map version:
void increment_map(std::unordered_map<char, int>& count, char c) {
count[c]++;
}compiled into x86 assembly output:
increment_map(std::unordered_map<char, int>&, char):
// --- [1. SETUP & REGISTER BACKUPS] ---
sub rsp, 56 // Allocate 56 bytes of stack space
mov r8, QWORD PTR [rdi+8] // r8 = map._M_bucket_count (number of buckets)
xor edx, edx // edx = 0 (prepare high 32 bits for division)
mov QWORD PTR [rsp+24], rbp // Save callee-saved registers to stack
movsx rbp, sil // rbp = sign-extended char 'c'
mov rax, rbp // rax = hash (for char, hash is the char value itself)
mov QWORD PTR [rsp+16], rbx // Save rbx
mov rbx, rdi // rbx = this pointer (&map)
mov QWORD PTR [rsp+40], r13 // Save r13
mov QWORD PTR [rsp+32], r12 // Save r12
// --- [2. COMPUTE BUCKET INDEX] ---
div r8 // rax = rax / r8, rdx = rax % r8 (rdx = bucket_index)
mov rax, QWORD PTR [rdi] // rax = map._M_buckets (pointer to bucket array)
mov r13, rbp // r13 = target char 'c'
mov r11, QWORD PTR [rax+rdx*8] // r11 = buckets[rdx] (head node of this bucket)
lea r10, [0+rdx*8] // r10 = bucket byte offset (rdx * 8)
test r11, r11 // Check if bucket is empty (null pointer)
je .L41 // If empty -> jump to allocate new node
// --- [3. TRAVERSE LINKED LIST (SEARCH KEY)] ---
mov rsi, QWORD PTR [r11] // rsi = node pointer
mov r12, rdx // r12 = current bucket index
movzx edi, BYTE PTR [rsi+8] // edi = node->key (char at offset +8)
cmp dil, r13b // Compare node->key == 'c'
je .L3 // If match found -> jump to value increment (.L3)
.L43:
mov rcx, QWORD PTR [rsi] // rcx = node->_M_nxt (next node pointer)
test rcx, rcx // End of the entire linked list?
je .L41 // If null -> key not found, go allocate
movsx rax, BYTE PTR [rcx+8] // rax = next_node->key
xor edx, edx // edx = 0
mov r11, rsi // r11 = current node
mov rdi, rax // rdi = next_node->key
div r8 // Re-hash: next_node->key % bucket_count
cmp r12, rdx // Is the next node still in the same bucket?
jne .L41 // If bucket index changed -> key not found in bucket
mov rsi, rcx // Advance to next node
cmp dil, r13b // Compare next_node->key == 'c'
jne .L43 // If still not equal -> continue loop
.L3:
// --- [4. FAST PATH: KEY FOUND] ---
mov rax, QWORD PTR [r11] // rax = node pointer
lea r12, [rax+12] // r12 = &node->value (int at offset +12)
test rax, rax // Safety check
je .L41 // Branch if null
.L5:
// --- [5. INCREMENT VALUE & RETURN] ---
add DWORD PTR [r12], 1 // ++(node->value) -> PERFORM INCREMENT
mov rbx, QWORD PTR [rsp+16] // Restore callee-saved registers
mov rbp, QWORD PTR [rsp+24]
mov r12, QWORD PTR [rsp+32]
mov r13, QWORD PTR [rsp+40]
add rsp, 56 // Deallocate stack frame
ret // Return from function
.L41:
// --- [6. SLOW PATH: ALLOCATE NEW NODE] ---
mov edi, 16 // Argument: sizeof(Node) = 16 bytes
mov QWORD PTR [rsp+48], r14 // Save r14
mov QWORD PTR [rsp+8], r10 // Save bucket byte offset
mov QWORD PTR [rsp], r8 // Save bucket count
call operator new(unsigned long) // rax = heap address of new node
// Initialize new node fields:
mov BYTE PTR [rax+8], r13b // node->key = 'c'
mov QWORD PTR [rax], 0 // node->_M_nxt = nullptr
mov DWORD PTR [rax+12], 0 // node->value = 0 (default initialized)
mov r12, rax // r12 = new node address
// Check if table needs resizing (Load Factor check):
mov rdx, QWORD PTR [rbx+24] // rdx = map._M_element_count
mov rsi, QWORD PTR [rsp] // rsi = bucket_count
lea rdi, [rbx+32] // rdi = &map._M_rehash_policy
mov ecx, 1 // Adding 1 element
mov r14, QWORD PTR [rbx+40]
call std::__detail::_Prime_rehash_policy::_M_need_rehash
test al, al // Does it need rehash?
jne .L6 // If yes -> jump to resize table (.L6)
// --- [7. INSERT NODE INTO BUCKET (NO REHASH)] ---
mov r8, QWORD PTR [rbx] // r8 = map._M_buckets
mov r10, QWORD PTR [rsp+8] // r10 = bucket offset
add r10, r8 // r10 = &buckets[bucket_index]
mov rax, QWORD PTR [r10] // rax = existing bucket head
test rax, rax
je .L18 // If empty -> insert as first element in bucket
.L46:
// Splice new node into bucket's existing list
mov rax, QWORD PTR [rax]
mov QWORD PTR [r12], rax // new_node->next = old_head->next
mov rax, QWORD PTR [r10]
mov QWORD PTR [rax], r12 // old_head->next = new_node
.L19:
add QWORD PTR [rbx+24], 1 // map._M_element_count++
mov r14, QWORD PTR [rsp+48] // Restore r14
add r12, 12 // r12 = &new_node->value (+12 offset)
jmp .L5 // Jump to increment value and return
.L6:
// --- [8. REHASH TABLE (RESIZE & RE-BUCKET)] ---
mov r13, rdx // r13 = new bucket count
cmp rdx, 1
je .L44
mov rax, rdx
shr rax, 60
jne .L45 // Overflow check -> throw exception
lea rdx, [0+rdx*8] // rdx = new bucket array size in bytes
mov rdi, rdx // rdi = size
mov QWORD PTR [rsp], rdx
call operator new(unsigned long) // Allocate new bucket array
mov rdx, QWORD PTR [rsp] // rdx = size
xor esi, esi // esi = 0
mov rdi, rax // rdi = new bucket array address
call memset // Zero-initialize new bucket array
lea r10, [rbx+48]
mov r8, rax // r8 = new bucket array pointer
.L9:
// Traverse old nodes and redistribute them into new buckets
mov rsi, QWORD PTR [rbx+16] // rsi = map._M_before_begin._M_nxt
mov QWORD PTR [rbx+16], 0
test rsi, rsi
je .L12 // If empty -> jump to cleanup
xor edi, edi
lea r9, [rbx+16]
jmp .L16
.L13:
mov rdx, QWORD PTR [r11]
mov QWORD PTR [rcx], rdx
mov rax, QWORD PTR [rax]
mov QWORD PTR [rax], rcx
test rsi, rsi
je .L12
.L16:
// Loop: recompute hash % new_bucket_count for each existing node
mov rcx, rsi
xor edx, edx
mov rsi, QWORD PTR [rsi]
movsx rax, BYTE PTR [rcx+8] // rax = node->key
div r13 // node->key % new_bucket_count
lea rax, [r8+rdx*8] // rax = &new_buckets[new_idx]
mov r11, QWORD PTR [rax]
test r11, r11
jne .L13
mov r11, QWORD PTR [rbx+16]
mov QWORD PTR [rcx], r11
mov QWORD PTR [rbx+16], rcx
mov QWORD PTR [rax], r9
cmp QWORD PTR [rcx], 0
je .L14
mov QWORD PTR [r8+rdi*8], rcx
.L14:
mov rdi, rdx
test rsi, rsi
jne .L16 // Repeat for all remaining nodes
.L12:
// Free the old bucket array
mov rdi, QWORD PTR [rbx] // rdi = old bucket array pointer
cmp r10, rdi
je .L17 // Don't delete if it was single stack node
mov rax, QWORD PTR [rbx+8] // rax = old bucket count
mov QWORD PTR [rsp], r8
lea rsi, [0+rax*8] // rsi = old array size in bytes
call operator delete(void*, unsigned long) // Free old bucket memory
mov r8, QWORD PTR [rsp]
.L17:
// Update map metadata with new buckets
mov rax, rbp // rax = current key 'c'
xor edx, edx
mov QWORD PTR [rbx+8], r13 // map._M_bucket_count = new_bucket_count
div r13 // Compute bucket for our new node
mov QWORD PTR [rbx], r8 // map._M_buckets = new_buckets
lea r10, [0+rdx*8]
add r10, r8 // r10 = &new_buckets[index]
mov rax, QWORD PTR [r10]
test rax, rax
jne .L46
.L18:
// Link new node as the head of bucket
mov rax, QWORD PTR [rbx+16]
mov QWORD PTR [rbx+16], r12
mov QWORD PTR [r12], rax
test rax, rax
je .L20
movsx rax, BYTE PTR [rax+8]
xor edx, edx
div QWORD PTR [rbx+8]
mov QWORD PTR [r8+rdx*8], r12
.L20:
lea rax, [rbx+16]
mov QWORD PTR [r10], rax
jmp .L19 // Return back to increment value
.L45:
// Exception handling: array size overflow
shr r13, 61
je .L11
call std::__throw_bad_array_new_length()
.L44:
lea r8, [rbx+48]
mov QWORD PTR [rbx+48], 0
mov r10, r8
jmp .L9
.L11:
// Exception handling: out of memory
call std::__throw_bad_alloc()compile here with -O2 opt
briefly, it computes the bucket index and traverses the linked list to find the key, if found, increments the value of the key c, if not found, the code must branch into heap allocation via operator new to create and initialize a 16-byte node, followed by splicing it into the bucket’s list. Finally, it must evaluate the container’s load factor. if the table has exceeded its capacity threshold, the assembly executes a full rehash routine, which entails allocating a larger bucket array, re-distributing every existing node via modulo operations, and deallocating the old bucket buffer. (We will dive into the low-level details of hashing algorithms and collision resolution in a follow-up post.)
TLDR: If you know the bounds of your key set in advance, use a fixed-size array instead of a hash map. You get O(1) space complexity, eliminate dynamic heap allocations entirely.