Hash Table Visualizer -- Watch Hashing, Collisions, and Probing Animate

Hash Table Visualizer

Enter a key, select a collision resolution strategy, and watch how the hash function maps it to a bucket. See collisions, probing sequences, and chaining in action.

How Hash Tables Work

A hash table is a data structure that provides fast key-value lookups by mapping each key to an array index using a hash function. The hash function computes a number from the key, then takes that number modulo the table size to get an index between 0 and size-1.

For example, with a table size of 13, the key "hello" might sum its character codes to get 532, then 532 % 13 = 12, so "hello" goes into bucket 12. For numeric keys like 42, we compute 42 % 13 = 3, placing it in bucket 3.

Ideally, every key maps to a different bucket, giving O(1) insertion, deletion, and lookup. However, when two keys hash to the same index, a collision occurs. Hash tables handle collisions using one of two main strategies: chaining or open addressing.

Hash Functions

This visualizer uses:

• String keys: Sum of ASCII character codes, then modulo table size
• Numeric keys: The number itself, modulo table size

Good hash functions distribute keys uniformly across buckets. Poor hash functions cluster keys together, causing many collisions and degrading performance to O(n).

Collision Resolution Strategies

Chaining

Each bucket stores a linked list (or chain) of all keys that hash to that index. Insertion appends to the list; lookup scans the list; deletion removes from the list. Chaining is simple and never fills up, but uses extra memory for list pointers.

Linear Probing

If a bucket is occupied, try the next bucket (wrapping around to 0 after the end). Keep probing until an empty bucket is found. Search follows the same probe sequence. Linear probing has good cache locality but suffers from primary clustering where long runs of occupied buckets form.

Quadratic Probing

Instead of probing bucket+1, bucket+2, etc., quadratic probing tries bucket+1^2, bucket+2^2, bucket+3^2, etc. This reduces primary clustering but can still suffer from secondary clustering when keys with the same initial hash follow the same probe sequence.

Double Hashing

Uses a second hash function to compute the probe step size. For a key k, the sequence is: hash1(k), hash1(k) + hash2(k), hash1(k) + 2*hash2(k), etc. This virtually eliminates clustering and provides the best distribution among open addressing methods.

Load Factor and Resizing

The load factor is the ratio of items to table size (items/size). For chaining, hash tables remain efficient even with load factors above 1.0. For open addressing, performance degrades sharply above 0.7. Real implementations resize the table (rehashing all items into a larger table) when the load factor crosses a threshold, typically 0.75.

Comparison: Chaining vs Open Addressing

Time Complexity

Average case assumes a good hash function that distributes keys uniformly. Worst case occurs when all keys hash to the same bucket (a terrible hash function or adversarial input).

Frequently Asked Questions

What is a hash table?

A hash table is a data structure that maps keys to values using a hash function. The hash function converts a key into an array index where the value is stored. This enables O(1) average-case lookup, insertion, and deletion.

What is a hash collision?

A collision occurs when two different keys produce the same hash value (same array index). Collision resolution strategies include chaining (storing multiple items at the same index using a linked list) and open addressing (probing for the next empty slot).

What is the difference between chaining and open addressing?

Chaining stores colliding elements in a linked list at each bucket. Open addressing finds another empty bucket using a probing sequence (linear, quadratic, or double hashing). Chaining is simpler but uses more memory; open addressing has better cache performance.

Why does load factor matter?

Load factor (items/size) directly affects performance. For chaining, a load factor above 1.0 is fine but increases average chain length. For open addressing, load factors above 0.7 cause severe clustering and slow down all operations. Resizing keeps load factor in a healthy range.

What is a good hash function?

A good hash function distributes keys uniformly across all buckets, minimizing collisions. It should be fast to compute and deterministic (same key always produces the same hash). Examples include division method (key % size), multiplication method, and cryptographic hashes like SHA-256 for security-sensitive uses.

Does this tool store any data?

No. All visualizations run entirely in your browser. No data is sent to any server.

Related Tools

• Sorting Algorithm Visualizer -- watch bubble sort, merge sort, quick sort, and more animate step by step
• Data Structure Visualizer -- insert, delete, and traverse BST nodes interactively
• Regex Tester -- test regular expressions with live matching and explanation
• Base64 Encoder/Decoder -- encode and decode base64 strings

Privacy

This tool runs entirely in your browser. No keys or hash table data is sent to any server. Nothing is stored.

Hash Table Visualizer FAQ