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) ret
0 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.