Hash Table — Language Specifications & API Reference¶

Table of Contents¶

1. Go: map
2. Java: HashMap
3. Java: HashSet
4. Java: ConcurrentHashMap
5. Python: dict
6. Python: set
7. Comparison Table

Go: map¶

Declaration and Initialization¶

// Declare with make (preferred for non-empty maps)
m := make(map[string]int)          // empty map
m := make(map[string]int, 100)     // empty map with capacity hint (avoids early resizes)

// Literal initialization
m := map[string]int{
    "alice": 95,
    "bob":   82,
}

// Declare nil map (reads return zero value; writes panic)
var m map[string]int  // m is nil

Operations¶

Key Constraints¶

Valid key types must be comparable (== and != are defined): - All numeric types, string, bool, pointers, channels, arrays (of comparable elements), structs (of comparable fields). - Not valid: slices, maps, functions.

Internal Implementation¶

• Go maps use a hash table with buckets of 8 key-value pairs each.
• Overflow buckets are chained when a bucket is full.
• Growth trigger: Average entries per bucket > 6.5, or too many overflow buckets.
• Incremental rehashing: Growth happens gradually during map operations (not all at once).
• Iteration order: Deliberately randomized (do not rely on order).
• Not goroutine-safe: Concurrent read+write causes fatal error: concurrent map read and map write. Use sync.RWMutex or sync.Map.

Zero Value Behavior¶

m := make(map[string]int)
fmt.Println(m["missing"]) // 0 (zero value for int)

// Distinguish "missing" from "exists with zero value":
val, ok := m["missing"]
// val = 0, ok = false

Java: HashMap¶

Declaration and Initialization¶

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

// Default capacity 16, load factor 0.75
Map<String, Integer> map = new HashMap<>();

// Custom initial capacity
Map<String, Integer> map = new HashMap<>(1000);

// Custom capacity and load factor
Map<String, Integer> map = new HashMap<>(1000, 0.5f);

// Initialize from another map
Map<String, Integer> map = new HashMap<>(existingMap);

// Immutable map (Java 9+)
Map<String, Integer> map = Map.of("alice", 95, "bob", 82);

Core Methods¶

Atomic Compound Methods (Java 8+)¶

Internal Implementation¶

• Array of Node entries (linked list buckets).
• Default capacity: 16. Always a power of 2.
• Load factor: 0.75 (configurable).
• Treeification (Java 8+): When a chain exceeds 8 entries AND table capacity >= 64, the chain converts to a red-black tree (O(log n) worst case per bucket). Un-treeifies when chain drops below 6.
• Hash spreading: h = key.hashCode(); h ^= (h >>> 16); — spreads high bits to low bits.
• Null keys: One null key is allowed (hashes to bucket 0).
• Not thread-safe: Use Collections.synchronizedMap() or ConcurrentHashMap for concurrency.
• Iteration order: Not guaranteed (use LinkedHashMap for insertion order).

Key Requirements¶

• Must implement hashCode() and equals() consistently.
• Contract: If a.equals(b), then a.hashCode() == b.hashCode().
• The reverse is NOT required (different objects may share a hash code).

Java: HashSet¶

Declaration and Initialization¶

import java.util.HashSet;
import java.util.Set;

Set<String> set = new HashSet<>();
Set<String> set = new HashSet<>(Arrays.asList("a", "b", "c"));
Set<String> set = Set.of("a", "b", "c"); // Java 9+, immutable

Core Methods¶

Set Operations¶

Set<String> a = new HashSet<>(Arrays.asList("1", "2", "3"));
Set<String> b = new HashSet<>(Arrays.asList("2", "3", "4"));

// Union
Set<String> union = new HashSet<>(a);
union.addAll(b);  // {"1", "2", "3", "4"}

// Intersection
Set<String> inter = new HashSet<>(a);
inter.retainAll(b);  // {"2", "3"}

// Difference
Set<String> diff = new HashSet<>(a);
diff.removeAll(b);  // {"1"}

Internal Implementation¶

• Backed by a HashMap<E, Object> where every value is a static PRESENT object.
• All HashMap properties apply (load factor, treeification, etc.).

Java: ConcurrentHashMap¶

Declaration¶

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(1000);
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(1000, 0.75f, 16);
// Third arg: concurrencyLevel (estimated concurrent writers; hint only)

Key Differences from HashMap¶

Atomic Operations¶

// All of these are atomic (thread-safe compound operations):
map.putIfAbsent("key", 1);
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
map.merge("key", 1, Integer::sum);

Bulk Parallel Operations (Java 8+)¶

// Parallel forEach with parallelism threshold
map.forEach(10_000, (key, value) -> {
    System.out.println(key + ": " + value);
});

// Parallel search: returns first match or null
String found = map.search(10_000, (key, value) ->
    value > 90 ? key : null
);

// Parallel reduce
int total = map.reduceValues(10_000, Integer::sum);

The long parameter is the parallelism threshold: if the map has more elements than this, operations run in parallel using the ForkJoinPool.

Python: dict¶

Declaration and Initialization¶

# Literal
d = {"alice": 95, "bob": 82}

# Constructor
d = dict(alice=95, bob=82)
d = dict([("alice", 95), ("bob", 82)])

# Comprehension
d = {k: v for k, v in zip(keys, values)}

# fromkeys (all values same)
d = dict.fromkeys(["a", "b", "c"], 0)  # {"a": 0, "b": 0, "c": 0}

Core Methods¶

Internal Implementation¶

• Open addressing with probing (not chaining).
• Hash table stores indices into a compact array of (hash, key, value) tuples.
• Insertion order preserved since Python 3.7 (language guarantee).
• Load factor threshold: 2/3 (~0.67).
• Growth: Approximately 2x (to next power of 2, times 2/3 threshold).
• Hash randomization: Hash seed randomized per process (since Python 3.3) to prevent hash-flooding attacks. Set PYTHONHASHSEED=0 for deterministic behavior.

Key Requirements¶

Keys must be hashable: implement __hash__() and __eq__(). - Built-in hashable types: int, float, str, bytes, tuple (if all elements are hashable), frozenset, None. - Not hashable: list, dict, set, bytearray.

collections Module Extensions¶

from collections import defaultdict, OrderedDict, Counter

# defaultdict: auto-creates missing keys with a factory
dd = defaultdict(list)
dd["key"].append(1)  # No KeyError

# Counter: frequency counting
c = Counter("aabbbcccc")
c.most_common(2)  # [('c', 4), ('b', 3)]

# OrderedDict: remembers insertion order (mostly superseded by dict in 3.7+)
# Still useful for: move_to_end(), equality considers order

Python: set¶

Declaration and Initialization¶

s = {1, 2, 3}
s = set([1, 2, 3])
s = set()  # Empty set (NOT {}, which is an empty dict)
fs = frozenset([1, 2, 3])  # Immutable set (hashable, usable as dict key)

Core Methods¶

Set Operations¶

Comparison Table¶