Order of finding correct bucket in java hashmap

Question

what is order of finding correct bucket in java hashmap??

In hashmap first bucket is located using hashcode method and then we iterate over it using equals method, so my question is on first part, what is complexity of finding the bucket in which desired key is present.

you can find all your answers here http://en.wikipedia.org/wiki/Hash_table (java HashMap uses "separate chaining"). — jtahlborn, Apr 03 '12 at 14:35

score 1 · Accepted Answer · answered Apr 03 '12 at 14:35

1

Looking up the bucket is O(1). Hashmap just computes the hashcode and uses it to index into the bucket slots.

answered Apr 03 '12 at 14:35

Ted Hopp

232,168
48
399
521

score 0 · Answer 2 · answered Apr 03 '12 at 14:48

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.

it doesn't provide "constant time" performance, it provides "amortized constant time" performance. — jtahlborn, Apr 03 '12 at 14:58

Order of finding correct bucket in java hashmap

2 Answers2