Hash Table Search
Every search algorithm up to this point worked by comparing keys: asking whether the value you want is smaller or larger than the one you are looking at. Even the fastest tree searches hit a logarithmic wall doing that. A hash table dodges the wall by changing the question: instead of comparing values, it computes an address directly from the key using a hash function. In the ideal case, the math points straight at the target slot on the very first try. That is O(1) expected time: constant work regardless of whether the table holds ten items or ten million.
The reality check is that multiple keys can hash to the exact same slot—a collision. When two keys collide, the table has to decide where the newcomer lives. This visualizer uses open addressing with linear probing: if bucket h is already taken, it steps forward to h + 1, h + 2, and so on, wrapping around the end until it finds an open slot. Searching retraces that exact same path. It checks bucket h; if that holds a different key, it scans forward until it either finds the target or lands on an empty slot. Because entries were placed contiguously, hitting an empty bucket is absolute proof the item is not in the table.
The trade-off is clustering and memory. As a hash table fills up, collisions create runs of occupied slots, causing probes to take longer and dragging performance toward O(n) in the worst case. Keeping the table sparse (usually under 70% full) keeps probe counts near one or two. When you have enough memory to keep the table roomy, nothing beats the speed of hashing.
Watch the gold ring jump straight to the hashed bucket index on the first probe, and notice how it walks forward through any collision cluster before turning green on a match. Type a value into the search box to look for something specific, or let the Target menu pick one that is present or absent. Data switches between numbers and words, and New array deals a fresh table.