Using HashSets in Different Programming Languages

Mechanism

A HashSet stores each element by computing hash(key) mod tableSize to pick a bucket directly, so membership testing never has to scan the collection — it jumps straight to the slot where the element must live (or a short chain/probe sequence off that slot) and compares only against what's there. Every language's "set" type is this same bucket-array-plus-hash-function machine wearing different syntax; Go is the outlier because it exposes the underlying hash table (map[T]bool) instead of a dedicated set type.

Recognize the pattern

Reach for a HashSet when the task talks about: "has this been seen before", "remove duplicates", "does X exist in the collection", "unique elements only", or "check membership fast without caring about order". If the wording instead says "in sorted order", "k-th smallest", or "range between a and b", that's a signal for an ordered structure (TreeSet / sorted array), not a plain HashSet.

Brute force to optimal

Brute force — array/list scan: keep elements in a plain array; to check membership or insert-if-absent, linearly scan every existing element. Insert-if-absent costs O(n) per call because you must rule out a duplicate first; over n insertions that's O(n²) total.

Optimal — hash table: compute one hash, jump to the bucket, compare against the (typically 0–2) elements already there. Insert-if-absent becomes O(1) average; over n insertions, O(n) total. The trade is memory overhead (empty slots, hash codes) for that speed.

Complexity, derived

Time. With n elements in a table of m buckets, the load factor is α = n/m. If the hash function distributes keys uniformly, the expected number of elements sharing any bucket is α, so an average lookup/insert/delete does 1 (index computation) + O(α) (compare against bucket contents) operations. The two resize policies below both bound α by a constant, which is what makes lookup/insert/delete O(1) average — they just pick different constants and growth rules. Java's HashMap/HashSet doubles the table and rehashes whenever n exceeds α·m with the default threshold α = 0.75, keeping load factor capped around 0.75. C#'s HashSet<T>/Dictionary use a different rule: they grow (to the next prime size, not a strict doubling) only once the entries[] array is fully exhausted — i.e., an effective load factor near 1.0, not 0.75. Both are still O(1) average because both keep α bounded by *some* constant; the constant and the trigger condition just differ. Worst case: if every key collides into one bucket (adversarial input or a broken hash function), the bucket degenerates into a linear list/chain of n elements, so lookup/insert/delete cost O(n) (Java's HashMap mitigates this since Java 8 by treeifying long chains into a red-black tree, giving O(log n) worst case for that bucket; C#'s HashSet does not treeify). Best case is O(1) when collisions are near zero.

Space. Storing n elements needs O(n) for the elements themselves plus O(m) for the (mostly empty, in Java's case) bucket array, and since m is kept proportional to n, total space is O(n). During a resize, the old table and new table briefly coexist while entries are rehashed, so peak space spikes to O(m) extra — i.e., O(n) amortized but a transient ~O(2n) during the copy.

Worked example

Insert [4, 7, 4, 2, 7, 9] into a HashSet with an initial table of m = 4 buckets (index = value mod 4):

Result: 4 unique elements from 6 inputs, 6 hash computations, 0 chain collisions in this trace (each value landed on a distinct occupied/empty bucket).

import java.util.*;

public class DedupeExample {
    public static void main(String[] args) {
        int[] nums = {4, 7, 4, 2, 7, 9};
        Set<Integer> seen = new HashSet<>();
        List<Integer> unique = new ArrayList<>();
        for (int n : nums) {
            if (seen.add(n)) {          // add() returns false if n was already present
                unique.add(n);
            }
        }
        System.out.println(unique);      // [4, 7, 2, 9]
    }
}

Pitfalls

• Mutable keys: mutating an object after inserting it (Java/Python/JS custom objects) changes its hash, so it becomes unfindable in its old bucket — silent "lost" elements.
• Missing/inconsistent hashCode+equals (Java) or __hash__/__eq__ (Python): without overriding both, two logically-equal objects land in different buckets or in the same bucket but never compare equal, breaking deduplication.
• Assuming iteration order: Java HashSet, Python set, and Go map iteration order is unspecified (Go's is deliberately randomized per run) and can change across JVM/runtime versions or after a resize — code that depends on insertion order silently breaks (use LinkedHashSet in Java). The exception is JavaScript: the ECMAScript spec guarantees Set iterates in insertion order, so relying on order there is safe and version-independent.
• Python unhashable elements: mutable built-ins (list, dict, set) cannot be set elements — they raise TypeError: unhashable type; convert to tuple/frozenset first.
• Go's map[T]bool false-vs-absent ambiguity: a missing key and a key mapped to false look the same on a plain value read; always use the two-value form v, ok := m[k] to test presence.
• Degenerate hash functions: a poor or attacker-controlled hash (hash-flooding) collapses many keys into one bucket, turning O(1) into O(n) per op — mitigated in Java 8+ by treeifying long chains, but not in C#'s HashSet, which stays a plain chain.

When to use / when not

Use a HashSet when you need O(1) average membership/insert/delete and don't care about order — deduplication, "seen before" checks, set algebra (union/intersect via two HashSets).

Avoid it, prefer a TreeSet / sorted array when you need sorted iteration, range queries ("all elements between 10 and 50"), or floor/ceiling lookups — those cost O(log n) in a balanced BST-backed TreeSet but are not supported at all by a hash table's O(1) contract. TreeSet trades the O(1) average for a guaranteed O(log n) worst case with ordering, which is worth it whenever order matters more than raw speed.

Takeaways

• A HashSet's speed comes from computing an index, not from any clever comparison — that's what makes it O(1) average but order-less.
• Load factor is the dial that trades memory for collision rate; each language resizes on its own trigger (Java at α≈0.75, C# when entries[] fills) but all keep α bounded so average-case O(1) holds over time.
• Across languages the API name changes but the bucket-array-plus-hash mechanism is identical; Java and C# both chain collisions (C# via an explicit Next-linked entries array, Java via linked/tree bins) while Python probes open addresses; Go just makes you build it yourself with map[T]bool. The classic trade between the two engines: open addressing wins cache locality but needs tombstones on delete and must keep α < 1; chaining tolerates α ≥ 1 and deletes cleanly, at pointer-chasing cost.

Recall: why does inserting a mutable object into a HashSet and then changing one of its hashed fields make the object effectively unfindable?

Derived from first-principles analysis of hash table load factor and resizing; language API details cross-checked against java.util.HashSet, Python set, std::unordered_set, JS Set, .NET's HashSet<T>/Dictionary<TKey,TValue> source (buckets[]/entries[]/Next chaining), and Go's map documentation.