3

I understand that returning the same value for each object is inefficient, but is it the most efficient approach to return distinct values for distinct instances?

If each object gets a different hashCode value then isn't this just like storing them in an ArrayList?

Mike
  • 312
  • 6
  • 18
  • I'd highly recommend reading the theory on hashing, just try to understand the basics, Java comes naturally afterwards. – bestsss Jul 21 '12 at 20:51

5 Answers5

4

hashCode must be consistent with equals, that's number one priority. If no two objects are equal, then this would be desirable. Bear in mind that if your object has any more than 32 bits of state, it is theoretically impossible to provide a perfectly spread hashcode.

Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
  • btw no hashtable in java uses 32bits of hashcode (arrays are 31bit max length) – bestsss Jul 21 '12 at 20:49
  • @bestsss That is not a fundamental barrier--you could easily have two arrays. – Marko Topolnik Jul 22 '12 at 07:35
  • 1
    CHM can hold more than 2^32 elements. Spreading the arrays into multiple segments and an extra trie (for collisions) is doable [and should be done] for the plain hashmap (esp the trie part). My point is that there is no hastable in java (as of now and at least any popular) that uses the whole 32bits. – bestsss Jul 22 '12 at 11:32
3

No, it's not actually.

Assuming your objects are going to be stored into a HashMap (or Set... doesn't matter, we'll use HashMap here for simplicity), you want your hashCode method to return a result in a way that distributes the objects as evenly as possible.

Hashcode should be unique for Objects that are not equal, although you can't guarantee this will always be true. On the other hand, if a.equals(b) is true, then a.hashCode() == b.hashCode(). This is known as the Object Contract.

Besides this, there are performance issues also. Each time two different objects have the same hashCode, they're mapped to the same position in the HashMap (aka, they collide). This means that the HashMap implementation has to handle this collision, which is much more complex than simply storing and retrieving an entry.

There are also plenty of algorithms that rely on the fact that values are distributed evenly across a Map, and the performance deteriorates rapidly when the number of collisions increase (some algorithms assume a perfect hash function, meaning that no collisions ever occur, no two different values get mapped to the same position on the Map).

Good examples of this are probabilistic algorithms and data-structures such as Bloom Filters (to use an example that appears to be in fashion these days).

pcalcao
  • 15,789
  • 1
  • 44
  • 64
  • You're reading the contract wrong: It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables. – Matt Jul 20 '12 at 12:58
  • You're right, it's not required, but the method should produce different outcomes. I wrote that a bit ambiguously, I'll rephrase, thanks. – pcalcao Jul 20 '12 at 14:09
1

You want hashCode() as varied as possible to avoid collisions. If there are no collisions, each key or element will be stored in the underlying array on its own. (A bit like an ArrayList)

The problem is that even if the hashCode() are different you can still get collisions. This happens because you don't have a bucket for every possible hashCode, and this value has to be reduced to a smaller range. e.g. you have 16 buckets, the range is 0 to 15. How it does this is complicated, but I am sure you can see that even if all the hashCodes are different, they can still result in a collision (though its unlikely)

It is a concern for denial of service attacks. Normally strings have a low collision rate, however you can deliberately construct strings which have the same hashcode. This question gives a list of Strings with a hashCode of 0 Why doesn't String's hashCode() cache 0?

Community
  • 1
  • 1
Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
0

The hashCode() method isn't suited for placing objects in an ArrayList. Although it does return the same value for the same object every time, two objects could quite possibly have the same hashcode.

Therefore the hashCode method is used on the key Object when storing items in for example a HashMap.

René Jensen
  • 451
  • 3
  • 20
0

The HashMap class's major data structure is this:

Entry[] table;

It's important to note that the Entry class (which is a static package protected class that implements Map.Entry) is actually a linked list style structure.

When you try to put an element, first the key's hashcode is computed and then transformed into a bucket number. The "bucket" is the index into the above array.

Once you find the bucket, a linear search is done inside of that bucket for the exact key (if you don't believe me, look at the HashMap code). If it is found, the value is replaced. If not, the key/value pair is appended to the end of that bucket.

For this reason, hashcode() values need not be unique, however, the more unique and evenly distributed they are, the better your odds are to have the value evenly distributed among the buckets. If your hashcode() method return the same value for all instances, they'd all end up in the same bucket, hence rendering your get() method to be one long linear search, yielding O(N)

The more distributed the values are, the smaller the buckets, and thus the smaller the linear search component would be. Unique values would yield constant time lookup O(1).

Matt
  • 11,523
  • 2
  • 23
  • 33