Hashing and Hash Tables Questions

Direct answer

Hash-table lookup, insertion, and deletion are O(1) on average, assuming keys spread roughly evenly
across buckets, but they degrade to O(n) in the worst case when many keys land in the same bucket,
because that bucket then behaves like a plain list you have to scan linearly.

Structured elaboration

Where the O(1) average comes from. If n keys spread uniformly across m buckets, each bucket holds
about n/m entries, the load factor, kept bounded by resizing. A lookup does one O(1) hash computation
plus a scan of that one bucket's roughly-constant-length contents.

What forces the worst case. Three distinct triggering conditions, each real:

1. A degenerate/weak hash function that maps many real keys to the same bucket regardless of
   intent (e.g. only reading the first character of a string key when most keys share a prefix).
2. An adversary who controls the keys. Even a well-designed general-purpose hash function has
   some set of inputs that all collide (pigeonhole principle guarantees this), and if an attacker
   can discover or brute-force that set (this is exactly what the 2011 hash-flooding disclosures
   exploited across PHP, Python, Ruby, and other languages: PHP and Perl specifically used the
   DJBX33A hash for this, while Python and Ruby each had their own similarly deterministic,
   unseeded string hash broken the same way), they can deliberately force every key into one
   bucket, turning every operation into an O(n) scan, a genuine denial-of-service vector (the mitigations are a deep topic in their own right).
3. A load factor left unbounded, i.e. the implementation simply never resizes.

How modern implementations mitigate this. Java's HashMap (since Java 8) treeifies a bucket
once its chain grows past 8 entries in a sufficiently large table, converting that one bucket's linked
list into a small balanced red-black tree, capping that bucket's worst case at O(log n) instead of
O(n), while leaving every other, non-degenerate bucket untouched. Python and other languages instead
lean on hash randomization (a per-process secret seed mixed into string hashing) so an attacker
cannot predict which inputs will collide without also knowing the secret seed, closing off attack
class 2 above without changing the underlying data structure at all.

Worked example

Concretely, for a chaining table with 8 buckets: if 100 keys spread perfectly evenly, each bucket
holds 12.5 entries (average-case O(1) relative to a further-scaled table, i.e. still small and
constant as the table resizes to keep this bounded). If instead all 100 keys were engineered to hash
into bucket 0, that one bucket now holds a 100-entry list and a lookup for the 100th key inserted
there requires scanning all 100 (or, in Java 8+, only up to a red-black tree's O(log 100) is approx 7
comparisons instead, once treeification's threshold of 8 is crossed).

Trade-offs and pitfalls

Stating "hash tables are O(1)" without qualification is the single most common shallow answer to this
question; a strong answer immediately volunteers the word "average-case" and can name at least one
concrete mechanism that breaks it. A second-level pitfall is thinking treeification "fixes" the
worst case universally, it only bounds the cost of ONE pathological bucket to O(log(bucket size)),
it does not prevent an attacker from still degrading overall throughput by forcing every key into
that single treeified bucket, it just caps how bad that specific bucket's cost gets.

Direct answer

An exact hash map gives perfect counts but its memory grows with the number of distinct keys ever seen, which for things like user ids or token n-grams can exceed what a feature extraction job can afford. Count-Min Sketch (CMS) and Lossy Counting both trade a bounded, quantified error for a memory footprint that does not grow with the number of distinct keys, but they bound different things and fail differently.

Structured elaboration

The width $w$ and depth $d$ of a Count-Min Sketch are set directly from the target accuracy $\epsilon$ and confidence $\delta$:

w = ceil(e / epsilon)      # e is Euler's number, not a variable
d = ceil(ln(1 / delta))

For $\epsilon = 0.001$ (error at most 0.1% of the stream length) and $\delta = 0.01$ (99% confidence): $w = \lceil e/0.001 \rceil = 2719$ and $d = \lceil \ln(1/0.01) \rceil = 5$, so 13,595 integer counters total, roughly 54 KB at 4 bytes each. That footprint is fixed whether the stream has 10,000 or 10,000,000 distinct tokens; an exact hash map over 2,000,000 distinct tokens, by contrast, easily costs 100+ MB just in key and bucket overhead.

Lossy Counting (Manku-Motwani) instead partitions the stream into buckets of width $\lceil 1/\epsilon \rceil$ and keeps a table of (item, estimated count, max possible error), dropping any item whose estimate-plus-error falls below the current bucket id. It is built specifically to answer "which items occur with frequency above support threshold s", not "what is the count of this arbitrary key", which is why it forgets rare items instead of estimating them.

Worked example

Suppose a feature-extraction job is computing document-frequency-style features for tokens in a stream of 200,000 events with an effective vocabulary that could reach millions of rare tokens (typos, ids, one-off strings). With $\epsilon=0.001, \delta=0.01$ the CMS above uses a fixed ~54 KB and, for any token, returns a count guaranteed not to overshoot the truth by more than $0.001 \times 200{,}000 = 200$ with 99% confidence, regardless of how many distinct rare tokens showed up. An exact hash map over the same stream would need one entry per distinct token actually seen; if 500,000 of those are one-off strings, that is 500,000 map entries the pipeline has to hold, most of which are used exactly once.

Trade-offs and pitfalls

Use the exact hash map when the key space is small and bounded (a fixed categorical vocabulary) or when the count feeds a hard business decision that cannot tolerate error (billing, quota enforcement, or a threshold like "flag only if seen fewer than 3 times" where an off-by-epsilon-N answer could flip the decision). Use Count-Min Sketch when you need point queries on arbitrary keys and want cheap cross-shard merging in a distributed pipeline (each worker keeps its own sketch, merge at aggregation time). Use Lossy Counting when the actual goal is finding the heavy hitters above a threshold and you can afford to lose visibility into everything else, and you are not merging across many independent shards. A common mistake is chaining an over-estimating structure (CMS) into a threshold rule written for exact counts without re-deriving the threshold to account for the one-sided bias; another is assuming Lossy Counting can serve as a general point-query structure the way CMS can, then being surprised when a previously-frequent-turned-rare key silently vanishes from the table.

Approach

Quadratic probing is open addressing (every entry lives directly in one flat array, no linked chains) where a collision at the home slot is resolved by trying home + 1^2, home + 2^2, home + 3^2, ... modulo the table capacity, instead of the fixed stride double hashing would use. The quadratic step spreads consecutive colliding keys apart quickly, which avoids the long runs of adjacent occupied slots that plain linear probing (home + 1, home + 2, ...) produces (a problem known as primary clustering). Deletes cannot just null out a slot, because a later key may have probed past it; a tombstone marker keeps get probing through a deleted slot while letting put reclaim it.

Code (Java)

public class QuadraticProbingMap {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity, size, used;

    public QuadraticProbingMap(int capacity) {
        this.capacity = capacity;
        this.keys = new Object[capacity];
        this.values = new Object[capacity];
    }

    private int home(Object key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }

    public void put(String key, Integer value) {
        if ((double) (used + 1) / capacity > 0.6) resize();
        int base = home(key), firstTombstone = -1;
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) {
                int target = (firstTombstone != -1) ? firstTombstone : slot;
                if (keys[target] == null) used++;
                keys[target] = key; values[target] = value; size++;
                return;
            } else if (keys[slot] == TOMBSTONE) {
                if (firstTombstone == -1) firstTombstone = slot;
            } else if (keys[slot].equals(key)) {
                values[slot] = value;
                return;
            }
        }
        throw new IllegalStateException("table full, resize invariant violated");
    }

    public Integer get(String key) {
        int base = home(key);
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) return null;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) return (Integer) values[slot];
        }
        return null;
    }

    public boolean remove(String key) {
        int base = home(key);
        for (int i = 0; i < capacity; i++) {
            int slot = (int) (((long) base + i * i) % capacity);
            if (keys[slot] == null) return false;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) {
                keys[slot] = TOMBSTONE; values[slot] = null; size--;
                return true;
            }
        }
        return false;
    }

    private void resize() {
        Object[] oldKeys = keys, oldValues = values;
        capacity = nextPrime(capacity * 2);
        keys = new Object[capacity]; values = new Object[capacity];
        size = 0; used = 0;
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) put((String) oldKeys[i], (Integer) oldValues[i]);
        }
    }

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    private static int nextPrime(int n) {
        int candidate = Math.max(n, 2);
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

    public int size() { return size; }
    public int capacity() { return capacity; }

    public static void main(String[] args) {
        QuadraticProbingMap m = new QuadraticProbingMap(11);
        m.put("x", 1); m.put("y", 2); m.put("z", 3);
        System.out.println("get x -> " + m.get("x"));
        System.out.println("get missing -> " + m.get("nope"));
        m.remove("y");
        System.out.println("get y after remove -> " + m.get("y"));
        m.put("w", 4);
        System.out.println("get w -> " + m.get("w"));
        System.out.println("get x still resolves past tombstone -> " + m.get("x"));
        for (int i = 0; i < 25; i++) m.put("k" + i, i * 5);
        System.out.println("size -> " + m.size() + " capacity -> " + m.capacity());
        boolean allCorrect = true;
        for (int i = 0; i < 25; i++) if (!Integer.valueOf(i * 5).equals(m.get("k" + i))) allCorrect = false;
        System.out.println("all 25 post-resize keys correct -> " + allCorrect);
        System.out.println("z survived resize -> " + (m.get("z") == 3));
        System.out.println("y stays deleted after resize -> " + (m.get("y") == null));
    }
}

Output (compiled with javac and executed as shown; starting capacity 11):

get x -> 1
get missing -> null
get y after remove -> null
get w -> 4
get x still resolves past tombstone -> 1
size -> 28 capacity -> 47
all 25 post-resize keys correct -> true
z survived resize -> true
y stays deleted after resize -> true

Key points

• Collision resolution choice: quadratic probing was chosen over linear probing specifically to avoid primary clustering (long runs of adjacent full slots that make every new insertion near that run progressively more expensive), at the cost of a subtler risk covered below. It was chosen over chaining because the goal here is to keep every entry inside one contiguous array, which is more cache-friendly (fewer pointer chases) and avoids per-entry node allocation.
• Tombstones on delete: remove marks the slot with TOMBSTONE rather than null, so get keeps probing past it (confirmed above: x still resolves after y's slot becomes a tombstone), while put is free to reuse that slot for a new key (w reuses y's old slot).
• Resize and rehashing: capacity grows to the next prime at least double the old size once used (live entries plus tombstones) crosses 60% of capacity; every live entry is walked and reinserted, and tombstones are dropped in the process, reclaiming their space.
• Memory implications: open addressing stores keys and values directly in two flat arrays with no per-entry node object and no next-pointer, which is more memory-efficient per live entry than chaining (which pays for a node object per entry) as long as the load factor is kept reasonably low; the cost is that the array itself must always be sized somewhat larger than the live entry count (here, never let past 60% full), whereas chaining can, in principle, run at a load factor above 1.0 with only a linear degradation in bucket length.

Complexity

• Average case, put/get/remove: (O(1)), given a good hash and the load factor kept under the resize threshold.
• Worst case: (O(n)), a table with heavy clustering or many tombstones can force a long probe sequence.
• Resize: (O(n)) when triggered, but (O(1)) amortized per insert, by the same doubling argument as any doubling hash table: total rehashing work across all resizes up to (n) inserts is bounded by a constant multiple of (n).

Edge cases and pitfalls

• The quadratic-probing coverage limitation: for home + i^2 mod capacity with a prime capacity, i and capacity - i produce the same residue, so the probe sequence for i = 0, 1, 2, ... visits only about half of the table's slots before repeating, not all of them. A load factor of 0.6 is inside the danger zone for this: it is possible (though not certain, and it did not occur in the run above) for put to fail to find a free slot even though the table is well under 100% full, because the reachable half happens to be occupied. The safer engineering choice is either to cap the load factor nearer 0.5 for this exact probing formula, or use a probing sequence proven to cover every slot, such as triangular-number probing (i(i+1)/2) on a power-of-two-sized table.
• Deleting then reusing a slot for an unrelated key: must not break lookups for keys whose probe sequence passes through that slot (verified above).
• A key that was never inserted: the probe sequence hits an empty (null) slot and both get and remove correctly report absence.
• A table saturated with tombstones but few live entries: resizing on used, not size, prevents probe sequences from silently degrading even when the map looks small from the outside.

Direct answer

Since a raw Python dict cannot be a set/dict key (dicts are unhashable, by design, because
they are mutable), convert each record to something hashable before deduping: a canonical
serialization (deterministic JSON with sorted keys), a sorted tuple of its items, or a stable
content fingerprint (a SHA-256 digest of the canonical form). The fingerprint approach is
usually best in an ETL (extract, transform, load) pipeline, since it gives a fixed-size, directly
comparable key regardless of record size, but all three require deliberate handling of key order, floating-point
representation, and missing fields, or dedup will silently under- or over-merge records.

Structured elaboration

Why the dict itself cannot be a key. Python requires a key to be hashable, and hashability
requires immutability, since a mutable object's hash could change after it is inserted, which
would break the exact bucket-integrity guarantee hash-based lookup depends on (the same failure
mode discussed for mutable hash keys generally). A plain dict is mutable, so Python disallows
it as a key outright, raising a TypeError rather than allowing a subtly broken key.

Canonical serialization (deterministic JSON). Serialize each record with sort_keys=True so
two dicts with the SAME content but different key insertion order produce the IDENTICAL JSON
string, then use that string (or its hash) as the dedup key. This alone handles key-order
independence but does nothing yet about floating-point noise or missing-versus-null fields; those
need explicit normalization before serialization.

Sorted tuples. Convert sorted(record.items()) into a tuple, which is hashable as long as
every value inside it is also hashable (a nested dict or list value is NOT, so this approach
needs a recursive conversion for nested structures, which canonical JSON serialization handles
more naturally since JSON is already a recursive format).

Stable fingerprints (SHA-256). Hash the canonical serialization with a cryptographic digest
to get a fixed-size, directly comparable identifier, useful when records are large (the
fingerprint is small and constant-size regardless of record size) or when you want to persist the
dedup key separately from the record itself.

The three edge cases the question calls out, and how to actually handle each.

• Ordering: solved by sort_keys=True in JSON serialization, or by sorting the tuple's items
  before hashing; without this, two logically identical records with differently-ordered keys
  fingerprint differently and dedup silently fails to merge them.
• Floating point: two records can represent the SAME business value with different floating-
  point bit patterns (upstream arithmetic noise, different serialization precision), which
  fingerprint DIFFERENTLY unless floats are rounded to a fixed, deliberately chosen precision
  before serialization; skipping this rounding step causes dedup to under-merge (treat identical
  records as distinct).
• Missing fields: a field entirely ABSENT from a dict and the same field explicitly set to
  null/None are different things to a naive JSON serializer (json.dumps omits an absent key
  entirely but writes null for an explicit None), so normalize by explicitly filling every
  expected field via record.get(field, default) before serializing, or two logically identical
  records (one with a field omitted, one with it explicitly null) will fingerprint differently and
  fail to dedup.

Performance and correctness. Fingerprinting is O(record size) per record, done once; the
subsequent dedup itself is then an ordinary O(1) average hash-set membership check per record,
same as any other hash-based dedup. Correctness depends entirely on how faithfully the
normalization step (rounding, explicit field-filling, key sorting) captures "these two records
should count as the same," which is a judgment call specific to the data, not something the
serialization mechanism decides for you.

Worked example

import hashlib, json

fields = ["user_id", "amount", "region", "notes"]
a = {"user_id": "u1", "amount": 19.99, "region": "US", "notes": None}
b = {"region": "US", "notes": None, "amount": 19.99, "user_id": "u1"}       # reordered keys
c = {"user_id": "u1", "amount": 19.99, "region": "US"}                       # 'notes' key ABSENT
d = {"user_id": "u1", "amount": 19.99000000000001, "region": "US", "notes": None}  # float noise

# Confirm the premise: a raw dict cannot be a set element at all.
try:
    literal_set = {a}
except TypeError as e:
    print("TypeError on raw dict in a set literal:", e)

def canonical_fingerprint(record, expected_fields, ndigits=6):
    normalized = {}
    for field in expected_fields:
        value = record.get(field, None)
        if isinstance(value, float):
            value = round(value, ndigits)
        normalized[field] = value
    canonical_json = json.dumps(normalized, sort_keys=True)
    return hashlib.sha256(canonical_json.encode()).hexdigest()

print(canonical_fingerprint(a, fields) == canonical_fingerprint(b, fields))
print(canonical_fingerprint(a, fields) == canonical_fingerprint(c, fields))
print(canonical_fingerprint(a, fields) == canonical_fingerprint(d, fields))

# Confirm rounding is doing real work: a naive fingerprint WITHOUT rounding
# should fail to match a and d, even though the rounded version matches.
def naive_fingerprint(record, expected_fields):
    normalized = {f: record.get(f, None) for f in expected_fields}
    return hashlib.sha256(json.dumps(normalized, sort_keys=True).encode()).hexdigest()

print(naive_fingerprint(a, fields) == naive_fingerprint(d, fields))

Running this: attempting {a} (a literal set containing a plain dict) raises
TypeError: cannot use 'dict' as a set element (unhashable type: 'dict'), confirming the
premise. Record a (natural key order) and record b (identical content, shuffled key order)
fingerprint IDENTICALLY (True). Record c, where the notes key is entirely absent rather than
explicitly None, ALSO fingerprints identically to a (True), because both normalize through
record.get("notes", None) to the same value. Record d, where amount carries floating-point
noise (19.99000000000001 instead of 19.99), fingerprints identically to a (True) once
rounded. The final line confirms rounding is actually load-bearing: the naive (unrounded)
fingerprint of a and d comes out False, a false negative that would leave two logically
identical records undeduped if the rounding step were skipped.

Trade-offs and pitfalls

• Rounding precision for floats is a business decision, not a technical default. Too coarse a
  rounding (few digits) can merge genuinely different values; too fine (many digits) can leave
  float noise unresolved. Pick the precision that matches the field's real-world meaningful
  granularity (for a currency amount, cents is usually the right granularity).
• Silently defaulting missing fields to None can mask real data-quality problems if a field
  is SOMETIMES missing due to an upstream bug rather than legitimately absent; log or flag records
  that rely on the default rather than silently normalizing them away.
• Nested structures (a dict value containing another dict or a list) need the SAME
  normalization recursively applied, or a nested float or nested key-order difference reproduces
  the exact same bugs one level down.
• A fingerprint collision is theoretically possible but not the practical risk here: SHA-256's
  collision probability is negligible at any realistic ETL scale; the actual, common failure mode
  is a NORMALIZATION bug (missed rounding, missed default-fill, unsorted nested keys), not a hash
  collision.

Direct answer

Doubling capacity gives amortized O(1) insertion because the total cost of all the copying done across n insertions is bounded by a geometric series that sums to O(n), a standard aggregate-analysis argument. A smaller growth factor like 1.5x keeps the same asymptotic O(1) amortized guarantee but changes both constants in opposite directions: it wastes less memory right after a resize but does strictly more total copying over the table's lifetime, which is why memory-constrained services sometimes deliberately choose a smaller factor despite the extra copying cost.

Structured elaboration

Formal proof: doubling gives amortized O(1)

Use the aggregate method. Suppose the table starts at capacity $C_0$ and doubles every time it fills: $C_0, 2C_0, 4C_0, \dots$ After $n$ insertions, the table has resized $r = \lceil \log_2(n/C_0) \rceil$ times. Each resize at capacity $2^{i}C_0$ copies all $2^{i}C_0$ existing elements. The total copying work across all resizes is

a geometric series that telescopes to strictly less than $2n$, that is, $O(n)$ total copying work for $n$ insertions. Adding the $n$ direct insertion costs (O(1) each, O(n) total) gives total work $O(n)$ for $n$ insertions, so the AMORTIZED cost per insertion, total work divided by $n$, is $O(1)$, even though any single insertion that triggers a resize costs $O(n)$ in that instant.

Alternative growth factors: 1.5x versus 2x

The same argument holds for any growth factor $g > 1$: the geometric series still telescopes to $O(n)$ total copying, so amortized O(1) holds for ANY fixed $g>1$, not just doubling. What changes is the CONSTANT inside that O(1), in two opposite directions:

• Time constant: total copying work relative to $n$ scales with $\frac{g}{g-1}$. This is LARGER for smaller $g$: at $g=2$, the constant is 2 (copy up to 2x the final size in aggregate); at $g=1.5$, the constant is 3 (copy up to 3x). Smaller growth factors resize more often and do MORE total copying over the table's life.
• Space constant: right after a resize to capacity $gC$ holding $C$ elements, the table is only $1/g$ full. At $g=2$, that is 50% full (up to half the allocated capacity is temporarily wasted); at $g=1.5$, that is about 67% full (only about a third wasted). Smaller growth factors waste LESS peak memory.

So doubling buys a cheaper amortized time constant at the cost of wasting up to half the table's capacity right after a resize; a smaller factor like 1.5x wastes less memory at the cost of a larger total-copying constant over the table's lifetime.

When a smaller growth factor is preferable

For a memory-constrained service, many small maps held simultaneously, or a hard per-process memory limit such as embedded or high-density multi-tenant deployments, the up-to-50%-wasted peak capacity of doubling is a real, direct memory cost multiplied across every live table. Trading some extra copying work (a CPU cost, generally cheaper and more elastic than a hard memory ceiling) for a tighter worst-case memory bound is the right trade when memory, not CPU, is the binding constraint.

Worked example (10 million keys)

Target: insert 10,000,000 keys, keeping the load factor at or below 0.75 at all times, starting from an initial capacity of 16 and doubling.

Minimum capacity needed to hold 10,000,000 keys at a 0.75 load factor: $10{,}000{,}000 / 0.75 \approx 13{,}333{,}334$. The smallest power of two at or above that is $2^{24} = 16{,}777{,}216$. Starting from $2^4=16$ and doubling to $2^{24}$ takes exactly

Total copying work across those 20 resizes (summing the capacity at each resize: $16+32+64+\dots+2^{23}$) is $2^{24}-16 = 16{,}777{,}200$ element-copies, about 1.68x the final key count of 10,000,000, confirming the amortized O(1) bound concretely: roughly 1.68 copy-operations per insertion on average, despite 20 individual resize events, several of which each cost millions of copies in that single instant.

Mitigating long pause times in production

• Pre-size when the target is knowable: if 10,000,000 is known or well-estimated ahead of time, constructing the table at capacity $2^{24}$ directly eliminates all 20 resizes and their pauses, at the cost of allocating the full capacity up front even before it is needed.
• Incremental (lazy) resizing: instead of copying the entire old table in one atomic step, keep both the old and new tables alive during a transition window and migrate a bounded number of entries (a few buckets) on each subsequent operation, spreading one large pause into many tiny ones; this is how some production key-value stores avoid a single stop-the-world copy.
• Smaller growth factor: reduces the SIZE of the worst individual pause (each resize copies less, since resizes happen more often but at a smaller jump), trading a few large pauses for more numerous, smaller ones, useful when the tail latency of one huge pause matters more than the higher aggregate resize count.
• Segmented structures: a table built from independently-sized segments, adding a new segment instead of reallocating and copying the whole table, avoids the "copy everything" pattern altogether, at the cost of a slightly more complex lookup path (checking the right segment).

Trade-offs and pitfalls

• Treating "amortized O(1)" as meaning "every insertion is fast" is the most common misreading of this proof; the guarantee is about the AVERAGE over many insertions, individual resize-triggering insertions are genuinely $O(n)$ in that instant, exactly why production services with strict per-operation latency budgets need the mitigations above, not just the amortized guarantee.
• Choosing a growth factor without a specific memory or latency constraint driving the choice is arbitrary; the analysis above only tells you the shape of the trade-off, the right point on it depends on which resource, memory or CPU/pause time, is actually scarce for the specific service.