Experiments and implementations · Intermediate

Testing hash tables across collision workloads

Compare equal-result dictionary workloads and observe how forced hash collisions affect equality-call counts.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Count comparisons before timing
  2. Preserve the equality and hashing contract
  3. Reset counters after construction
  4. Collisions should not change the answer
  5. Vary workload size and key cost
  6. Record the limits of the observation
  7. Ask Logeia about this articleCheck your understanding

Count comparisons before timing

Average hash-table performance depends on assumptions about keys and hashing. Store three hundred custom keys in a Python dictionary and look them up using separate but equivalent key objects. One set uses integer hashes; the other deliberately returns zero for every key. Both return the same squared integer values. Instead of relying first on wall-clock timing, count equality-method calls, which expose part of the work induced by collisions. The count is implementation-specific, but it supplies an observable quantity less directly affected by unrelated machine load. This is a controlled local experiment, not a claim about the latency of a production dictionary workload.

Preserve the equality and hashing contract

Keys with the same value compare equal, and equivalent keys within a trial produce the same hash. Returning a constant hash does not violate that contract; unequal keys are allowed to collide. This differs from letting an equal key produce inconsistent hashes. Do not mutate the value after insertion, because changing hashing-related state can make the mapping unusable. The program also avoids mixing the two collide settings inside one dictionary. A controlled switch between trials is not permission to violate consistency among keys coexisting in a table. Correctness of the key definition must be established before interpreting additional lookup work.

Reset counters after construction

Reset the equality counter after constructing the mapping so insertion work is not mixed into the lookup observation. Lookups use new equivalent Key instances instead of reusing the inserted object identities. Assert that every returned value matches an independently constructed list of squares, and include an unsuccessful lookup for 999. Missing-key work can differ from successful lookup work, so document their presence rather than comparing unmatched workloads. A smaller counter is not an improvement if returned results or the number of attempted operations differ. The assertions establish equal logical work before the counters are compared.

Python 3
class Key:
    comparisons = 0
    def __init__(self, value, collide):
        self.value, self.collide = value, collide
    def __hash__(self):
        return 0 if self.collide else hash(self.value)
    def __eq__(self, other):
        Key.comparisons += 1
        return isinstance(other, Key) and self.value == other.value

def trial(collide):
    mapping = {Key(i, collide): i * i for i in range(300)}
    Key.comparisons = 0
    answers = [mapping[Key(i, collide)] for i in range(300)]
    assert answers == [i * i for i in range(300)]
    assert Key(999, collide) not in mapping
    return Key.comparisons
normal, collision = trial(False), trial(True)
assert collision > normal
print({"normal_equality_calls": normal, "colliding_equality_calls": collision})

Collisions should not change the answer

A dictionary distinguishes colliding keys by equality, so both trials return the same correct values here. Treating a matching hash as complete key identity would be a correctness defect rather than a performance improvement. Candidate probing, resizing and precise equality counts depend on the language implementation and version. The experiment deliberately avoids fixing one exact count as a universal answer. It asserts only that the intentionally colliding trial performs more equality calls than the normal trial on this workload. That observation does not reconstruct every aspect of the table’s internal algorithm or establish a bound for unrelated implementations.

Vary workload size and key cost

Repeat both trials with thirty, three hundred or one thousand entries and recheck equal results each time. If equality itself scans long strings, its unit cost is not necessarily constant. Separate hashing, equality, allocation and table growth to understand assumptions hidden by a casual average constant-time description. A service processing externally chosen keys must also consider whether a poor distribution can be induced by its inputs. Nevertheless, this artificial Key class does not measure the attack resistance of built-in string hashing. It isolates one mechanism and cannot substitute for analysis of the actual key type and runtime used by an application.

Record the limits of the observation

Record Python version, entry count, successful versus unsuccessful lookup counts and observed equality calls. If adding a timing measurement, match whether construction is included and inspect variation across repeated runs. Three hundred entries keep this example small; that number is neither a capacity recommendation nor a performance threshold. Updating an instrumentation counter itself adds runtime work, so an instrumented custom key is not equivalent to an uninstrumented built-in key for timing purposes. Report logical correctness, measurement overhead and implementation-dependent results separately. These distinctions let another reader reproduce the mechanism without treating a local counter as a universal benchmark.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path