3 ms·

Fair enough, I'm not intimately familiar with how randomised algorithms are most often analysed in a very formal sense (I never saw an explicit theory of it, ev

Fair enough, I'm not intimately familiar with how randomised algorithms are most often analysed in a very formal sense (I never saw an explicit theory of it, even though I've seen multiple more "intuitive" analyses). My point was more that there is no reason why you shouldn't be able to describe an expected runtime via O notation, whether or not that's the right way to do it in practice. > Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions. But isn't this how it works for a hash table? It was my understanding that the actual hash function is deterministic, so there are no random choices to make - the randomness comes from the inputs; on the other hand you do have some assumptions (maybe not strictly proven) about the collision frequency, which should allow you to get a handle on the input distribution, or am I wrong?

eru 6y ago
In simpler times, hash maps used to be deterministic. But that lead to easy denial of service attacks. So many languages, like eg Python, patched their hashmaps to use randomized hashes. See eg https://arstechnica.com/information-technology/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/ https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703 https://bugs.python.org/issue13703
- Tainnor 6y ago
  Now that you mentioned it, I remember running into this. We would compute hashes out of some objects to compare for equality and it turned out we sometimes had more collisions than expected (orders of magnitude more), but this wasn't really reproducible. That was when I found out that the hashing algorithm wasn't deterministic. (Of course, the underlying cause was that our hash code calculations were not good and we had to fix them.)

eru 6y ago

In simpler times, hash maps used to be deterministic. But that lead to easy denial of service attacks. So many languages, like eg Python, patched their hashmaps to use randomized hashes. See eg https://arstechnica.com/information-technology/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/ https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703 https://bugs.python.org/issue13703

Tainnor 6y ago
Now that you mentioned it, I remember running into this. We would compute hashes out of some objects to compare for equality and it turned out we sometimes had more collisions than expected (orders of magnitude more), but this wasn't really reproducible. That was when I found out that the hashing algorithm wasn't deterministic. (Of course, the underlying cause was that our hash code calculations were not good and we had to fix them.)