Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
worst case searching for Hash map is O(logn) because their internal implementation uses the B+/AVL Trees( It depends on compiler ). Other hand of arrays takes O(n)
I think you are wrong over here, hashmap's worst case search time is O(n).
Reference from Wikipedia and other places.
Hashmaps are better for average case search, generally O(c), where c is the number of elements in the longest linked list associated with an entry in a hashmap. (This is when we are making use of Chaining to avoid hash collision) We make sure that this happens with the help of load factor.
- coder April 03, 2012In the worst case scenario, c = n, i.e. there is only one chain and array and hashmap are practically equivalent.