How to Find Number in Phonebook Java Hashmap

INTRODUCTION

In Java, you might have heard about the Map interface (which extends the Collection Interface). There are some implementation classes of map interface, out of which one such class is HashMap (present in java. util package). It is denoted as HashMap<K, V> where K stands for Key and V for value. In simpler terms, HashMap<K, V> is a data structure that stores elements in the form of a key-value pair. These key-value pairs are also termed as an Entry of HashMap. Keys are unique, and duplicate keys are not allowed. It stores values based on keys, and it can be accessed using keys. Hashmap allows multiple null values and only one null key.

HashMaps are non-synchronized, meaning that they are not thread-safe. If multiple threads access the hashmap at the same time, they will modify the map structurally. HashMaps are an unordered collection of key-value pairs. They do not maintain the insertion order. They are much faster in terms of retrieving data as compared to arrays and linked-list, with constant time performance for the basic operations. Its initial default capacity(number of elements that can be stored) of hashmap is 16, and the default load factor is 0.75. We will discuss the capacity and load factor a little later in the coming sections.

Check the hierarchy diagram above; the HashMap class extends the AbstractMap class and implements the Map, Serializable and Cloneable interfaces.

Check the hierarchy diagram above; the HashMap class extends the AbstractMap class and implements the Map, Serializable and Cloneable interfaces.

Declaration of Hashmap class :

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

K: type of Key

V: type of Value

CONSTRUCTORS IN HASHMAP

There are four constructors of the hashmap, all of which have public access specifiers.

1.Hashmap()

 It is the default constructor that creates an instance of a hashmap with the initial capacity of

   16 and load factor 0.75.

HashMap<K,V> hm = new HashMap<K,V>();      // instance creation

Program to demonstrate default Hashmap Constructor :

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {        HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4); 	    System.out.println(hm);     } }        

Output: {Red=1, Blue=2, Yellow=4, Green=3} [order of insertion is not preserved]

 2.HashMap(int initialCapacity)

This constructor creates an instance of a hashmap with the specified initial capacity and

      default load factor 0.75.

HashMap<K,V> hm = new HashMap<K,V>(int initialCapacity);   // instance creation

Program to demonstrate above Hashmap Constructor :

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(5); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4); 	    System.out.println(hm);      } }        

Output: {Red=1, Blue=2, Yellow=4, Green=3}

3.HashMap(int initialCapacity, float loadFactor)

This constructor creates an instance of a hashmap with the specified initial capacity and the

    specified load factor.

HashMap<K,V> hm = new HashMap<K,V>(int initialcapacity, float loadfactor);

Program to demonstrate above Hashmap Constructor :

import java.io.*; import java.util.*;  public class Hashmap {     public static void main(String args[]) {         HashMap<String, Integer> hm = new HashMap<String, Integer>(5,0.75f); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4); 	    System.out.println(hm);     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

4. HashMap(Map map)

This constructor creates an instance of a hashmap with similar mappings as the given Map.

HashMap<K,V> hm = new HashMap<K,V>(Map m); //instance creation

Program to demonstrate above Hashmap Constructor :

import java.io.*; import java.util.*;  public class Hashmap {      public static void main(String args[]) {        	 Map<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4); 	    System.out.println(hm);  	  HashMap<String, Integer> hm1 = new HashMap<String, Integer>(hm); 	  System.out.println(hm1);     } }        

Output :

     {Red=1, Blue=2, Yellow=4, Green=3}

     {Red=1, Blue=2, Yellow=4, Green=3}

OPERATIONS OF HASHMAP

The hashmap includes basic operations like add, get, update and delete the elements, just like any other data structure. Following are the basic operations :

1. Add Elements

To insert the elements or an entry in a Hashmap, the put(K, V) method is used.

K:type of key

V:type of value

Program to demonstrate put method :

import java.io.*;  import java.util.*;   public class Hashmap {      public static void main(String args[]) {        	 Map<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);                  System.out.println(hm);     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

2. Remove Elements

The remove(K) method takes the key as the argument and deletes the entry for the given key if it is present on the map. We also have one more remove(K, V) method to delete the entry.

Program to demonstrate remove operation using remove ():

import java.io.*;  import java.util.*;   public class Hashmap {      public static void main(String args[]) {        	 Map<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);                  System.out.println(hm); 	    hm.remove("Blue");    //remove Blue key 	    System.out.println(hm);  	    } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Yellow=4, Green=3}

remove(K, V):This methodtakes key and value as the argument and removes the entry only if both the key and value match.

Program to remove the entry using remove(K, V) :

import java.io.*;  import java.util.*;   public class Hashmap {          public static void main(String args[]) {          Map<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);                  System.out.println(hm); 	    hm.remove("Blue",3); 	    System.out.println(hm);; 	    hm.remove("Blue",2); 	    System.out.println(hm);  	    } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Yellow=4, Green=3}

3. Access elements and Traverse hashmap

    3.1 Access one particular value associated with a key using get(K)

The value present in a hashmap can be accessed using the method get(K) . The key must be passed in the argument, and the value stored in that key will be fetched.

Program to access the value using the get(K) method:

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {         HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    System.out.println(hm.get("Green"));     } }        

Output:

   {Red=1, Blue=2, Yellow=4, Green=3}

   3

3.2 Access only the keys of elements

If you want to retrieve only theset of keys, the keySet() method will return just the set of keys in hashmaps.

Program to show usage of method keySet():

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    System.out.println(hm.keySet());     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

[Red, Blue, Yellow, Green]

3.3Access only the values of elements

The values()  method helps to obtain theset of values.

Program to show usage of values() :

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    System.out.println(hm.values());     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

[1, 2, 4, 3]

3.4 Access the entries of HashMap

The entrySet()  method will return theset of entries(<K, V>) in a hashmap.

Program to show usage of entrySet():

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    System.out.println(hm.entrySet());     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

[Red=1, Blue=2, Yellow=4, Green=3]

3.5 Traverse the HashMap

After knowing how to access the elements in a hashmap, let us see how to iterate ortraverse the hashmap. The idea is to iterate over the set of entries using the for-each loop and then access the key and values in an entry using the getKey()  and getValue()  methods. We use Map.Entry(K, V) allows us to access the entries of a map.

Program to traverse the entries of a hashmap :

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    for(Map.Entry<String, Integer> e: hm.entrySet()) 	    { 	        System.out.println(e.getKey()+","+e.getValue()); 	         	    }     } }        

Output :

{Red=1, Blue=2, Yellow=4, Green=3}

Red,1

Blue,2

Yellow,4

Green,3

4.Update the value

If you want to update the value stored in a given key, you can either use put(K, V)  or

    replace() method.

Program to update the value using put():

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    hm.put("Yellow",5);    //updates the value of key Yellow             System.out.println(hm);     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=5, Green=3}

Program to update using replace(K,V):

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    hm.replace("Yellow",6);                 System.out.println(hm);     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=6, Green=3}

FEATURES OF HASHMAP

Hashmap is a Map-based collection class that contains the values based on a key.Let us discuss some key features of it :

• It is an unordered collection; that is to say, it does not maintain the keys and values in the same order in which they were inserted.
• It cannot have duplicate keys; however, it can have duplicate values.
• It allows one null key and multiple null values.
• HashMap uses an inner classEntry<K, V> to store data in nodes of a multiple singly linked list.
• Its initial default capacity is 16, and its load factor is 0.75
• They are not synchronized (not thread-safe) as multiple threads can modify their structure when accessing it. So, we must externally synchronize these concurrent modifications. We can useCollections.synchronizedMap(Hashmap) to synchronize it.
• It makes use of a technique calledHashingto transform a key into a shorter hash key which makes it easier to insert and retrieve data from a hashmap. We will learn about the working of Hashmap in detail in the coming sections.

Internal Working of HashMap in Java

What is HashMap?

Basically,HashMapis one of the most popular Collection classes in java. HashMap internally usesHashTableimplementation. This HashMap class extendsAbstractMapclass that implements theMapinterface.

Few important points to aboutHashMap :

1. HashMap uses its static inner classNode<K,V> for storing the entries into the map.
2. HashMap allows at most onenullkey and multiplenullvalues.
3. TheHashMapclass does not preserve the order of insertion of entries into the map.
4. HashMaphas multiple buckets or bins which contain a head reference to a singly linked list. That means there would be as many linked lists as there are buckets. Initially, it has a bucket size of 16 which grows to 32 when the number of entries in the map crosses the 75%. (That means after inserting in 12 buckets bucket size becomes 32)
5. HashMap is almost similar to Hashtable except that it'sunsynchronized and allows at max one null key and multiple null values.
6. HashMapuseshashCode() andequals() methods on keys for theget andputoperations. So HashMap key objects should provide a good implementation of these methods.
7. That's why theWrapper classes likeInteger and String classes are a good choice for keys for HashMapas they are immutable and their object state won't change over the course of the execution of the program.

Note: Java HashMap is not thread-safe and hence it should not be used in multithreaded application. For the multi-threaded application, we should use ConcurrentHashMap class.

How to Initialize the Constructor with Our Own Capacity and Load factor?

There are mostly 4 different constructors that can be used while creating the hashmap.

These are as follows :

Frequently Used Hashmap Methods:

• public boolean containsKey(Object key): Returnstrueif this map contains a mapping for the specified key.
• public boolean containsValue(Object value): Returns true if this map maps one or more keys to the specified value.
• public V get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
• public V put(K key, V value): Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value.
• public void putAll(Map<? extends K, ? extends V> m): Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this map had for any of the keys currently in the specified map.
• public V remove(Object key): Removes the mapping for a key from this map if it is present (optional operation).
• public boolean isEmpty(): A utility method returning true if no key-value mappings are present in the map.
• public int size(): Returns the number of key-value mappings in this map. If the map contains more thanInteger.MAX_VALUE elements returnInteger.MAX_VALUE.
• public Set<K> keySet(): Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
• public Set<Map.Entry<K,V>> entrySet(): This method returns a Set view of the HashMap mappings. This set is backed by the map, so changes to the map are reflected in the set, and vice-versa.

Let's See an Example of Hashmap and Its Functions:

Let's say we want to have a mapping of all the contacts of our friends and relatives. We'll have a myPhoneBook map of a name (String type) as a key and a number(Long) as a value.

Output:

          — — — — -: Contacts in my Phone List : — — — — —  Name : John Number : 8923535110 Name : Vikram Number : 8149535110 Name : Mark Number : 7080535110  — — — — — — — — — — — — — — — — — — — — — — — —  No of contacts in myPhoneBook : 3 Contact number of Vikram : 8149535110 Delete Mark's contact : 7080535110        

Now Let's Look at the Internal Working Of hashmap:

• HashMap uses its static inner classNode<K,V> for storing map entries. That means each entry in hashMap is aNode. Internally HashMap uses ahashCodeof the key Object and this hashCode is further used by thehash function to find the index of the bucket where the new entry can be added.
• HashMap uses multiple buckets and each bucket points to aSingly Linked List where the entries (nodes) are stored.
• Once the bucket is identified by the hash function using hashcode, then hashCode is used to check if there is already a key with the same hashCode or not in the bucket(singly linked list).
• If there already exists a key with the same hashCode, then theequals() method is used on thekeys. If the equals method returnstrue, that means there is already a node with the same key and hence the value against that key isoverwrittenin the entry(node), otherwise, a new node is created and added to this Singly Linked List of that bucket.
• If there is no key with the same hashCode in the bucket found by the hash function then the new Node is added into the bucket found.

Each Node Has the Following Structure:

final int hash; final K key; V value; Node<K,V> next;        

In the above example, we assume that all these five keys have the same hashCode, then the bucket number or index returned by hash function would be the same for these five keys (in this case bucket 4) and hence they are put into the same bucket. Later the keys are compared using the equals() method to check whether the key is already present or not. But we assumed these five keys are having different key content and hence 5 nodes are there in the list.

To have a high-performance hashMap we need good implementation of hashCode() and equals() method along with hash function.

A Very Important Note That You Must Know:

Before java 8, singly-linked lists were used for storing the nodes. But this implementation has changed to self-balancing BST after a thresold is crossed (static final int TREEIFY_THRESHOLD = 8;). The motive behind this change is that HashMap buckets normally use linked lists, but for the linked lists the worst-case time is O(n) for lookup. Also note that Ordinary binary search trees have pathological cases where they become O(n) [basically BST becomes skewed], but red-black/AVL trees are specifically designed to prevent these cases. In a HashMap with linked lists, if we have a really really awful hash function, we could end up with all the items hashing to the same bucket and get O(n) lookup, But it seems like with this red-black/AVL tree scheme, even if all the items hashed into the same bucket, we would get O(log⁡n) lookup in worst of worst scenario.

Let's See This Mechanism Diagrammatically:

For this example, I have assumed the threshold value as 5 but ideally, it should be by default 8.

In this example, we assume all the five keys key1 to key5  have the same value of hashCode  and hence Hash function returns the same bucket number that is 4. Also equals method on all these five keys returns false which means the object content of these keys is different and hence 5 nodes are created and added to the tree.

Re-Hashing :

Whenever the number of entries in the hashmap crosses thethreshold value then the bucket size of the hashmap is doubled and rehashing is performed and all the already existing entries of the map are copied and new entries are added to this increased hashmap.

Threshold value = Bucket size * Load factor        

Eg. If bucket size is 16 and the load factor is 0.75 then the threshold value is 12.

Time Complexity:

1. In a fairly distributed hashMap where the entries go to all the buckets in such a scenario, the hashMap hasO(1) time for search, insertion, and deletion operations.
2. In the worst case, where all the entries go to the same bucket and the singly linked list stores these entries, O(n)time is required for operations like search, insert, and delete.
3. In a case where thethresholdfor converting this linked list to a self-balancing binary search tree(i.e. AVL/Red black) is used then for the operations, search, insert and deleteO(logN) is required as AVL/Red Black tree has a max length oflogN in the worst case.

Why Hashmap Should Not Be Used for Multi-threaded Environments?

Output:

Exception in thread "main" java.util.ConcurrentModificationException  at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)  at java.util.HashMap$KeyIterator.next(HashMap.java:1469)  at ExceptionExample.main(ExceptionExample.java:16)        

When a new entry got inserted into the HashMap, the Iterator for the keys is failing. Actually, the Iterator on Collection objects isfail-fast i.e any modification in the structure or the number of entries in the collection object(in our case phoneBook) will trigger the exception. And hence the exceptionConcurrentModificationExceptionis thrown. Basically, HashMap contains a variable to count the number of modifications and the iterator uses it when you call its next() function to get the next entry.

Now let's understand, if we're iterating a map, why doesphoneBook.remove() cause aConcurrentModificationExceptionto be thrown whereaskeyIterator.remove() does not?

Consider this example:

Map<String, Long> phoneBook = new HashMap<String, Long>(); phoneBook.put("Vikram",8149101254L); phoneBook.put("Mike",9020341211L); phoneBook.put("Jim",7788111284L);  Iterator<String> keyIterator = phoneBook.keySet().iterator();  while (keyIterator.hasNext()){     String key = keyIterator.next();     if ("Vikram".equals(key)){         //keyIterator.remove();#1         //phoneBook.remove("John");#2     } }        

If we uncomment line#1, it will work fine. If we uncomment line #2 (but leave#1 commented) then it will cause the subsequent call tokeyIterator.next() to throwConcurrentModificationException.

The reason is that an iterator is a separate object that has some references to the internal state of the underlying map object. If we modify the map while the iterator is in operation, it could cause the iterator to behave badly, e.g. by skipping elements, repeating elements, indexing off the end of the array, etc. It attempts to detect such modifications and so it throwsConcurrentModificationException.

Another point to note is that removing elements through the iterator works and does not cause exceptions. This updates the underlying map and the iterator's state that refers to the internals of the map, so everything can stay consistent.

However, there is nothing special aboutkeyIterator.remove() that makes it work in all cases. If multiple iterators are iterating over the same map, modifications made by one will cause problems for the others. Consider:

Iterator<String> keyIterator1 = phoneBook.keySet().iterator(); Iterator<String> keyIterator2 = phoneBook.keySet().iterator(); keyIterator1.remove(); keyIterator2.remove();        

We now have two iterators pointing to the same map. If we modify the map using one of them, it disrupts the operation of the second, so the call tokeyIterator2.remove(); will result inConcurrentModificationException.

The above scenario can be overcome usingConcurrentHashMapand hence it's advised not to use hashmap for multi-threading applications

INTERNAL STRUCTURE OF HASHMAP

Considering the internal structure of the hashmap, it has aNode<K, V> which represents the inner classEntry<K, V> that stores the mappings of the hashmap. Each key-value pair is stored in an object of Entry<K, V> class. This class is a static inner class of Hashmap. Each node has four fields in it, namely :

1. Hash key (shorter key obtained post hashing)
2. Key
3. Value
4. The node next (a reference to another Entry, just like a singly linked list)

Points to know about a node in a HashMap:

• The hash attribute stores the hashcode of the key.
• The Key attribute stores the key, and it is of final type.
• Value attribute holds the value of the element.
• Entry<K, V> next holds the pointer to the next key-value pair.

Declaration of inner class Entry<K,V>:

static class Entry<K,V> implements Map.Entry<K,V>{ 	int hash;  	final K key; 	V value; 	Entry<K,V> next; }        

Concept of Buckets in HashMap

Buckets are the array of nodes or entries that store elements. Many nodes can have similar buckets. The hashmap stores the elements just like a singly linked list, and a list of entries are termed as Buckets.These nodes are connected through a linked list. The capacity of hashmap and the number of buckets have a relation :

The Capacity of HashMap = Number of buckets * Load factor

Structure of hashmap

Internal Working of a HashMap

Hashmap uses a technique calledHashing.It is a process to convert a given key into a hash-key using the hashCode()  method. Hashing also involves the equals()  method to check if the keys are equal. Hashing is used to index and retrieve items faster.The performance of a hashmap is based on the hashcode() method, so this method should be carefully chosen.Let us discuss the hashCode and equals method below.

1. hashCode(): This method generates the hashcode of an object and returns the memory reference of the object passed in the integer form. It returns a random integer unique to each instance. The result of this method is termed ahash.

                                                 Syntax: public int hashCode()

2. equals():Hashmap uses this method to check if two objects are equal or not. If this method returns true, they are equal, else they are not.

Syntax:boolean equals (Object ob)

Program to show usage of equals() :

import java.io.*; import java.util.*; public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>();         HashMap<String, Integer> hm1 = new HashMap<String, Integer>(); 	    	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);             System.out.println(hm);          	    hm1.put("Red",1); 	    hm1.put("Blue",2); 	    hm1.put("Green",3); 	    hm1.put("Yellow",4); 	    System.out.println(hm1); 	    	    System.out.println(hm.equals(hm1)); 	        } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Green=3}

true

Collisions

Collisions occur when distinct keys produce the same hashcode value, and the element is already present at that index value. To avoid or reduce collisions, a good hash function should be used, ensuring the best distribution of values throughout the hashmap. When a collision occurs, we use the chaining technique, as shown in the 2nd example above, to distribute the values.

Calculating Index in Hashing

Indexes are generated in hashing to reduce the size of an array.If the hashcode of the key is used as an index, the integer value obtained might be large, and it can increase the size of the array.

The Index is calculated using the formula :

Index = hashCode(Key) & (n-1)

n = the size of array/bucket

 (n = 16 in case of default)

Hashing for Put() operations

Let us consider an empty hashmap with the default capacity of 16 (n=16).

1.No Collision: Suppose you want toputthe entry ("welcome",15) in a newly created map.

• As per the concept of hashing, the hash will be generated first using the hashCode(key)
• Calculate hash = hashCode("welcome"); [suppose it is 200]
• Calculate index = hash & (16-1),        [evaluates to 8]
• Create a node/Entry object with hash, key, value, and reference pointer.
• Place this object at index value 8 if it is empty.

2.Collision: Sometimes, a scenario might come where the index will be the same, and collision can occur. Let's try inserting ("wait",16) in the hashmap now.

• Calculate hash = hashCode("wait"); [suppose it is 120]
• Calculate index = hash & (16-1),   [evaluates to 8]
• Create a node object with hash, key, value, and reference pointer.
• Place this object at index value 8 if no other value is placed there.
• If some value is placed there, like in our case, it is a state of collision.
• In case of collision, check through equals() if the keys are similar.
• If the equals() method returns true, replace the value with the current value.
• If the equals() method returns false, then point this new node object to the previous node through a linked list at the same index value. (Chaining method)
• In our case, since the keys, welcome and wait are different, we will place a new node using a link list.

Hashing for the Get() operation

Let us see how to use hashing to implement the get operation. The get(Key) is used to get the value at the given key.

Example:No Collision

Let's say you want to find the value of a key "welcome", follow the below steps of hashing.

• Calculate hash = hashCode("welcome"); [assume 200]
• Calculate index = hash & (n-1) , n=16   [index evaluates to 8]
• Check the index 8; if this key matches with the element's key using the equals() method, then return the value.
• If the key does not match, then check the next element's key and so on.
• In our case, the key matches, so the value of the key "welcome", i.e. 15, will be returned.

Example:Collision

Let's say you want to find the value of a key "wait" :

• Calculate hash = hashCode("wait");    [assume 120]
• Calculate index = hash & (n-1) , n=16   [index evaluates to 8]
• Check that index; if this key matches with the element's key using the equals() method, then return the value.
• Here, it does not match, so check the next element (next node) in the list. The next key at this index is waiting. Recheck the keys; they match now, so the value of the key "wait" [i.e. 16] will be returned.
• If the next reference of the Node is null, return null, else move to the next node and repeat the key matching process.

PERFORMANCE OF HASHMAP

The performance of the hashmap is based upon two significant factors :

1. Initial Capacity
2. Load Factor

Initial Capacity:The initial number of buckets a hashmap has when its instance is created. Its default value is 16. That is, initially, the hash map can store 16 key-value elements.

Load Factor:It is a measure of how much percentage the hashmap is allowed to fill before its capacity increases. The default load factor value is 0.75, ranging between 0 to 1 usually.

Some other terms related to performance are :

Threshold:It is the product of the load factor and the capacity of the hashmap. Default threshold value is 0.75*16= 12. When 12 elements are filled in the hashmap, we need to stop inserting more elements into it. Rehashing will be done, which will double the capacity of the hashmap.

Rehashing:It is a way of doubling the capacity when the threshold value is reached. When the threshold value is crossed, the rehashing is done so that the bucket now has twice the capacity and the operation takes less time.

Time Complexity of HashMap

Talking about the time complexity, theperformance of a HashMap operation depends upon thehash function implementation. If the hashcode implementation is good (no hash collision), then the best, worst and average time complexity isO(1). In a situation where the hashcode implementation is bad (hash which gives a collision), complexity would beO(n). Also, the iteration over a hashmap depends upon its capacity and the key-value pairs. If the capacity is high, the iterations will increase, which will increase the time complexity and affect the performance.

Performance Improvement

Regarding performance improvement in Hashmap, two factors that must be chosen appropriately are theoptimized hash function andcapacity. The hash function implementation should be such that the hashcode gives no to fewer collisions. Keeping the capacity high will increase the iterations and the time complexity, so both these factors must be carefully chosen.

The changes that have been done in JAVA 8 :

Some hashmap performance improvement changes have been done in JAVA 8 to handle the hash collisions. Before Java 8, the hashmap performance was low in the case of hash collisions which had an impact on the complexity. Due to collisions, both the keys and values were placed in a node, and in the worst case, the complexity was O(n) due to link list traversal. Changes are as follows:

• Initially, the hash map will store the entries in a singly linked list, but when the threshold value is reached, the self-balancing BST trees will be used instead of a linked list. The benefit of using BST is that we get the worst-case complexity is O(log n).

METHODS IN HASHMAP

Some examples of the other essential functions of hashmap that are defined above :

Program to show the size of the hashmap :

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	     	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    System.out.println(hm.size());     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

4

Program to show putAll() and putIfAbsent() method:

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	    	    	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    HashMap<String, Integer> hm1 = new HashMap<String, Integer>(); 	    hm1.putAll(hm);  //putAll 	    System.out.println(hm1); 	    hm.putIfAbsent("Orange",7);  //putIfAbsent 	    System.out.println(hm); 	        } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Orange=7, Green=3}

Program to show containsKey() and containsValue() methods:

import java.io.*; import java.util.*;  public class Hashmap{     public static void main(String args[]) {          HashMap<String, Integer> hm = new HashMap<String, Integer>(); 	    	    	    hm.put("Red",1); 	    hm.put("Blue",2); 	    hm.put("Green",3); 	    hm.put("Yellow",4);  	    System.out.println(hm); 	    System.out.println(hm.containsKey("Green")); 	    System.out.println(hm.containsKey("Orange")); 	    System.out.println(hm.containsValue(3)); 	    System.out.println(hm.containsValue(7));     } }        

Output:

{Red=1, Blue=2, Yellow=4, Green=3}

true

false

true

false

Synchronized HashMap

As already stated above, Hashmaps are unsynchronised, meaning they are not thread-safe. When simultaneously accessing the hashmap, multiple threads can change it structurally, and then it has to be synchronized externally. External synchronization can be done in the following way :

Map m = Collections.synchronizedMap(Hashmap map);

Thank you for reading it.

KEEP LEARNING KEEP GROWING!!!

Thanks To: javarevisited & mygreatlearning

How to Find Number in Phonebook Java Hashmap

Source: https://www.linkedin.com/pulse/hashmap-java-everything-you-need-know-omar-ismail

Share :