What is the time complexity of iterating a hash map in average case? I think its O(n)
What is the time complexity of map.get(key); I think its O(1)
Add a comment |
3 Answers
From the documentation, which should be your first port of call:
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
9 Comments
posdef
@Jon: you must have the API on hotkey or something... :)
jslearner
@jon :I made some chnages in original post, can you comment?
Jon Skeet
@jslearner: Yes - you've got them round the wrong way. How can iterating a hash map be O(1)?
Jigar Joshi
@jslearner if you iterate through the keys then you it will be o(1) for retrieval of value for each key, and yes you are right
Jon Skeet
@typedef: We don't know what counts as "too much" - but a map with 5000 entries is fine, and reasonably small even, certainly for server-side work.
|
O(1) which is constant in normal case, if they don't collide
See Also
Comments
From the API:
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.