That would indeed be way (quadratically) more likely but we don't count the number of attempts but measure run time, and since comparisons (even with optimizations like insertion sort) take time, the speed difference between the two methods will be "just" a few orders of magnitude.

[–] Redjard@lemmy.dbzer0.com 3 points 22 hours ago

As long as you don't run out of memory, you can actually insert and lookup in O(1) time for a known space of values (that we have). Therefore we do get the quadratic speedup, that when dealing with bits of keysize or entropy means cutting it in half.
Checking to get a specific uuid takes 128bit, so 2^128^ draws of a uuid. Putting all previous uuids into a table we expect a collision in 64bit, so 2^64^. We also need about that much storage to contain the table, so some tens of exabytes.