Re:Why databases use ordered indexes but programming uses ha...
by davedx on Tuesday December 10, 2019 @02:02AM
(#21750321)
> But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n))
I'm sorry, but as a reader it is quite amusing that various posters are claiming (all without citing any sources) hashtables are O(1), O(n) and O(log(n))
But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)). By the pigeon hole principle, it is impossible to store N items in a hash table using a key whose representation is less than log(N) bits without a collision. This means that there is a relationship between the the size of the key being hashed and the number of elements being inserted in the hash map, specifically the relationship is an element of O(log(n)).