{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Strategy{{ resultsReady ? simulation.strategy_label : '—' }} Load{{ resultsReady ? formatRatio(simulation.metrics.load_factor) : '—' }} Visits{{ resultsReady ? simulation.metrics.visits : '—' }}

Hash placement visual unavailable.

Triangular quadratic probing uses offsets 0, 1, 3, 6… and requires a power-of-two table size.
Use 4, 8, or 16 buckets with triangular quadratic probing.
Use 1–12 lines: insert 9 Bravo, search 9, or delete 9. Keys range from -999 to 999.
Samples replace only the operation script.
{{ effectiveTraceStep }} / {{ operationCount }}
The summary, visual, chart, and ledgers all use this same canonical trace position.
Move through operations
The neutral default is off.
{{ show_hash_arithmetic ? 'Enabled' : 'Disabled' }}
StepOperationHomeVisitedEventExplanationCopy
Move the trace beyond the empty table to see visits.
{{ row.operation_index }}{{ row.operation_label }} {{ row.key }}{{ row.home }}{{ row.bucket }}{{ row.event_label }}{{ row.detail }}

The chart renderer is unavailable. Visit counts remain available in the bucket ledger.

BucketContentsEntriesVisitsCopy
{{ row.index }}{{ row.contents }}{{ row.entries }}{{ row.visits }}
Strategy notes

{{ note.title }}

{{ note.body }}

BST Operations Simulator Trace BST operations from insertion and search through deletion and traversal across ordinary, AVL or red-black trees with invariant checks and replay.
Linear Data Structure Operations Simulator Trace list, stack, queue, and deque operations across linked and bounded-array representations with endpoint and invariant evidence.
Search Algorithm Simulator Compare four search methods with repeatable probe traces and see how candidate ranges, data order and duplicates affect first-match or miss results.
String Matching Algorithm Simulator Compare four exact string-matching methods with Unicode traces showing preprocessing and shifts plus overlap and hash-collision handling.

A hash table turns a key into a bucket index so insertion and exact-key lookup can start near the likely record instead of scanning every entry. Because many keys can map to the same index, collision handling is part of the data structure rather than an exceptional error.

The chosen collision strategy changes where records live and how a search proves that a key is absent. Separate chaining keeps several entries at one home bucket. Open addressing keeps entries in the bucket array itself and follows a repeatable probe sequence when the home slot is occupied.

Home bucket
The first index produced from the key.
Probe
One inspected slot in an open-address sequence.
Collision
A different live key already occupies the needed bucket or slot.
Tombstone
A deletion marker that keeps later keys reachable while allowing the slot to be reused.
Load factor
Live entry count divided by bucket count.

Deletion reveals an important difference. Removing a chained entry leaves the rest of its chain intact. Clearing an open-address slot completely could make a later colliding key unreachable, so deletion leaves a tombstone and search continues past it until the key or a never-used empty slot is found.

The simulation uses integer keys and a simple modulo home function to make every decision visible. Production hash tables usually hash richer key types, resize as the load changes, and use library-specific policies, so the recorded visit and collision counts describe this bounded run rather than a universal performance guarantee.

How to Use This Tool:

Keep the operation script and table size fixed when comparing collision strategies.

  1. Choose Separate chaining, Linear probing, or Triangular quadratic probing.
  2. Select 4, 5, 8, 11, or 16 buckets. Triangular quadratic probing accepts only the power-of-two sizes 4, 8, and 16.
  3. Enter 1 to 12 operation lines. Use insert KEY VALUE, search KEY, or delete KEY; keys are integers from -999 to 999.
  4. Move Trace position from the empty table to the final operation. The table state, bucket visits, collision count, tombstones, and load factor all stop at that same position.
  5. Inspect the operation trace when a key is not found or an insertion reports a full table. It identifies each visited bucket and the event that ended the probe.

Interpreting Results:

The selected state is a prefix of the operation script. Advancing the trace applies one more operation; moving it backward reconstructs the same earlier state rather than undoing a mutable table.

  • Visits counts every bucket inspection. In chaining, several entry comparisons can count as repeated visits to the same bucket.
  • Collisions counts conflicting entries encountered during insertion. Search and delete visits do not add to that collision total.
  • Occupied counts live entries. A tombstone is not occupied, but it can lengthen a probe.
  • Load factor is a snapshot, not a prediction of average search cost. Key distribution and tombstones also affect the path.
  • Table full means one complete open-address probe found no empty or reusable tombstone slot. Chaining does not have the same one-entry-per-bucket limit.

Technical Details:

Modulo arithmetic maps every accepted integer, including a negative key, into the bucket interval 0 through m − 1. Open addressing then adds a strategy-specific offset and wraps around the table.

Formula Core:

Let k be the key, m the table size, a the zero-based probe attempt, and q the number of live entries.

h(k) = ((kmodm)+m)modm plinear(a) = (h(k)+a)modm ptriangular(a) = (h(k)+a(a+1)2)modm LoadFactor = qm

The triangular sequence produces offsets 0, 1, 3, 6, 10, and so on. Restricting it to power-of-two table sizes makes the bounded teaching sequence visit every slot before repeating.

Rule Core:

Operation Separate chaining Open addressing
Insert Compare entries in home-bucket order; update a matching key or append a new entry. Follow the probe sequence; update a matching key, otherwise insert at the first reusable tombstone or empty slot.
Search Scan the home chain until the key is found or the chain ends. Continue through live entries and tombstones; stop on the key, a never-used empty slot, or one full probe cycle.
Delete Remove only the matching chain entry. Replace the matching live entry with a tombstone.

Worked Examples:

A collision followed by deletion

With 8 buckets, keys 1 and 9 both have home bucket 1. Linear probing places 1 in slot 1 and 9 in slot 2. Deleting key 1 leaves a tombstone at slot 1, so a later search for 9 continues to slot 2 and succeeds. Marking slot 1 as never used would stop the search too early.

References: