How does a Java HashMap handle different objects with the same hash code?
A hashmap works like this (this is a little bit simplified, but it illustrates the basic mechanism):
It has a number of "buckets" which it uses to store key-value pairs in. Each bucket has a unique number - that's what identifies the bucket. When you put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. For example: The hash code of the key is 235 -> the pair is stored in bucket number 235. (Note that one bucket can store more then one key-value pair).
When you lookup a value in the hashmap, by giving it a key, it will first look at the hash code of the key that you gave. The hashmap will then look into the corresponding bucket, and then it will compare the key that you gave with the keys of all pairs in the bucket, by comparing them with equals()
.
Now you can see how this is very efficient for looking up key-value pairs in a map: by the hash code of the key the hashmap immediately knows in which bucket to look, so that it only has to test against what's in that bucket.
Looking at the above mechanism, you can also see what requirements are necessary on the hashCode()
and equals()
methods of keys:
If two keys are the same (
equals()
returnstrue
when you compare them), theirhashCode()
method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket).If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use
equals()
to tell them apart.
What happens if two different objects have the same hashcode?
They will just be added to the same bucket and equals()
will be used to distinguish them.
Each bucket can contain a list of objects with the same hash code.
In theory you can return the same integer as a hash code for any object of given class, but that would mean that you loose all performance benefits of the hash map and, in effect, will store objects in a list.
Can different objects with same value for the attributes have same hashcode in Java
equal objects means equal hashcode.
equal hashcode doesn't mean equal object.
nonequal hashcode means nonequal objects.
two unequal objects with same hashcode
2) It is not required that if two objects are unequal according to the equal(), then calling the hashcode method on each of the two objects must produce distinct values.
Depending on the hashing function, 2 different objects can have the same hash code. However, 2 objects which are the same must produce the same result when hashed (unless someone implemented a hashing function with random numbers in which case it's useless)
For example, if I am hashing integers and my hashing function is simply (n % 10)
then the number 17
and the number 27
will produce the same result. This does not mean that those numbers are the same.
How HashMap retrieves different values if Key's hashcode is same but equals method return false
A HashMap
/HashSet
implements per bucket a list of keys (on the case of a Map
together with the values). If multiple key's share the same hashCode
value, they are placed in this list.
So the search method first extracts the hashCode
of the queried key and then iterates over the corresponding list until an equals
method succeeds. In case of a HashSet
it means the key
is found, in case of a HashMap
, it returns the other side of the tuple: the value.
The memory of a HashMap
thus works like:
+--------+--------+--------+--------+
| 00 | 01 | 10 | 11 |
+--------+--------+--------+--------+
| | | |
k00/v00 _ k06/v06 _
| |
k08/v08 k14/v14
| |
k04/v04 _
|
_
What you see is on top the four buckets. Each bucket has a list (the items underneath), that stores tuples of keys (k
) and values (v
). Since there are here only four buckets, the hash algorithm uses a modulo 4 operation, so a key k06
with value v06
would be placed in bucket 06 mod 4 = 02
thus 10
. In case a second key k14
is added with 14 mod 4 = 02
thus 10
, it is simply added to the list.
Since the values are stored with it as well, one can perform a fast lookup operation. The key is thus stored together with the value.
You noticed, that iterating over the (linked) list is an expensive operation. But the point of a HashMap
is that one hopes, that the number of hash-collisions to use the correct term (number of keys sharing the same bucket) is very low. In general one might expect two or three elements per bucket. The performance boost is thus achieved by selecting the correct bucket in constant time, searching the bucket requires however linear time (or in case there is a complete ordering on the key's, one might implement a (balanced) binary tree to search in logarithmic time). Worst-case however, a HashMap
can achieve, the same performance as an ArrayList
/LinkedList
of entries, but given the hash-function has been designed decently, the odds are very low.
Under what Conditions two different objects may have same hashcode() value..?
You can override hashCode
in your classes. You would usually override it along with overriding equals
, so that if a.equals(b)
is true, a.hashCode() == b.hashCode()
is also true (even if (a == b)
is false).
However, even if a.equals(b)
is false, a.hashCode() == b.hashCode()
may still be true.
As you can see in the Javadoc of Object class :
- If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must
produce the same integer result.- It is not required that if two objects are unequal according to the java.lang.Object.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.
hash code of different objects are the same
I think you have already realized what the answer to your question is, but the code that you added in your update makes it clear:
Your
CustomClass
extends theBaseClass
.The
BaseClass
overridesObject::hashCode()
The override in the version of
BaseClass
that you showed us will always return 1. It is calling ahashCode(ObjectLocator, HashCodeStrategy2)
method with a specific strategy, but the implementation of that method simply ignores the strategy argument.
Now is pretty clear that that version the BaseClass
code can only ever return 1 as the hashcode. But you say that your code used to work, and you only changed the dependency. From that, we must conclude that the dependency has changed, and that the new version of the dependency is broken.
If anything is "bizarre" about this, it is that someone decided to implement the (new) BaseClass
like that, and release it without testing it properly.
Actually, there is a possible way that you can get your CustomClass
to work. The BaseClass::hashCode(ObjectLocator, HashCodeStrategy2)
method is public and not final, so you could override it on your CustomClass
as follows:.
@Override
public int hashCode(ObjectLocator locator, HashCodeStrategy2 strategy) {
return System.identityHashCode(this);
}
And indeed, it may be that the implementers of BaseClass
intend you to do this. But I would still argue that BaseClass
is broken:
- Coding the class so that
hashCode
returns 1 as the default behavior is nasty. - There is no javadoc in
BaseClass
to explain the need to override the method. - Their (unannounced?) change to the behavior of
BaseClass
is an API breaking change. You shouldn't do stuff like that, without very good reason, and without warning. - The default behavior of the corresponding
equals
method is objectively wrong.
Same hashCode but two different entries in HashMap
Hash collisions aren't the only limiting factor in the map construction, however returning a constant 1
is a "worst" case Map and it behaves like a LinkedList (every element is in one bucket). From the Object.hashCode()
Javadoc
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 hash tables.
Related Topics
How to Add Local .Jar File Dependency to Build.Gradle File
Using Threads to Make Database Requests
Difference Between Wait() and Sleep()
Access Restriction on Class Due to Restriction on Required Library Rt.Jar
Java Arrays Printing Out Weird Numbers and Text
Getting the Ip Address of the Current Machine Using Java
How to Calculate Someone'S Age in Java
Why Do I Get an Unsupportedoperationexception When Trying to Remove an Element from a List
How to Check If a String Contains Another String in a Case Insensitive Manner in Java
Is Java.Sql.Timestamp Timezone Specific
Why Can't I Do Assignment Outside a Method
Polymorphism VS Overriding VS Overloading
Java 8 Lambda Function That Throws Exception
Why Is the Java Main Method Static
How to Address Unchecked Cast Warnings
Org.Xml.Sax.Saxparseexception: Content Is Not Allowed in Prolog
Are Getters and Setters Poor Design? Contradictory Advice Seen