Hash Tables in Different Programming Languages

Hash tables are incredibly useful tools in programming for storing and retrieving information quickly. Think of them like a super-efficient filing system or a digital dictionary where you can look up a definition (value) using a word (key) almost instantly. While you can build hash tables from scratch, most modern programming languages provide ready-to-use implementations. This makes life much easier for programmers!

This article will explore how hash tables look and feel in some popular programming languages like Python, Java, JavaScript and C++. We’ll see that while the names might change, the core idea of storing key-value pairs for fast access remains the same.

Hash Tables in Python: Dictionaries (dict)

In Python, the primary built-in implementation of a hash table is called a dictionary, often abbreviated as dict. Dictionaries store data as key-value pairs, just like the conceptual hash table.

  • Keys: Must be unique and “hashable” (meaning they can be processed by a hash function). Common hashable types include strings, numbers, and tuples containing only hashable types.
  • Values: Can be any Python object.

Using a dictionary in Python is straightforward:

  # Create an empty dictionary
  my_dict = {}

  # Add key-value pairs
  my_dict["name"] = "Alice"
  my_dict["age"] = 30
  my_dict["city"] = "New York"

  # Access a value using its key
  print(my_dict["name"])  # Output: Alice

  # Check if a key exists
  if "age" in my_dict:
    print("Age exists:", my_dict["age"]) # Output: Age exists: 30

  # Remove a key-value pair
  del my_dict["city"]

  print(my_dict) # Output: {'name': 'Alice', 'age': 30}

Python’s dictionaries are highly optimized. Python automatically handles the underlying details like choosing a hash function, managing the internal array (the “buckets”), handling collisions, and resizing the table when needed (rehashing). This allows programmers to focus on using the dictionary effectively rather than managing its internal workings.

Hash Tables in Java: HashMap and Hashtable

Java provides several implementations of hash tables, primarily within its Collections Framework. The most commonly used ones are HashMap and Hashtable, both found in the java.util package. They both implement the Map interface, which defines the standard operations for key-value mappings.

  • HashMap: This is the generally preferred implementation for most situations.
    • It allows one null key and multiple null values.
    • It is not synchronized, meaning it’s faster in single-threaded applications or when synchronization is handled externally.
  • Hashtable: This is an older, legacy class.
    • It does not allow null keys or values.
    • It is synchronized, meaning its methods are protected against simultaneous modification by multiple threads. However, this synchronization often leads to performance bottlenecks compared to HashMap. For concurrent applications, java.util.concurrent.ConcurrentHashMap is usually a better choice.

Here’s a simple example using HashMap:

  import java.util.HashMap; // Import the HashMap class
  import java.util.Map;     // Import the Map interface

  public class HashMapExample {
    public static void main(String[] args) {
      // Create a HashMap (stores String keys and Integer values)
      Map<String, Integer> scores = new HashMap<>();

      // Add key-value pairs using put()
      scores.put("Alice", 95);
      scores.put("Bob", 80);
      scores.put("Charlie", 88);

      // Access a value using its key with get()
      System.out.println("Alice's score: " + scores.get("Alice")); // Output: Alice's score: 95

      // Check if a key exists using containsKey()
      if (scores.containsKey("Bob")) {
        System.out.println("Bob's score exists: " + scores.get("Bob")); // Output: Bob's score exists: 80
      }

      // Remove a key-value pair using remove()
      scores.remove("Charlie");

      System.out.println(scores); // Output: {Bob=80, Alice=95} (order may vary)
    }
  }

Tip

In modern Java development, prefer HashMap for general use. If you need thread safety (multiple parts of your program accessing the map concurrently), consider using ConcurrentHashMap instead of the older Hashtable.

Like Python’s dict, Java’s HashMap handles hashing, collisions, and resizing automatically, providing an efficient and easy-to-use map implementation.

Hash Tables in JavaScript: Objects and Map

JavaScript has traditionally used its fundamental Object type to mimic hash table behavior. More recently, ES6 (ECMAScript 2015) introduced the Map object, offering a more direct and often more suitable hash table implementation.

  • Plain Objects ({}):

    • Keys are implicitly converted to strings (or Symbols). If you use a non-string key, it gets converted.
    • They are easy to create using object literal syntax ({}).
    • Historically, the order of properties wasn’t guaranteed (though modern JavaScript engines often preserve insertion order for non-integer keys).
    • Getting the number of elements (size) requires extra steps (like using Object.keys(obj).length).
      // Create an object
  let user = {};

  // Add properties (key-value pairs)
  user["name"] = "David";
  user.age = 25; // Dot notation also works for valid identifiers

  // Access properties
  console.log(user.name); // Output: David
  console.log(user["age"]); // Output: 25

  // Check if a property exists
  if ("name" in user) {
    console.log("Name exists:", user.name); // Output: Name exists: David
  }

  // Remove a property
  delete user.age;

  console.log(user); // Output: { name: 'David' }

    jsoncodes javascript

  • Map Object:

    • Introduced in ES6, designed specifically as a key-value collection.
    • Keys can be any data type (including objects, functions, etc.), not just strings/symbols.
    • Maintains the insertion order of elements.
    • Provides a built-in size property to easily get the number of entries.
    • Uses methods like set(), get(), has(), delete().
      // Create a Map
  let productPrices = new Map();

  // Add entries using set()
  productPrices.set("apple", 0.5);
  productPrices.set("banana", 0.25);
  productPrices.set(123, "SKU Number"); // Key can be a number

  // Access values using get()
  console.log(productPrices.get("apple")); // Output: 0.5
  console.log(productPrices.get(123));    // Output: SKU Number

  // Check if a key exists using has()
  if (productPrices.has("banana")) {
    console.log("Banana price exists:", productPrices.get("banana")); // Output: Banana price exists: 0.25
  }

  // Get the size
  console.log("Map size:", productPrices.size); // Output: Map size: 3

  // Remove an entry using delete()
  productPrices.delete("apple");

  console.log(productPrices.size); // Output: 2

Tip

While plain objects are often used for simple key-value storage (especially when keys are strings), the Map object is generally more robust and flexible, particularly if you need non-string keys, guaranteed order, or easy size tracking.

JavaScript engines manage the underlying hash table implementation for both Objects and Maps, optimizing performance for common operations.

Hash Tables in C++: unordered_map

In C++, the Standard Template Library (STL) provides a hash table implementation called std::unordered_map. It’s defined in the <unordered_map> header file. As the name suggests, it stores elements in an unordered fashion, optimized for fast key lookups.

  • Purpose: Stores unique keys and associated values, allowing for efficient retrieval, insertion, and deletion based on the key.
  • Keys: Must be hashable. Standard C++ types like int, double, std::string, and pointers have built-in hash functions. For custom types (like your own classes or structs), you need to provide a hash function and an equality comparison operator (==).
  • Values: Can be any C++ type.

Here’s how you can use std::unordered_map:

  #include <iostream>
  #include <unordered_map> // Include the header
  #include <string>

  int main() {
    // Create an unordered_map (string keys, int values)
    std::unordered_map<std::string, int> student_grades;

    // Add key-value pairs using operator[]
    student_grades["Eve"] = 92;
    student_grades["Frank"] = 75;

    // Another way to insert using insert() and std::make_pair
    student_grades.insert(std::make_pair("Grace", 89));

    // Access a value using its key with operator[]
    // Note: If the key doesn't exist, operator[] inserts a default-constructed value!
    std::cout << "Eve's grade: " << student_grades["Eve"] << std::endl; // Output: Eve's grade: 92

    // Safer access using at() (throws an exception if key not found)
    try {
        std::cout << "Frank's grade: " << student_grades.at("Frank") << std::endl; // Output: Frank's grade: 75
    } catch (const std::out_of_range& oor) {
        std::cerr << "Key not found: " << oor.what() << std::endl;
    }

    // Check if a key exists using count() or find()
    if (student_grades.count("Grace")) { // count() returns 1 if key exists, 0 otherwise
      std::cout << "Grace's grade exists: " << student_grades["Grace"] << std::endl; // Output: Grace's grade exists: 89
    }

    // Remove a key-value pair using erase()
    student_grades.erase("Frank");

    // Iterate and print the map (order is not guaranteed)
    std::cout << "Current map contents:" << std::endl;
    for (const auto& pair : student_grades) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // Possible Output (order might differ):
    // Current map contents:
    // Grace: 89
    // Eve: 92

    return 0;
  }

Warning

Be careful when using the [] operator for accessing elements in std::unordered_map. If the key you provide doesn’t exist, [] will automatically insert a new element with that key and a default-constructed value (e.g., 0 for integers, empty string for std::string). Use at() or check with find() or count() if you only want to access existing elements.

Similar to the implementations in other languages, std::unordered_map handles the complexities of hashing, collision resolution, and resizing internally, allowing developers to leverage fast key-based lookups without managing the low-level details. C++ also offers std::unordered_set for storing unique keys without associated values.

What’s Next?

Now that you’ve seen how hash tables are implemented in several popular programming languages, you might be curious to explore other related topics: