hashmap hashcode to obtain worst case constant time?

Question

I know that hashmap operations are O(1) amortized due to possible collisions. But in java, integer.hashCode is just its value. Then if you were to put m distinct integers into a hashmap where m = hashmap's INITIAL_CAPACITY (16 lets say) does that mean that there will be 16 different buckets with 1 integer each? Then would this guarantee O(1) lookup, deletion, insertion for worst time?

thanks, after opening the hood of java's hashmap code i found that: private static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } why are these magic numbers used? — League of Draven, Nov 04 '13 at 02:32

score 0 · Answer 1 · answered Nov 04 '13 at 02:12

No, because HashMap is going to have to take the very large number of possible values returned by hashCode and map them to the very small number of buckets, and there's no guarantee that that mapping will map different integers' hashcodes to different buckets.

score 0 · Answer 2 · answered Nov 04 '13 at 02:20

You should look at the way Hashmap decides which bucket the key/object will belong to and yu will see that it does NOT use object's hashCode() as bucket number but manipulates it (bit shifting) a little to limit a number of buckets to less than Integer.MAX_VALUE

score 0 · Answer 3 · edited May 23 '17 at 12:21

if you were to put m distinct integers into a hashmap where m = hashmap's INITIAL_CAPACITY (16 lets say) does that mean that there will be 16 different buckets with 1 integer each?

Depends on the values, probably the HashMap will create new buckets (increase the capacity) to keep the load factor under a minimum (Java HashMap increases size if load is over 75% by default).

What is load factor

would this guarantee O(1) lookup, deletion, insertion for worst time?

No, in particulary bad cases the lookup time can be up to O(n) (depending on the number of elements and their values). In the case of integers, all posible int values are mapped to the hashmap size, so it´s likely to be a lot of collisions for a small sized map.

score 0 · Accepted Answer · answered Nov 04 '13 at 02:28

0

No because HashMap will rehash the hash for its own internal purposes.

answered Nov 04 '13 at 02:28

user207421

305,947
44
307
483

hashmap hashcode to obtain worst case constant time?

4 Answers4