I'm developing a web app where I wish to use pseudorandom keys for items, perhaps akin to Imgur. I was thinking about how many combinations I need to reduce the chance of someone guessing any random item in the database (by checking the associated URL) to x. On the performance side, it would seem to be the same (similar?) problem when I'm generating new keys randomly to avoid an excessive hit from repeated collisions.

From the birthday attack article, roughly, the number of options there needs to be (H) for a 50% chance of collision is sqrt(H). So, even if I have 10 billion (10¹⁰) possible keys, someone only needs to guess 100 thousand (10⁵) to get a collision...

Something seems severely off with my understanding of the math: if I only have a couple thousand keys used (or lets say 1) out of billions possible, it seems like the chance to randomly find it would be one in a billion.

What's relevant for me I suppose is given the number of entries I expect, and some tolerance for a possible attacker to randomly find one of said entries, how many choices do I need? Naively I'd just say it's

num_possible_key_values >= expected_entries / max_probability_to_randomly_find_one

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys.