Skip to content
All apps

Hashing & collisions

About this app

How a string becomes a table slot and how a search works: the calculator works character by character up to hash mod m. Seven methods from deliberately bad (length, first letter, character sum) to usable (polynomial hash, djb2, FNV-1a) plus the number itself. Search with a comparison counter: only one bucket is searched, while a list and a search tree need 14 and 7 instead of 3 comparisons. Growing at two thirds like dict, prime vs. power of two, statistics against the ideal.

Hash function and hash table

A hash function turns a string of any length, character by character, into a number h, deterministically, so the same each time. The remainder h mod m picks a slot in a table with m slots. A lookup can then go straight to that slot instead of scanning the whole table. Collisions are unavoidable because there are infinitely many strings but only m slots. A good hash function does not prevent collisions; it spreads them evenly. Even a perfectly random distribution produces collisions, as the birthday paradox shows. Hashing is not encryption: it cannot be reversed.

What the app shows

A calculator computes the hash character by character up to the slot h mod m, step by step or as playback. Seven methods are available: deliberately bad ones (length, first letter, character sum), usable ones (polynomial hash with factor 31, djb2, FNV-1a) and “number itself” for numeric keys. The table size can be chosen as a prime or a power of two, with automatic resizing above a load factor of 2/3. Examples such as anagrams, first names or serial numbers fill the table. Statistics compare collisions and the longest chain with the ideal value.

Try it yourself

Load the anagrams and compare “sum” with “poly31”: with the character sum, Lager and Regal always collide, with the polynomial hash they do not. Set m to a power of two and to a prime and watch the distribution. Then look up a word: the comparison counter shows that only one slot is searched. For contrast the app states how many comparisons a list or a balanced search tree would need.

Frequently asked questions

How does a hash table work?
A hash table uses a hash function to turn the key into a number and, via mod m, into the slot that holds the entry. A lookup computes the same slot and checks only there. If several keys land in the same slot, they are stored, for example, in a chain.
What is a hash collision?
A collision happens when two different keys land in the same slot. Collisions cannot be avoided because there are more possible keys than slots. A good hash function spreads keys evenly so that chains stay short.
Why should a hash table size be a prime number?
If m is a power of two, h mod m depends only on the low bits of h. With a prime, all bits influence the slot. This compensates better for weaknesses of the hash function; the multiplier and m should also be coprime.
Which hash functions can I compare in the app?
Length, first letter, character sum, polynomial hash with factor 31, djb2, FNV-1a and “number itself” for numeric keys. For each, the app explains why it distributes well or badly.

Subject: Cryptography

More from Cryptography

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps