Expected hash collisions calculator
Hash 100 keys into 128 buckets and, on average, more than half the keys end up sharing a bucket, at a load factor of 0.78125. You also get singletons, empty and occupied buckets, overflow keys and pairwise collisions. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 100
- M
- 128
- Load factor
- 0.78125
- Expected colliding keys
- 53.9975057729
- Expected singleton keys
- 46.0024942271
- Expected occupied buckets
- 69.5768323316
When you hash n distinct keys uniformly into m buckets, some keys share a slot even at a modest load factor. Intuition underestimates occupancy: people remember the birthday-paradox probability that at least one pair collides, then treat that probability as if it were a count. This expected hash collisions calculator answers a different planning question. It uses the classical balls-in-bins model — each item chooses one of m buckets independently and uniformly — and returns the expected number of colliding keys, meaning keys that are not alone in their bucket. Alongside that headline figure it reports singleton keys, occupied and empty buckets, overflow keys beyond the first occupant, pairwise collisions, and the load factor n divided by m. The arithmetic is a closed-form identity evaluated in log space, fully deterministic, with no Monte Carlo sampling and no language model. Use it to size a hash table, tune a load factor, compare a 32-bit hash space with a narrower one, or check a textbook occupancy claim before you commit memory.
What expected colliding keys measure in the balls-in-bins model
Throw n balls independently and uniformly into m bins and you have the standard model for a uniform hash. A colliding key is a ball that shares its bin with at least one other ball. That is not the same quantity as the birthday-paradox probability that at least two balls share a bin, and it is not the same as the number of pairwise matches.
For capacity planning you usually want a count: how many keys, on average, fail to own a private slot, how many buckets sit empty while others overflow, and how many extra keys pile on top of the first occupant. Linearity of expectation gives clean answers without simulation. Fix any one key.
The other n minus one keys each miss that key's bucket with probability one minus one over m, so the chance the chosen key is a singleton is (1 − 1/m) raised to n minus one. Multiply by n and you have the expected number of singleton keys. The same occupancy argument yields the expected number of empty buckets, m times (1 − 1/m) to the n, and therefore the expected number of occupied buckets.
Overflow keys are the items beyond the first in each occupied bucket, equal to n minus occupied. Pairwise collisions equal n choose two divided by m, because any specific pair lands together with probability one over m. Load factor is simply n over m.
Together these figures tell you whether a proposed table is starved for buckets, merely busy, or already paying a chain-length tax that a larger m would remove.
Capacity planning, limits, pricing, and where the numbers earn their keep
Use the browser tool when you are choosing a table size, comparing load factors, or walking a team through why a load factor of one still leaves a large share of keys sharing a bucket. Sweep m upward until expected colliding keys or overflow keys fall under your service-level budget, then keep a little headroom for growth.
Contrast the result with a birthday-paradox probability if you also need the chance that any collision exists; that probability saturates near one long before the expected colliding-key count becomes large, which is why the two tools answer different tickets. Results are fully deterministic: the same n and m always yield the same occupancy vector, so you can pin examples in tests and lesson materials. There is no language model, no external statistics service, and no randomness.
What you can do with it
Hash table and map sizing
Pick n equal to the working-set key count and sweep m (table slots) until expected colliding keys and overflow keys sit under your latency budget.
Cache shard and partition occupancy
Treat shards as buckets and incoming keys as balls to estimate how many keys share a hot partition before you add capacity or rehash.
Deterministic oracles for lessons and tests
Courses, interview platforms, and CI suites call a stable occupancy oracle that rejects n or m below one and returns identical fields for identical inputs.
FAQ
What is a colliding key in this calculator?
A key that is not alone in its bucket. The expected count is n minus the expected number of singletons. It is an expected count, not the probability that at least one pair collides.
How is this different from the birthday paradox?
The birthday paradox returns P(at least one shared day). This tool returns expected occupancy counts for hash tuning: colliding keys, overflow keys, empty buckets, and pairwise collisions under balls-in-bins.
What happens if n or m is below 1?
At least one item and at least one bucket are required; zero and negative values are rejected and not charged.
Is the expected hash collisions calculator free?
The browser tool runs free on your device.
How many buckets stay empty on average?
The expected count is the number of buckets times the chance that no key lands in a given bucket. With 100 keys in 128 buckets almost half the buckets stay empty, even though more than half the keys share a slot.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/dev/hash-expected-collisions \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":100,"m":128}'const res = await fetch("https://api.kit.forhosting.com/dev/hash-expected-collisions", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 100,
"m": 128
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/hash-expected-collisions",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 100,
"m": 128
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/hash-expected-collisions", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":100,"m":128}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":100,"m":128}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/hash-expected-collisions", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": 100,
"m": 128
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.hash_expected_collisions",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_n | 1000000000000 |
max_m | 1000000000000 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
What expected colliding keys measure in the balls-in-bins model
Subtract from n and you have the expected number of colliding keys: n times one minus (1 − 1/m) to the n minus one.
Input contract, formulas, numerical stability, and errors
Send two required integers: n, the number of items, and m, the number of buckets. Both values must be finite integers inside the published limits: n from one through one trillion, and m from one through one trillion, which covers classroom examples, in-memory maps, and a full 32-bit hash space of four billion two hundred ninety-four million nine hundred sixty-seven thousand two hundred ninety-six slots. After validation the engine evaluates powers of one minus one over m in log space as the exponential of the exponent times log1p of minus one over m, so large n and m do not underflow to a silent zero the way a naive loop of multiplies would. Special cases stay exact: a single item never collides; a single bucket with two or more items makes every key collide; a zero exponent is treated as one so (1 − 1/m) to the power zero does not become an indeterminate zero to the zero. Aliases items, keys, or balls for n, and buckets or bins for m, are accepted. Missing fields, non-integers, n or m below one, and values above the maxima fail with invalid_input and are not charged. The JSON body echoes n and m, then returns load_factor, expected_colliding_keys, expected_singleton_keys, expected_occupied_buckets, expected_empty_buckets, expected_collision_buckets, expected_overflow_keys, expected_pairwise_collisions, and a formula string restating the two headline identities.
Capacity planning, limits, pricing, and where the numbers earn their keep
Each successful request is one billable item at $0.002; failed validation does not consume balance. The published ranges keep the closed-form evaluation inside ordinary IEEE-754 doubles while covering every practical hash table you would size by hand. Wire the endpoint into hash-table tutorials, cache-shard planners, Bloom-adjacent occupancy checks, or coding-interview oracles where you prefer the exact balls-in-bins identities over approximate sampling histograms that never quite settle.
Technical questions
How do I estimate expected hash collisions for n keys and m buckets?
Send integers n (items) and m (buckets) to dev.hash_expected_collisions. The response includes expected_colliding_keys = n*(1-(1-1/m)^(n-1)), plus occupied, empty, overflow, pairwise, and load_factor.