Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Project: audit four keyed-lookup structures

Last updated: 3 Oct 202630 min read
project
IntermediateBy AITrove Editorial

An incident platform needs revisioned alert states, ordered term completion, service-route selection, and a growing alert-ID directory. Build an exact reference for each: one dictionary snapshot per revision, a sorted term set, a list of matching prefixes, and a current dictionary of alert records. Compare every answer after inserts and replacements. Use IDs 47 and 303 to force an eight-bit hash collision; never infer key equality from digest equality. Record how many directory references point to the same bucket before counting stored records. Keep the route width and hash width fixed so the exercise has an explicit failure boundary.

Acceptance trace

Keep revision one of alert 47 open while revision two records closed; alert 303 remains review in both. Complete al to obtain al, alarm, alert, and alpine, while alp remains an incomplete term. Route A947 to pump, A983 to depot, and 3901 to fallback. Insert 47, 51, 55, and 303 into a two-record extendible directory and verify all four full IDs remain retrievable even though 47 and 303 share a digest. Test replacements as well as first insertions.

Expected review record

Output
old-47=open
new-47=closed
alp-exact=False
route-A947=pump
alert-303=incident-303

Boundary and cost review

Generate keys that collide on only their low four bits and keys that collide on all eight. Check historical roots after each replacement, compare every term prefix with direct string filtering, and select the deepest matching route by an independent mask scan. After each directory split, verify that every bucket's references agree with its local-depth low-bit pattern and that no record exists in two distinct buckets. Explain collision-bucket scans, skewed ternary trees, fixed route width, and directory-doubling cost without presenting these Python models as measured production memory layouts.

Common Mistakes

  • Do not overwrite a node shared by an older map revision.
  • Do not mark every reached term prefix as complete.
  • Do not stop at a short matching route when a deeper one exists.
  • Do not count directory aliases as separate stored buckets.

Connected lessons

data structures
projects
Storage details