Hashmap is an data structure in which entry is stored as an key-value pair.
Internally, it is an array of nodes and node represents a class having following objects.
Key is always unique. Maximum one null key allowed in a hashmap.
a)int hash
b)K key
c)V value
d)Node next
Hashing : It is a process to get an integer representation of the key. It is used to calculate bucket location of the entry(key-value). Integer representation is calculated by calling hashcode() method on the key object.
Now let’s discuss equals method.
Hashmap equals:
It is used to compare 2 objects which are keys in the case of hashmap. Equals method is part of java.lang.object class. Equality is checked on the basis of the reference(hashcode) of the 2 objects.
If it is the same object, then equals method would return true. If those are different objects, it would be false always.
But sometimes, 2 different objects can be equal too but their member variables match.
For example, consider the below 2 objects from class A having just 2 member variables x & y.
A a = new A();
A b =new B();
a.x =5; b.x = 5;a.y =7; b.y = 7;
So objects a and b are ideally equal. But if we call the equals method on the object, it would return false since the reference is different for 2 objects.
a==b returns false.
In such case, we need to override the equals method in the class A and derive equality on the basis of the member variables.
boolean equals(Object key)
{
if (this.x == key.x && this.y == key.y)
{ return true }
else return false
}
Bucket:
A bucket is one element of hashmap array. It is used to store nodes. Two or more nodes can have the same bucket.
In that case, linked list is used to connect the nodes inside that bucket location.
Now let’s see how an bucket index is calculated. The hash function internally used for index location calculation is:
index = hashcode(k) & (n-1)
so if hashCode of key = 117 and size of array =16 then index loc = 5.
Ideal candidates for keys:
String is the best candidate for key since it is immutable and there is no need to override equals method.
Load factor:
The Load factor is a measure that decides when to increase the HashMap capacity to maintain the get() and put() operation complexity of O(1). The default load factor of HashMap is 0.75f (75% of the map size).
Insertion,deletion and fetch in hashmap:
HashMap<Integer, String> hash_map = newHashMap<Integer, String>(); hash_map.put(10, "Java"); hash_map.put(15, "Guru");
Here 10 and 15 are keys.
String retVal= (String)hash_map.remove(10);
It removes the entry 10, ‘Java’.
String retVal= (String)hash_map.get(15);
It fetches Guru as the value.