How HashMap retrieves different values if hashcode key is the same but equal method return false false
I can't figure out the working HashMap pattern. Please help to understand this.
Let's say we have two objects Obj1 and Obj2 having the same Hashcode as 1212 . Now when we run "==" and equal, it returns false.
Now I am using ValueObj1 and Valueobj2 as a value in a HashMap with keys Obj1 and Obj2 respectively. I believe both values will be stored in the same bucket as the list .
My question is how HashMap selects Valueobj2 for Obj2 and ValueObj1 for Obj1 . Let's say there are such objects and values. How does this key association -> value work internally, although the hashcode is the same, but the values are different.
Assuming both conditions are not equally overridden and overridden .
source to share
A HashMap
/ HashSet
implements on the bucket a list of keys (in case, Map
along with values). If several keys have the same value hashCode
, they are placed in this list.
Thus, the lookup method first retrieves the hashCode
requested key and then iterates through the corresponding list until the method equals
succeeds. In case HashSet
it means found key
, in case HashMap
it returns the other side of the tuple: the value.
The memory HashMap
works as follows:
+--------+--------+--------+--------+
| 00 | 01 | 10 | 11 |
+--------+--------+--------+--------+
| | | |
k00/v00 _ k06/v06 _
| |
k08/v08 k14/v14
| |
k04/v04 _
|
_
What you see is above four buckets. Each bucket has a list (items below it) that stores a tuple of keys ( k
) and values ( v
). Since there are only four buckets, the hash algorithm uses modulo 4, so the key k06
with the value v06
will be placed in the bucket 06 mod 4 = 02
this way 10
. If you add a second key k14
with 14 mod 4 = 02
this way, 10
it is simply added to the list.
Since the values are saved with it, you can perform a quick search operation. Thus, the key is saved along with the value .
You've noticed that iterating over a (linked) list is an expensive operation. But point a HashMap
is that one hopes that the number of hash collisions to use the correct term (the number of keys sharing the same bucket) is very small. Usually you can expect two or three items per bucket. Thus, performance gains are achieved by selecting the correct bucket at constant time , bucket searches require linear time, however (or in the case of a full key order, one can implement a (balanced) binary tree for logarithmic time searches). The worst case, however, HashMap
can achieve the same performance as writes ArrayList
/LinkedList
but considering the hash function was decently designed, the coefficients are very low.
source to share
You can always look at the code.
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
- Therefore, it first gets the hash for the given key.
- Using this hash, it finds the table (in other answers as a bucket).
- For each record in the bucket, it checks if the
equals
key has the table record key and if it found the correct item.
Splitting keys with hashes in buckets reduces the size of linear searches using comparisons equals
. So you can see how harmful it is to return a fixed value for hashcode. See for tips on good hashcode computation.
source to share
HashMap
works by dividing its contents into buckets based on the hash value of the key. Each bucket, in turn, contains a list of records, a record consisting of a key and a value.
Let's say we want to look x
at the map. We calculate x.hashCode()
and select the appropriate bucket. We then iterate over the bucket list and select the entry e
where e.key
equals x
. Then we return e.value
.
pseudocode:
class Map {
class Entry {
Object key, value;
}
List<List<Entry>> buckets;
Object get(Object key) {
List<Entry> bucket = buckets.get(key.hashCode() % buckets.size());
for (Entry entry : bucket) {
if (Object.equals(key, entry.key) return entry.value;
}
return null;
}
}
(Disclaimer: Using% to compute the bucket index is simplistic and won't work as it is, it's just to convey the general idea)
source to share
hashcode()
the method is called and the hash code is calculated. This is hashcode
used to find the index of the array to store the Entry object.
indexFor(hash,table.length)
used to compute the exact index in the array of the table to hold the Entry object.
two key objects having the same hashcode
(which is known as a collision)
In a hashmap, a bucket uses a simple linked list to store objects.
if two keys have the same hash, then store the key-value pair in the same bucket as the existing key.
How do you retrieve the value object when two keys with the same hashcode are stored in a hashmap? Using hashcode wo go to the right bucket and using equals we will find the right item in the bucket and then return it.
HashMap get () function
If the key is non-zero, it will call the hash function on the key object.
int hash = hash(hashValue)
hashvalue
used to find the bucket location where the Entry is stored. The login object is stored in a bucket as shown in the figure (hash,key,value,bucketindex)
.
source to share
Comparing two objects with is ==
not a good idea, as it checks if two objects are actually associated with the same objects in memory.
There is a good Wikipedia article on hashtables on Wikipedia. Hashmap
in java it is contained inside a bucket array.
When you put a new pair <key, value>
(or in your case <obj1, valueObj1>
), the bucket number is calculated depending on obj1.hashcode()
. This pair is added to the selected bucket, which is LinkedList
inside to store the actual pairs <key, value>
.
When you try to search valueObj1
with a key, obj1
hashmap calculates the bucket number that pair is in and iterates over all the elements LinkedList
that compare the keys with equals()
. If it equals()
returns instantly true
, it means the item found was found.
source to share