Hashing and std::hash

Hash Table vs Binary Search Tree

When should I use a hash table (std::unordered_map) versus a binary search tree (std::map)?

Abstract art representing computer programming

Hash tables (std::unordered_map) and binary search trees (std::map) are both associative containers that store key-value pairs, but they have different characteristics and are suited for different use cases. Here are some guidelines to help you decide when to use each.

When to use a hash table (std::unordered_map)

Fast average-case lookup, insertion, and deletion are required.

  • Hash tables provide constant-time O(1) average-case complexity for these operations.
  • If you need to frequently access, insert, or remove elements and the order of elements is not important, a hash table is a good choice.

The keys have a good hash function and are uniformly distributed.

  • A good hash function minimizes collisions and ensures efficient distribution of elements across the buckets.
  • If the keys have a natural hash function or can be easily hashed, a hash table can provide excellent performance.

The order of elements is not important.

  • Hash tables do not maintain any particular order of elements. If you don't need to iterate over the elements in a specific order, a hash table is suitable.

When to use a Binary Search Tree (std::map)

The elements need to be stored in a sorted order based on keys.

  • Binary search trees maintain the elements in sorted order, allowing for efficient traversal and range queries.
  • If you require the elements to be sorted or need to perform operations like finding the minimum or maximum key, a binary search tree is a good choice.

Logarithmic-time complexity for lookup, insertion, and deletion is acceptable.

  • Binary search trees provide logarithmic-time O(log n) complexity for these operations in the average and worst cases.
  • If you can tolerate slightly slower performance compared to hash tables, but still need efficient operations, a binary search tree is suitable.

The keys do not have a good hash function or are not uniformly distributed.

  • If the keys lack a good hash function or are prone to collisions, a binary search tree can provide more consistent performance.

Here's an example to illustrate the difference in usage:

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>

int main() {
  // Using std::unordered_map
  std::unordered_map<std::string, int> hashTable = {
    {"apple", 5}, {"banana", 3}, {"orange", 2}};

  // Fast lookup in hash table
  std::cout << "Count of 'banana' in hash table: "
    << hashTable["banana"] << "\n\n";

  // Fast insertion
  hashTable["grape"] = 4;  

  // Using std::map
  std::map<std::string, int> bst = {
    {"apple", 5}, {"banana", 3}, {"orange", 2}};

  // Traversing elements in sorted order
  std::cout << "Elements in sorted order (BST):\n";
  for (const auto& pair : bst) {
    std::cout << pair.first << ": "
      << pair.second << '\n';

  // Finding the minimum key
  std::cout << "Minimum key: "
    << bst.begin()->first << '\n';
Count of 'banana' in hash table: 3

Elements in sorted order (BST):
apple: 5
banana: 3
orange: 2
Minimum key: apple

In this example, we use std::unordered_map for fast lookup and insertion operations, and std::map for maintaining elements in sorted order and performing operations like finding the minimum key.

Remember, the choice between a hash table and a binary search tree depends on your specific requirements, such as the desired time complexity, ordering needs, and the characteristics of the keys. Consider the trade-offs and choose the data structure that best fits your use case.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved