- The underlying data structure is HashTable.
- Insertion order is not preserved and it is based on the HashCode of keys.
- HashMap is an implementation of Map interface, in this collection we provide an input key and lookup for values
- Duplicate keys are not allowed but duplicate values are allowed
- Null can be used as key only one time, null can be used as values multiple times
- Implements Serializable and Clonable but not Random Access
- Best choice if frequent operation is search
- Under the hood HapMap is a collection on Entry Objects which are independent to each other
- It is a data structure which allows us to store object and retrieve it in constant time O(1)
- In hashing, hash functions are used to link key and value in HashMap.
- Objects are stored by calling put(key, value) method of HashMap and retrieved by calling get(key) method.
- When we call put method, the hashcode() method of the key object is called so that the hash function of the map can find a bucket location to store value object, which is actually an index of the internal array, known as the table.
- HashMap internally stores mapping in the form of Map.Entry object which contains both key and value object.
- LoadFactor is 75% if more than that data is reached then memory is doubled
- Big O Notation
- Retrieval Time – O(1)
- HashMap m = new HashMap<>();
- Default Initial Capacity 16
- Load Factor as 0.75
- HashMap m = new HashMap(int initialCapacity)
- HashMap m = new HashMap(int initialCapacity,float loadFactor)
- HashMap m = new HashMap<>(Map m);
Note: Changing the value of Entry, the actual value inside map is changed since it is a reference to the same map.
How to get a Synchronized version of HashMap ?
HashMap m = new HashMap();
Map m1 = Collections.synchroinzedMap(m);
By default HashMap is non synchronized but we can get synchronized version of HasMap by passing HashMap into Collections sysnchronizedMap()
HashMap Internal Working – Implementation
Hashing – Transforming of string to a short fixed-length value that represents a original string. A short value helps in indexing an faster searches
- Everymethod in java has hashCode() method since it is present in object class
Properties of hashcode :
- Whenever it is invoked on the same object more than once during an execution of a Java application, the
hashCodemethod must consistently return the same integer.
- If two objects are equal according to the
equals(Object)method, then calling the
hashCodemethod on each of the two objects must produce the same integer result.
- Not necessary to produce two different hash for different value but it should improve the performance of HashMap
Reference for Internal Working:
- Initially a bucket of size 16 is created. (Represented as Array of nodes<k,v> with are implementation of red-black tree).
- If you set the initial capacity to 10 also the initial capacity is considered as 16 since only 2 to the power values are considered in hashmap.
- When a put method is called below logic is computed
- Note : Bit wise (&) and mod (%) works in a similar way but for negative hash mod will return a negative result which cannot be an index hence bitwise and (&) is used by developers of HashMap. Below example will clear things out for you
- So the index calculation is always within the class and the data is stored
- When the threshold of the HashMap is breached i.e 0.75 the hashmap expands and all the elements are re-hashed and stored in the bigger array of Node object.
- The Node object stores
- Hashcode of key
- Next node reference
- It is possible for 2 hash to end up in same array location or 2 objects to return same hash, this is called hash collision
- During collision
- We check if the node is null or not
- If null, directly values are assigned to that Node
- If not null then 2 values (hashcode of key and equals with Key) are compared if both of them are not same then same is done with next node (Since these nodes are part of red and black tree) and at the end if non of them matches the values are stored in new node.
- If hashcode and equals of key matches, then old values is returned and new value is stored in the same node.
- We check if the node is null or not
- If you re-size the HashMap its capacity is doubled and all the keys index location are recalculated and stored again in this bigger node object array.
Code of HashMap for more Understanding
- Node inner class of HashMap
- Put method of HashMap
- Get Method of HashMap
Reference of Resizing of HashMap