2 ms·
> Java's HashMap.get() was not 0(1) and asked if I was taught that in my non-Stanford education. (It is btw, feel free to analyze the implementation) It is O(1
by rb808 10y ago
> Java's HashMap.get() was not 0(1) and asked if I was taught that in my non-Stanford education. (It is btw, feel free to analyze the implementation)
It is O(1) if the hashmap is sparsely populated but if there are hash collisions the items are stored in a list (tree from 8) so is not O(1) in worst case
- dragonwriter 10y ago> It is O(1) if the hashmap is sparsely populated With a finite number of buckets (which is inherent to hashmap), asymptotic performance will never conform to the "sparsely populated" constraint, so its O(n). (That its concrete performance is roughly constant-time within certain size bounds in non-pathological cases is important knowledge, too, though.)