Two-Table Cuckoo Hashing Trace

Description

Trace insertion evictions, lookups and deletion in two fixed-size integer-key cuckoo tables using h1(k)=k mod m and h2(k)=floor(k/m) mod m; a kick limit rolls back the insertion and signals rehash-needed, without automatic resizing or hash-quality guarantees.

Cuckoo hashing gives each key two candidate table positions. Insertion can displace a resident key to its alternate position; a cycle or displacement limit can require rebuilding the table with different hashes. A trace makes those moves and membership outcomes visible.^[1]

When to use this tool

Use this tool when you need the stated calculation or classification with explicit inputs, intermediate evidence, and boundary conventions.

How to use the tool and how it works

Supply tableSize, maximumKicks, operations in the field shapes below.
Run the calculation. Correct format, shape, range, or undefined-statistic errors before interpreting a result.
Read tables, trace, size. Use the conventions below.

Use two fixed hashes, key modulo tableSize and floor(key/tableSize) modulo tableSize. Insert by alternating displacement between tables, and support direct lookup and deletion at both candidate slots. If maximumKicks is exhausted, restore both tables and report rehash-needed with attempted moves.^[2]

Input field	Meaning and units	Accepted input
tableSize	Slots in each of two tables.	Required. Safe integer; minimum 1; maximum 64.
maximumKicks	Maximum alternating placement attempts for each insertion.	Required. Safe integer; minimum 1; maximum 128.
operations	Operations	Required. Array of Object; no unknown keys.; minimum items 1; maximum items 128.
operations[].operation	Operation	Required. Text; one of "insert", "lookup", "delete".
operations[].key	Key	Required. Safe integer; minimum 0; maximum 9007199254740991.

Output field	Interpretation	Returned shape
tables	Tables	Required. Object; no unknown keys.
tables.first	First	Required. Array of Safe integer; minimum 0; maximum 9007199254740991. or Null.; minimum items 1; maximum items 64.
tables.second	Second	Required. Array of Safe integer; minimum 0; maximum 9007199254740991. or Null.; minimum items 1; maximum items 64.
trace	Trace	Required. Array of Object; no unknown keys.; minimum items 1; maximum items 128.
trace[].operation	Operation	Required. Text; one of "insert", "lookup", "delete".
trace[].key	Key	Required. Safe integer; minimum 0; maximum 9007199254740991.
trace[].outcome	Outcome	Required. Text; one of "inserted", "already-present", "present", "absent", "removed", "rehash-needed".
trace[].moves	Attempted displacements, including moves rolled back on rehash-needed.	Required. Array of Object; no unknown keys.; maximum items 128.
trace[].moves[].table	One-based table number: first is 1 and second is 2.	Required. Safe integer; minimum 1; maximum 2.
trace[].moves[].slot	Zero-based slot in that table.	Required. Safe integer; minimum 0; maximum 63.
trace[].moves[].incomingKey	Incoming Key	Required. Safe integer; minimum 0; maximum 9007199254740991.
trace[].moves[].evictedKey	Evicted Key	Required. Safe integer; minimum 0; maximum 9007199254740991. or Null.
size	Number of successfully stored distinct keys.	Required. Safe integer; minimum 0; maximum 128.

json

{
  "input": {
    "tableSize": 5,
    "maximumKicks": 10,
    "operations": [
      {
        "operation": "insert",
        "key": 12
      },
      {
        "operation": "insert",
        "key": 17
      },
      {
        "operation": "insert",
        "key": 8
      },
      {
        "operation": "lookup",
        "key": 12
      },
      {
        "operation": "delete",
        "key": 17
      },
      {
        "operation": "lookup",
        "key": 17
      }
    ]
  },
  "output": {
    "tables": {
      "first": [
        null,
        null,
        null,
        8,
        null
      ],
      "second": [
        null,
        null,
        12,
        null,
        null
      ]
    },
    "trace": [
      {
        "operation": "insert",
        "key": 12,
        "outcome": "inserted",
        "moves": [
          {
            "table": 1,
            "slot": 2,
            "incomingKey": 12,
            "evictedKey": null
          }
        ]
      },
      {
        "operation": "insert",
        "key": 17,
        "outcome": "inserted",
        "moves": [
          {
            "table": 1,
            "slot": 2,
            "incomingKey": 17,
            "evictedKey": 12
          },
          {
            "table": 2,
            "slot": 2,
            "incomingKey": 12,
            "evictedKey": null
          }
        ]
      },
      {
        "operation": "insert",
        "key": 8,
        "outcome": "inserted",
        "moves": [
          {
            "table": 1,
            "slot": 3,
            "incomingKey": 8,
            "evictedKey": null
          }
        ]
      },
      {
        "operation": "lookup",
        "key": 12,
        "outcome": "present",
        "moves": []
      },
      {
        "operation": "delete",
        "key": 17,
        "outcome": "removed",
        "moves": []
      },
      {
        "operation": "lookup",
        "key": 17,
        "outcome": "absent",
        "moves": []
      }
    ],
    "size": 2
  }
}

Limitations and assumptions

The tool does not actually rehash, randomize hash functions, or provide production hashing performance guarantees. Table numbers in moves are one-based and slots zero-based. A global 4,096-kick work budget can reject a run.
The field tables state structural bounds; cross-field constraints and bounded search or output budgets also apply. Unknown keys are rejected where the object contract disallows them. Input errors are distinct from null fields and deliberate invalid controls in a successful output.

Alternative or Complementary methods

Choose the statistic according to the question and data conventions. Inspect the supplied series or matrix and the stated assumptions before comparing outputs from implementations with different defaults.

References

Pagh and Rodler (2001): Cuckoo Hashing — BRICS, University of Aarhus
Tool behavior and example: Two-Table Cuckoo Hashing Trace Tool — tool.io

Similar or alternative tools

Hash table collision workload
Solve residues for the caller's toy linear modular hash, construct distinct planted colliding integer keys and bounded noise, then retain bucket counts and every actual collision pair; no cryptographic collision claim.
Random Bloom Filter Workload Generator
Deduplicate a supplied string universe, sample a distinct insertion set and controlled present/absent query pools, and delegate deterministic Bloom responses; report exact labels and observed false positives separately from the core's 8-significant-digit ideal-hash probability approximation, not a guaranteed error rate.