0

I know how hashmaps work and how they resolve collisions. But many answers related to collisions on SO point to two reasons:

  • HashCode contract - unequal objects can have the same hash code
  • Underlying array size - is fixed in size and hence bucket locations may be reused (using modulo operator) when it gets full.

My assumption is that reason 2 above is also correct, as am sure of reason 1.

Only 1 question:

  • Javadoc says that the hashmap uses LF and Capacity to decide when to rehash. I understand this as partly resizing the underlying array. So how is reason 2 above even possible?????

NB: This question came closest to what I want to understand. However, the accepted answer seems to discard reason 2 altogether, so it still leaves me wondering.

Community
  • 1
  • 1
egimaben
  • 653
  • 7
  • 22
  • Hashmap resizes according to capacity (when LF * capacity < size) or if there is a collision detected. – Laurent B Dec 16 '16 at 09:50
  • 2
    @LaurentB That's not true. Resize doesn't happen if a collision is detected. – Kayaman Dec 16 '16 at 09:51
  • @Kayaman sorry yes reread the source (1.7) only when bucket is full and capacity reached – Laurent B Dec 16 '16 at 10:05
  • @LaurentB my question is how does the size of the underlying array cause collisions? – egimaben Dec 16 '16 at 10:06
  • 1
    Well, a smaller array has a higher chance of collisions obviously. If you decided randomly whether to throw 2 balls in 2 buckets or 10 buckets, which would be more likely to end up with 2 balls in the same bucket? Are you sure you know how hashmaps work? – Kayaman Dec 16 '16 at 10:07
  • @Kayaman this now makes a lot of sense. The analogy of 2 balls has just increased my understanding of how hashmaps work :) – egimaben Dec 16 '16 at 10:21
  • That's good. Analogies are quite useful in the computing world. – Kayaman Dec 16 '16 at 10:47

1 Answers1

2

Your reason 2 is flawed. A bucket may be reused even if there are plenty of empty buckets if adding two (unequal) objects that end up in the same bucket (hashcode % buckets.length). There's no "getting full" element here, except that as buckets get filled there's obviously a greater chance of ending up in a non-empty bucket.

Kayaman
  • 72,141
  • 5
  • 83
  • 121