docs/COLLISION_MATH.md
This document explains the collision probability calculations for beads' adaptive hash-based IDs and the thresholds used for automatic length scaling.
The collision probability for hash IDs is calculated using the birthday paradox:
P(collision) ≈ 1 - e^(-n²/2N)
Where:
[a-z0-9])| DB Size | 4-char | 5-char | 6-char | 7-char | 8-char |
|---|---|---|---|---|---|
| 50 | 0.07% | 0.00% | 0.00% | 0.00% | 0.00% |
| 100 | 0.30% | 0.01% | 0.00% | 0.00% | 0.00% |
| 200 | 1.18% | 0.03% | 0.00% | 0.00% | 0.00% |
| 500 | 7.17% | 0.21% | 0.01% | 0.00% | 0.00% |
| 1,000 | 25.75% | 0.82% | 0.02% | 0.00% | 0.00% |
| 2,000 | 69.60% | 3.25% | 0.09% | 0.00% | 0.00% |
| 5,000 | 99.94% | 18.68% | 0.57% | 0.02% | 0.00% |
| 10,000 | 100% | 56.26% | 2.27% | 0.06% | 0.00% |
This shows the average number of actual hash collisions you'll encounter:
| DB Size | 4-char | 5-char | 6-char | 7-char | 8-char |
|---|---|---|---|---|---|
| 100 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| 500 | 0.07 | 0.00 | 0.00 | 0.00 | 0.00 |
| 1,000 | 0.30 | 0.01 | 0.00 | 0.00 | 0.00 |
| 2,000 | 1.19 | 0.03 | 0.00 | 0.00 | 0.00 |
| 5,000 | 7.44 | 0.21 | 0.01 | 0.00 | 0.00 |
| 10,000 | 29.77 | 0.83 | 0.02 | 0.00 | 0.00 |
Example: With 5,000 issues using 4-char IDs, you'll likely see ~7 hash collisions (automatically retried with +1 nonce).
Beads automatically increases ID length when the collision probability exceeds 25% (configurable via max_collision_prob).
| Database Size | ID Length | Collision Probability at Max |
|---|---|---|
| 0-500 | 4 chars | 7.17% at 500 issues |
| 501-1,500 | 5 chars | 1.84% at 1,500 issues |
| 1,501-5,000 | 5 chars | 18.68% at 5,000 issues |
| 5,001-15,000 | 6 chars | 5.04% at 15,000 issues |
| 15,001+ | continues scaling as needed |
The 25% threshold balances:
Even at 25% collision probability, the expected number of actual collisions is low (< 1 collision per 1,000 issues created).
You can customize the threshold with bd config set max_collision_prob <value>:
| DB Size | ID Length |
|---|---|
| 0-200 | 4 chars |
| 201-1,000 | 5 chars |
| 1,001-5,000 | 6 chars |
| 5,001+ | continues scaling |
| DB Size | ID Length |
|---|---|
| 0-500 | 4 chars |
| 501-2,000 | 5 chars |
| 2,001-10,000 | 6 chars |
| 10,001+ | continues scaling |
When a hash collision occurs (same ID generated twice), beads automatically:
Total: 30 attempts before failing (astronomically unlikely).
Example with 4-char base:
bd-a3f2 (nonce 0) - collision!bd-a3f2 (nonce 1) - collision again!bd-b7d4 (nonce 2) - success! ✓| Length | Possible IDs | Notation |
|---|---|---|
| 3 chars | 46,656 | 36³ |
| 4 chars | 1,679,616 | 36⁴ ≈ 1.7M |
| 5 chars | 60,466,176 | 36⁵ ≈ 60M |
| 6 chars | 2,176,782,336 | 36⁶ ≈ 2.2B |
| 7 chars | 78,364,164,096 | 36⁷ ≈ 78B |
| 8 chars | 2,821,109,907,456 | 36⁸ ≈ 2.8T |
Using [a-z0-9] (36 characters) instead of hex (16 characters):
bd-a3f2 vs bd-a3f2e1Run the collision calculator yourself:
go run scripts/collision-calculator.go
This generates the tables above and shows adaptive scaling strategy for any threshold.