Re:Ask HN: I just wrote an O(N) diffing algorithm – what am ...
by eru on Tuesday October 29, 2019 @01:23AM
(#21384426)
Well, it depends on your hashtable implementation, and where your data comes from.
Python's old hashtables used to be good enough for most practical uses; but when the input data was controlled by an adversary, it was easy to run a Denial of Service attack.
Hashtables can be made to run in O(1) with arbitrarily high probability for insert and lookup, if you are willing to be very careful with the implementation, and willing to endure slightly worse constant factors in some cases. (Of course, it also depends on what model of computation you are using. At some scale your keys have to grow like O(log n) of the number of elements, just so that you can distinguish all elements. But we usually abstract away from that.)
But yes, just programming any old hashtable doesn't magically give you O(1) performance, you need to work for it.
Python's old hashtables used to be good enough for most practical uses; but when the input data was controlled by an adversary, it was easy to run a Denial of Service attack.
See https://bugs.python.org/issue13703 They started randomising the hash function at runtime.
Hashtables can be made to run in O(1) with arbitrarily high probability for insert and lookup, if you are willing to be very careful with the implementation, and willing to endure slightly worse constant factors in some cases. (Of course, it also depends on what model of computation you are using. At some scale your keys have to grow like O(log n) of the number of elements, just so that you can distinguish all elements. But we usually abstract away from that.)
But yes, just programming any old hashtable doesn't magically give you O(1) performance, you need to work for it.