Hash Tables

Hash Tables (Dictionaries)

Hash tables, often called dictionaries or maps, are collections that let you quickly look up, add, or remove values using a unique key. They are one of the fastest and most convenient ways to associate a value with a label or identifier.

What You Need to Know

• You use a key to store or find a value (like using a contact's name to find their number).
• Each key in a hash table must be unique.
• The keys are unordered—there is no guarantee about the order in which keys or values will appear.
• Hash tables automatically handle all the details of how the data is organized and kept efficient. You don't have to worry about how it stores your data.

Performance

Hash tables usually provide very fast operations:

Operation	Average case	What it means
Insert	O(1)	Add a value by key, very fast
Lookup	O(1)	Find value by key, very fast
Delete	O(1)	Remove a value by key, very fast

You don’t need to configure memory size or adjust settings—just use the hash table, and it handles everything behind the scenes. In rare cases (lots of data or unusual key patterns), some operations might slow down, but this is seldom a problem for typical uses.

Using Hash Tables

Here’s how to use hash tables (or dictionaries/maps) in various languages:

JavaKotlinTypeScriptDartSwiftPython

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> map = new HashMap<>();
map.put("key1", 10);               // Add or update
map.put("key2", 20);
Integer value = map.get("key1");   // Lookup
map.remove("key2");                // Remove
boolean exists = map.containsKey("key1"); // Check presence

val map = mutableMapOf<String, Int>()
map["key1"] = 10                   // Add or update
map["key2"] = 20
val value = map["key1"]            // Lookup
map.remove("key2")                 // Remove
val exists = map.containsKey("key1") // Check presence

const map = new Map<string, number>();
map.set("key1", 10);               // Add or update
map.set("key2", 20);
const value = map.get("key1");     // Lookup
map.delete("key2");                // Remove
const exists = map.has("key1");    // Check presence

Map<String, int> map = {};
map["key1"] = 10;                  // Add or update
map["key2"] = 20;
int? value = map["key1"];          // Lookup
map.remove("key2");                // Remove
bool exists = map.containsKey("key1"); // Check presence

var map = [String: Int]()
map["key1"] = 10                   // Add or update
map["key2"] = 20
let value = map["key1"]            // Lookup
map.removeValue(forKey: "key2")    // Remove
let exists = map.keys.contains("key1") // Check presence

map_dict = {}
map_dict["key1"] = 10              # Add or update
map_dict["key2"] = 20
value = map_dict.get("key1")       # Lookup
del map_dict["key2"]               # Remove
exists = "key1" in map_dict        # Check presence

Why Hash Tables Are Useful

Hash tables make it easy to solve problems where you need fast access to data by a key.

For example, suppose you want to find the first value that appears twice in a list. Without a hash table, you'd have to check every pair, which can be slow. With a hash table (or hash set), you can remember what you’ve seen so far and solve the problem quickly:

JavaKotlinTypeScriptDartSwiftPython

public static Integer firstRecurring(int[] a) {
    Set<Integer> seen = new HashSet<>();
    for (int v : a) {
        if (!seen.add(v)) return v; // already present
    }
    return null;
}
// O(n) time, O(n) space

fun firstRecurring(a: IntArray): Int? {
    val seen = mutableSetOf<Int>()
    for (v in a) {
        if (!seen.add(v)) return v // already present
    }
    return null
}
// O(n) time, O(n) space

function firstRecurring(a: number[]): number | null {
    const seen = new Set<number>();
    for (const v of a) {
        if (seen.has(v)) return v; // already present
        seen.add(v);
    }
    return null;
}
// O(n) time, O(n) space

int? firstRecurring(List<int> a) {
    Set<int> seen = <int>{};
    for (int v in a) {
        if (!seen.add(v)) return v; // already present
    }
    return null;
}
// O(n) time, O(n) space

func firstRecurring(_ a: [Int]) -> Int? {
    var seen = Set<Int>()
    for v in a {
        if !seen.insert(v).inserted { return v } // already present
    }
    return nil
}
// O(n) time, O(n) space

def first_recurring(a: list[int]) -> int | None:
    seen: set[int] = set()
    for v in a:
        if v in seen:
            return v
        seen.add(v)
    return None
# O(n) time, O(n) space

Hash tables are an essential tool for working with data where fast lookup or associations are needed.