4

I have a doubt to my mind ::

Currently HashMap in java, resizes when totalSize(no of elements inserted) > arrayLength * loadFactor

so it doubles the table and rehashes all key-value.

But suppose hashcode in Key class is hardcoded to let's say 1, so everytime elements will be inserted at index 1 in linked list manner. But our bucketarray will unnecessary resize on total size. So it will keep on increasing bucketarray size while elements going in the same bucket with such hashcode implementation.

I have a question, should we not check resize on filled buckets, instead of total size ??

I know such hashcode will hamper the performance. I am asking this as a logical question.

Rajat Goyal
  • 465
  • 1
  • 5
  • 20
  • 1
    FYI, it's [not always a linked list](https://stackoverflow.com/questions/43911369/hashmap-java-8-implementation/43911638#43911638). – Michael Nov 08 '17 at 10:19
  • Using the total elements simplify the implementation vs keeping track of used buckets. Likely the HashMap developers did not base their design on someone using a HashMap where they don't need to, or did something very silly like using the same key for every element or otherwise provide a bad hashCode() function – nos Nov 08 '17 at 10:19
  • @nos "or otherwise provide a bad hashCode() function" actually, there *were* steps taken to reduce the performance impact of a poor hash function. – Michael Nov 08 '17 at 10:22

3 Answers3

3

HashMap has some code that attempts to improve bad hashCode() implementations, but it can do nothing to improve a terrible hashCode() implementation that always returns the same value.

Such a hashCode() will give bad performance regardless of whether or not you resize the HashMap. Therefore, such bad usage of HashMap doesn't justify adding special logic as you suggest.

The assumption on the hashCode() implementation of the key is that it will distribute the keys as close to uniformly as possible among the HashMap bins. Therefore the average number of entries in a bucket (which is the total number of entries divided by the number of buckets) should give a good estimate on when the HashMap should be resized, and the size of individual buckets doesn't need to be checked.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • I know such hashcode will hamper the performance. I am asking this as a logical question. – Rajat Goyal Nov 08 '17 at 10:23
  • 1
    @RajatGoyal `HashMap` is supposed to be used in a certain way. Suggesting a bad usage example as a reason to change the existing implementation (which works fine when you use `HashMap` properly) doesn't seem logical to me. – Eran Nov 08 '17 at 10:28
  • @Eran agree with you. – DhaRmvEEr siNgh Nov 08 '17 at 11:25
2

Imagine a hash map with size 12, and 9 items in it. Let’s say that by coincidence, #hashCode()only returns multiples of 3 - it’s still a flawed hash code, but it’s not a contrived edge case such as a constant hash code of 1. This means that in this case, only four buckets (0, 3, 6, and 9) would be filled with 1 or two elements.

With your approach, this hashmap would never get resized, the collision lists would grow forever, and performance would suffer. However, if you resize it based on total size, with a load factor of 75% that would be when adding the tenth element, you’d end up with a map with 24 buckets, 8 of which will be filled.

Growing based on total size keeps the collision lists at a reasonable size with realistic imperfect hash function, because it’s reasonable to expect every hash function at least makes a best attempt to distribute hash codes. Meaning that growing a hash map will lead to more full buckets than previously, even if there might still be clusters and empty buckets.

Basically, your suggestion is to optimize for memory use in an edge case, and to not optimize for access performance - i.e. the main purpose of maps - in more likely cases.

millimoose
  • 39,073
  • 9
  • 82
  • 134
0

if hashcode always returns same value

  1. it is a bad implementation, no logic of supporting what should not be done.

  2. hashcode may not be a constant function, HashMap has no way to know if the hash function is of type constant or not so it is wise to resize the hashmap as in case suddenly hashcode becomes non constant function then resizing may result in better distribution of the values.

nits.kk
  • 5,204
  • 4
  • 33
  • 55