Free URL shortener · DSA Micro Project 02
Short links,
hashed in plain sight.
Paste a long URL to get a short one. Then see exactly how a hand-written hash table stores it, resolves collisions and finds it again.
Find or delete a link
Paste a short link or just its code. All three data structures search for it, and each one's comparison count is shown. You can delete only links created in this browser.
How it works
Every link is stored three ways: in a hash table with separate chaining, in a hash table with open addressing, and in a plain linked list for comparison.
The hash function
A short code is turned into a bucket number, one character at a time:
h = (h × 31 + character code) mod m
Start with h = 0. Taking the remainder at every step keeps the numbers small, and the final h is the bucket. The same code always gives the same bucket, so finding a link means checking just that one bucket.
Separate chaining
Each bucket is a small linked list. When two codes land in the same bucket (a collision), the new one is added to the end of that bucket's chain. Growth rule: when there are more links than buckets, the table doubles in size (to the next prime) and every link is re-hashed.
Open addressing (linear probing)
One link per slot. If a code's home slot is taken, try the next slot, then the next, until one is free. A deleted slot keeps a tombstone so later searches don't stop early. Growth rule: once 70% of slots are used, the table doubles (to the next prime) and every link is re-inserted.
Linked list (the baseline)
The same links in one chain, oldest first. There is no shortcut: a search starts at head and checks each node in turn, so the last link needs as many comparisons as there are links.