Data-Structures

Symptom Product wants the daily unique-visitor count. You have a firehose of events. The obvious implementation is a set. Add each visitor ID, report the size. At a billion distinct IDs, eight bytes each, that is 8 GB before any hash table overhead, and in practice a HashSet will cost you two to three times that. Per day. Per dimension you want to slice by. Multiply by country, by platform, by campaign, and the memory bill is absurd for a number nobody looks at past two significant figures. ...

Symptom Your service went down under a hash collision attack. Somebody noticed your web framework put POST parameters into a hash table, found thousands of distinct keys colliding under its hash function, and posted a form with 20,000 of them. Every insert walked a chain. Quadratic behaviour, one CPU pinned per request, service dead. This actually happened, across PHP, Python, Ruby, Java and .NET in 2011, and again against Rust’s default HashMap before it switched to SipHash. ...

Symptom You have a dynamic array. push writes one element and bumps a counter, which is clearly $O(1)$ — except when the array is full, in which case it allocates a new buffer of twice the size, copies every element across, and frees the old one. That is $O(n)$. ...

Symptom You need a short ID for uploads. Eight hex characters feels generous, so you take the first 32 bits of a hash and move on. At about 80,000 uploads, two files collide, and one of them silently overwrites the other, and the bug report says the customer’s invoice contains someone else’s line items. ...