HashMap works on the principle of Hashing. There are several terms: key, hash code, hash function, bucket, entry in HashMap
public int hashCode()
hashCode returns an integer code, we can call this method as hash function
A bucket is used to store key value pairs . A bucket can have multiple key-value pairs . In hash map, bucket used simple linked list to store objects. In a bucket, there maybe one or more entries inside the linked list
|
1 2 3 4 5 6 7 8 9 10 |
Public V get(Object key) { if (key ==null) {...} int hash = hash(key.hashCode()); // defends against poor quality hash functions use hash to find the value saved in the array if(value is null) not exist, return null else return value } |
hash (getting from hash(key.hashCode())) is used to find the bucket location at which the Entry object is stored . Entry object stores in the bucket like this (hash,key,value,bucketindex) .
How to avoid the conflict hash code ( for example, key 1 and key 2 might have the same hashcode), both records will be saved in the bucket as a linked list (two entries). When we want to receive the value for key2, it will get the bucket which has two entries in the list. we traverse through linked list , comparing keys in each entries using keys.equals() until it return true. Then the corresponding entry object Value is returned .
The figure below demos the concept how the data can be saved in the HashMap
In Summary
1. HashMap works on the principal of hashing
2. HashMap uses the hashCode() method to calculate a hash value. Hash value is calculated using the key object. This hash value is used to find the correct bucket where Entry object will be stored
3. HashMap uses the equals() method to find the correct key
4. more than one key have the same hash value, Entry objects are stored as a linked-list with in a same bucket. With in a bucket values are stored as Entry objects which contain both key and value.
