3 ms·
> If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected If the list
by cabalamat 17y ago
> If the list size is known, it's very easy to construct a hash table or hash set where collisions are extremely low and O(1) lookups are expected
If the list size isn't known, you can still do this, by doubling the size of the hash table whenever there are too many entries in it.
- RiderOfGiraffes 17y ago> doubling the size of the hash table whenever > there are too many entries in it. And then re-hashing and dealing with all that implies. Surely all of that is much harder than chasing a pair of pointers down the list. Also, it doesn't work in the case of, say, Pollard's Rho method of factoring. I really need to change the original article to make it clear that that's a case I'm interested in.