1

So for example we have very poor hash for all custom objects = 2(in bits =..10). Somewhere in related posts is said : "HashMap uses power of two size because you can easily pick the bucket by hashCode & MASK where MASK = 000....111 where amount of 1s == current power of 2 used for size. "

So for map length = 2 we have ..10 & 01 = 0 - index for bucket when size is 2. For size = 4 we will have: ..010 & 11 = 10(= 2dex) - index for size 4. For size = 8 we will have: ..010 & 111 = 10(= 2dex) - again for size 8. So in this simple situation we will have 2 different buckets for same object key.(In general map method hash(int hashCode) does the same - it can produce different bucket indexes for same object hash - depending on the map size - to handle collisions on lower bits). When u perform get() on the map - does it go through all this different buckets suitable for the same key - or not? Or how does is track all needed buckets for object hash?
Why hash method in HashMap

Community
  • 1
  • 1
AlexInspired
  • 91
  • 2
  • 12

1 Answers1

2

Whenever the HashMap is resized, all the entries are re-hashed, i.e. they are moved to new buckets if the new size of the map requires so.

Therefore get() only has to look for the bucket that matches the hashCode() of the searched key and the current size of the map.

does it go through all this different buckets suitable for the same key - or not?

There's only one suitable bucket for a given key at any given point in time (which depends on the hashCode() of the key and the current size of the HashMap).

Eran
  • 387,369
  • 54
  • 702
  • 768
  • So again what is the point in method int hash(key.hashCode)? I supposed it can create multiple buckets for same key (thus performing better distribution by shifting higher bits to low). But if it produces the same amount of buckets as was(1 key goes to 1 bucket) - what is the use of it? – AlexInspired Mar 11 '16 at 09:52
  • I thought 1 more time and imagined situation where we have hash 326 and 120 and size say 16. This keys will go in same bucket in case of power-of-two hashMap. So method hash moves this hashes to low bits - and on some size they will apply to 111 in mask - and got to different buckets, thus improving the distribution of objects. – AlexInspired Mar 11 '16 at 10:29