|
Answer» The COLLISION problem is, whenever the hash function returns the same INDEX position for the different key, then a collision occurs. The collision detection technique is also called collision detection. Now, let's move to the collision prevention technique. The HashMap uses below algorithms to resolve the collision problem. - Linear probing: This algorithm is default implementation to resolve the collision issue, lets see how it works, in this approach HashMap implements LinkedList data structure to store the elements, while collision occurs HashMap first check the index position using the hashcode of key, if it founds same index position and conflict with other keys, then HashMap calls the equals() method of the Key, so using the composite approach of hashcode() and equals() method, the HashMap start traversing on linear(one by one) elements in LinkedList, because HashMap also maintain the equal() method of information in the linked LIST to store the elements, using both this approach the HashMap finds the correct elements in the linked list.
- Below is the CODE snippet forget operation in the HashMap. Where get method takes the Key object as input and returns the Value object as V and checking WHETHER the Key is null, then calculate the hash code and iterate over the hash map.
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;
}
|
