Tag Archives: hashmap

Collection, Collections

Java: Map Interface Methods and Examples

Leave a comment

In the collection framework, a map contains values on the basis of key and value pairs. This pair is known as an entry.

Points to Remember

  • Map contains unique keys.
  • Map allows duplicate values.
  • Map is useful to search, update or delete elements on the basis of a key.
  • Map is the root interface in the Map hierarchy for Collection Framework.
  • Map interface is extended by SortedMap and implemented by HashMap, LinkedHashMap.
  • Map implementation classes HashMap and LinkedHashMap allow null keys and values but TreeMap doesn’t allow null key and value.
  • Map can’t be traversed, for transversing needs to convert into the set using method keySet() or entrySet().

See Also:

Methods of Map Interface

Method Description
put(Object key, Object value) This method used to insert an entry on the map.
void putAll(Map map) This method inserts the specified map in the map.
V putIfAbsent(K key, V value) This method inserts the specified value with the specified key in the map only if it is not already specified.
V remove(Object key) This method used to delete an entry for the specified key.
boolean remove(Object key, Object value) This method removes the specified values with the associated specified keys from the map.
Set keySet() It returns the Set view containing all the keys.
Set<Map.Entry> entrySet() It returns the Set view containing all the keys and values.
void clear() It is used to reset the map.
V compute(K key, BiFunction remappingFunction) This method computes a mapping for the specified key and its current mapped value (or null if there is no current mapping).
V computeIfAbsent(K key, Function mappingFunction) This method computes its value using the given mapping function, if the specified key is not already associated with a value (or is mapped to null), and enters it into this map unless null.
V computeIfPresent(K key, BiFunction remappingFunction) This method computes a new mapping given the key and its current mapped value if the value for the specified key is present and non-null.
boolean containsValue(Object value)  if some value equal to the value exists within the map then return true, else return false.
boolean containsKey(Object key) if some key equal to the key exists within the map return true, else return false.
boolean equals(Object o) It is used to compare the specified Object values with the Map.
void forEach(BiConsumer action) Mentioned action will perform for each entry in the map until all entries have been processed or the action throws an exception.
V get(Object key) Returns the object that contains the value with respect to the key.
V getOrDefault(Object key, V defaultValue) Returns the value with respect to key is mapped, or defaultValue if the map contains no mapping for the key.
int hashCode() It returns the hash code value for the Map
boolean isEmpty() Check if the map not having any element Returns true if the map is empty or false.
V merge(K key, V value, BiFunction remappingFunction) If the given key is not mapped with a value or with null, associates it with the given non-null value.
V replace(K key, V value) It replaces the specified value with respect to the key.
boolean replace(K key, V oldValue, V newValue) It replaces the old value with the new value with respect to the key.
void replaceAll(BiFunction function) It replaces each entry’s value with the given function on that entry until all entries have been processed or the function throws an exception.
Collection values() It returns a collection of the values contained in the map.
int size() Returns the number of elements in the map.

Map.Entry Interface

Entry is the subinterface of Map. So we will be accessed by Map.Entry name. It returns a collection-view of the map, whose elements are of this class. It provides methods to get key and value.

Methods of Map.Entry interface

Method Description
K getKey() It is used to obtain a key.
V getValue() It is used to obtain value.
int hashCode() It is used to obtain hashCode.
V setValue(V value) It is used to replace the value corresponding to this entry with the specified value.
boolean equals(Object o) It is used to compare the specified object with the other existing objects.
static ,V> Comparator<Map.Entry> comparingByKey() It returns a comparator that compare the objects in natural order on key.
static Comparator<Map.Entry> comparingByKey(Comparator cmp) It returns a comparator that compare the objects by key using the given Comparator.
static <K,V extends Comparable> Comparator<Map.Entry> comparingByValue() It returns a comparator that compare the objects in natural order on value.
static Comparator<Map.Entry> comparingByValue(Comparator cmp) It returns a comparator that compare the objects by value using the given Comparator.

Map Example: Legacy Style without Generics

import java.util.*;
public class MapExample1 {
public static void main(String[] args) {
    Map map=new HashMap();
    //Adding elements to map
    map.put(1,"Anuj");
    map.put(5,"Raghav");
    map.put(2,"Jitendra");
    map.put(3,"Anuj");
    //Traversing Map Entry
	//Converting to Set so that we can traverse
    Set set=map.entrySet();
    Iterator itr=set.iterator();
    while(itr.hasNext()){
        //Type cast to Map.Entry so that we can get key and value separately
        Map.Entry entry=(Map.Entry)itr.next();
        System.out.println(entry.getKey()+" "+entry.getValue());
    }
}
}

Output :


1 Anuj
2 Jitendra
5 Raghav
3 Anuj

Map Example: With Generics

import java.util.*;
class MapExample2{
 public static void main(String args[]){
  Map map=new HashMap();
  map.put(20,"Anuj");
  map.put(21,"Virendra");
  map.put(22,"Raghav");
  //Elements can traverse in any order
  for(Map.Entry m:map.entrySet()){
   System.out.println(m.getKey()+" "+m.getValue());
  }
 }
}

Output :


22 Raghav
20 Anuj
21 Virendra

Map Example: comparingByKey() in ascending and descending order

import java.util.*;
class MapExample3{
 public static void main(String args[]){
Map map=new HashMap();
      map.put(20,"Anuj");
      map.put(21,"Virendra");
      map.put(22,"Raghav"); 

	  //ascending order
      //Returns a Set view of the mappings contained in this map
      map.entrySet()
      //Returns a sequential Stream with this collection as its source
      .stream()
      //Sorted according to the provided Comparator
      .sorted(Map.Entry.comparingByKey())
      //Performs an action for each element of this stream
      .forEach(System.out::println);  

	  //descending oder
	  //Returns a Set view of the mappings contained in this map
      map.entrySet()
      //Returns a sequential Stream with this collection as its source
      .stream()
      //Sorted according to the provided Comparator
      .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
      //Performs an action for each element of this stream
      .forEach(System.out::println);
 }
}

Output :


20=Anuj
21=Virendra
22=Raghav

Map Example: comparingByValue() in ascending and descending Order

import java.uti
class MapExample5{
 public static void main(String args[]){
Map map=new HashMap();
      map.put(20,"Anuj");
      map.put(21,"Virendra");
      map.put(22,"Raghav");  

	  //ascending order 

      //Returns a Set view of the mappings contained in this map
      map.entrySet()
      //Returns a sequential Stream with this collection as its source
      .stream()
      //Sorted according to the provided Comparator
      .sorted(Map.Entry.comparingByValue())
      //Performs an action for each element of this stream
      .forEach(System.out::println);  

	  //descending order

	  //Returns a Set view of the mappings contained in this map
     map.entrySet()
     //Returns a sequential Stream with this collection as its source
     .stream()
     //Sorted according to the provided Comparator
     .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
     //Performs an action for each element of this stream
     .forEach(System.out::println);
 }
}

Output :


20=Anuj
22=Raghav
21=Virendra

21=Virendra
22=Raghav
20=Anuj
Collection, Collections

Java: Hashmap Working

Leave a comment

What is Hashing?

Hashing is technique of converting an object into an integer value. For example hashcode() method always return int value. We can also override hashcode() method and implement own logic to get hashcode value.

Note : The integer value helps in indexing and faster searches.

What is HashMap

HashMap is a one type of collection in Java collection framework to store values in key and value pair. HashMap uses hashing technique for storing values. HashMap uses internal data structure as array and LinkedList for storing key and values. HashMap contains an array of nodes, and node presented by a class with respect to key.

See Also : Java: HashMap Class Methods and Examples

Contract between equals() and hashcode() method

Before discussing internal working of HashMap, need to understand hashCode() and equals() method contract in detail.

  • equals(): it’s Object class method to check the equality of two objects by comparing key, whether they are equal or not. It can be overridden.
  • hashCode(): it’s also object class methods which return memory reference of object in integer form. This value received from the hashcode() method is used as the bucket number or address of element inside Map. Hashcode value of null Key is 0.

If you override the equals() method, then it is mandatory to override the hashCod() method.

See Also: Java : java.lang.Object Class & Methods

Buckets: is an Array of the node, where each node has a data structure like a LinkedList. More than one node can use same bucket and may be different in capacity.

Working of HashMap

Insert Key, Value pair in HashMap

We use put() method to insert the Key and Value pair in the HashMap. The default capacity of HashMap is 16 (0 to 15).

Example: In the following example, we want to insert six (Key, Value) pair in the HashMap.

HashMap map = new HashMap();
map.put("Ankur", 35);
map.put("Saurabh", 36);
map.put("Gaurav", 32);
map.put("Raghav", 29);
map.put("Rajendra", 40);
map.put("Shailesh", 33);

When we call the put() method, then it calculates the hash code of the Key i.e “Ankur” hashcode is 63412443. Now to store the Key and value pair in memory, we have to calculate the index based on below formulae.

HashMap Representataion.jpg

Calculating Index Formulae:


Index = hashcode(Key) & (n-1)  
Where n is the size of the array.

Hence the index value for Ankur and others are as below:
Calculate Index for “Ankur”
Index = 63412443& (16-1) = 11
Calculate Index for “Saurabh”
Index = -758033668& (16-1) = 12
Calculate Index for “Gaurav”
Index = 2125849484& (16-1) = 12
Calculate Index for “Raghav”
Index = -1854623835& (16-1) = 5
Calculate Index for “Rajendra”
Index = 201412911& (16-1) = 15
Calculate Index for “Shailesh”
Index = -687212437& (16-1) = 11

The key “Ankur” calculated index value is 11. This key and value pair store in one of the node of HashMap.

Hash Collision

Hash Collisions occured when two or more keys are calculating index as same value.

From above calculated index value, keys “Ankur and “Shailesh” both index value is 11 having hash collision. Similarly for “Saurabh” and “Gaurav” having index value 12. In this case, equals() method compare both Keys are equal or not. If Keys are equal, replace the value with the current value. Otherwise, linked this node object (key and value pair) to the existing node object through the LinkedList.

Similarly, we will store the other keys with respect to below index positions.

HashMap get() method to retrieve values

HashMap get(Key) method is used to retrieve value by Key. This method calculate index position based on key hashcode value and capacity of hashmap and fetch result. If no matching key find out will return result as value null.

Suppose we have to fetch the Key “Ankur.” The following method will be called.


map.get(new Key("Ankur"));

It generates the hash code as 63412443. Now calculate the index value of 63412443 by using index formula. The index value will be 11. get() method search for the index value 11. It compares the given key value sequentially in bucket with respect to index position 11. If any equal key find out in bucket will return value object with respect to that key otherwise finally return null if not no match find out.

Let’s fetch another Key “Raghav.” The hash code of the Key “Raghav” is -1854623835. The calculated index value of -1854623835 is 5. Go to index 5 of the array and compare the first element’s Key with the given Key “Raghav”. It return the value object for match key.