Tag Archives: Hashing

Java: LinkedHashMap Class Methods and Examples


LinkedHashMap class extends the HashMap class and implements Map Interface to store values in key and value pairs.

Points to Remember

  • LinkedHashMap class is in java.util package.
  • LinkedHashMap uses data structure Hashtable and LinkedList implementation of the Map interface.
  • LinkedHashMap contains values based on the key.
  • LinkedHashMap contains unique elements.
  • LinkedHashMap class may have one null key and multiple null values.
  • LinkedHashMap is not synchronized.
  • LinkedHashMap maintains the insertion order.
  • LinkedHashMap initial default capacity is 16 with a load factor of 0.75.

LinkedHashMap Declaration


public class LinkedHashMap extends HashMap implements Map  
  • K: Here K represent Key of Map
  • V: Here V represents value in the Map with respect to K.

Constructors of LinkedHashMap class

Constructor Description
LinkedHashMap() This is the default LinkedHashMap constructor.
LinkedHashMap(int capacity)  Use to initialize a LinkedHashMap with the given capacity.
LinkedHashMap(int capacity, float loadFactor) Use to initialize both the capacity and the load factor.
LinkedHashMap(int capacity, float loadFactor, boolean accessOrder) Use to initialize both the capacity and the load factor with specified ordering mode.
LinkedHashMap(Map m) Use to initialize the LinkedHashMap with the elements from the given Map class m.

Methods of LinkedHashMap class

Method Description
V get(Object key) It returns the value object map to the specified key.
void clear() It removes all the key-value pairs from a map.
boolean containsValue(Object value) It returns true if one or more keys to the specified value.
Set<Map.Entry> entrySet() It returns a Set view of the mappings contained in the map.
void forEach(BiConsumer action) It performs the given action on each entry in the map until all entries have been processed or any action throws an exception.
V getOrDefault(Object key, V defaultValue) It returns the value to which the specified key is mapped or defaultValue if this map contains no mapping for the key.
Set keySet() It returns a Set view of the keys contained in the map
protected boolean removeEldestEntry(Map.Entry eldest) It returns true on removing its eldest entry.
void replaceAll(BiFunction function) It replaces each entry’s value in map with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
Collection values() It returns a Collection view of the values contained in this map.

LinkedHashMap Example : insert items and traverse

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample4 {

	public static void main(String args[]) {

		Map hm = new LinkedHashMap();

		hm.put(20, "Anuj");
		hm.put(21, "Virendra");
		hm.put(22, "Raghav");

		for (Map.Entry m : hm.entrySet()) {
			System.out.println(m.getKey() + " " + m.getValue());
		}
	}

}

Output :


20 Anuj
21 Virendra
22 Raghav

LinkedHashMap Example : Key-Value pair

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample1 {

	public static void main(String args[]) {
		Map map = new LinkedHashMap();
		map.put(20, "Anuj");
		map.put(21, "Virendra");
		map.put(22, "Raghav");
		// Fetching key from LinkedHashMap
		System.out.println("Keys: " + map.keySet());
		// Fetching value from LinkedHashMap
		System.out.println("Values: " + map.values());
		// Fetching key-value pair from LinkedHashMap
		System.out.println("Key-Value pairs: " + map.entrySet());
	}

}

Output :


Keys: [20, 21, 22]
Values: [Anuj, Virendra, Raghav]
Key-Value pairs: [20=Anuj, 21=Virendra, 22=Raghav]

LinkedHashMap Example : remove()

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample2 {

	public static void main(String args[]) {
		Map map = new LinkedHashMap();
		map.put(20, "Anuj");
		map.put(22, "Ravi");
		map.put(21, "Virendra");
		map.put(23, "Raghav");
		System.out.println("Before remove: " + map);
		// Remove value for key 22
		map.remove(22);
		System.out.println("After remove: " + map);
	}

}

Output :


Before remove: {20=Anuj, 22=Ravi, 21=Virendra, 23=Raghav}
After remove: {20=Anuj, 21=Virendra, 23=Raghav}

LinkedHashMap Example : getOrDefault()

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample3 {

	public static void main(String args[]) {
		Map map = new LinkedHashMap();
		map.put(20, "Anuj");
		map.put(22, "Ravi");
		map.put(21, "Virendra");
		map.put(23, "Raghav");
		// Here it will retrieve values for key 21 and 25
		// if values not find out in HashTable then return default value
		System.out.println(map.getOrDefault(21, "Not Found"));
		System.out.println(map.getOrDefault(25, "Not Found"));
	}
}

Output :


Virendra
Not Found

LinkedHashMap Example : with objects

import java.util.*;
class Magzine{
int id;
String name,author,publisher;
int quantity;
public Magzine(int id, String name, String author, String publisher, int quantity) {
    this.id = id;
    this.name = name;
    this.author = author;
    this.publisher = publisher;
    this.quantity = quantity;
}
}
public class LinkedHashMapExampleWithObjects {
	public static void main(String[] args) {
		// Creating map of Magzine
		Map map = new LinkedHashMap();
		// Creating Magzines
		Magzine m1 = new Magzine(21, "The Sun", "Sy Sunfranchy", "The Sun Company", 8);
		Magzine m2 = new Magzine(22, "Glimmer Trains", "Unknown", "Glimmer Train Press", 4);
		Magzine m3 = new Magzine(23, "Crazy horse", "Brett Lot", "College of Charleston", 6);

		// Adding magzine to map
		map.put(1, m1);
		map.put(2, m2);
		map.put(3, m3);
		// Traversing map
		for (Map.Entry entry : map.entrySet()) {
			int key = entry.getKey();
			Magzine m = entry.getValue();
			System.out.println("\nId: "+key + " Details:");
			System.out.println(m.id + " " + m.name + " " + m.author + " " + m.publisher + " " + m.quantity);
		}
	}
}

Output :


Id: 1 Details:
21 The Sun Sy Sunfranchy The Sun Company 8

Id: 2 Details:
22 Glimmer Trains Unknown Glimmer Train Press 4

Id: 3 Details:
23 Crazy horse Brett Lot College of Charleston 6

Java: Hashmap Working


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.