Pages

▼

Map Interface and its implementations. Java HashMap, LinkedHashMap and TreeMap Examples

What is Java Map Interface

The Java Map interface is a part of Java Collection framework, but it is not a subtype of the Collection interface. So it behaves in a different way compared to, say, Lists, or other collection Objects. Each element of Map<Key, Value> represents a key-value pair. Both Key and value are some objects. All keys in a particular map are unique, while values are not, so they can be duplicated. You may think of Map in Java such as a kind of dictionary or online-shop catalog, where you can find any item using its unique index. The key is a unique identifier of the value in a Map. For example in Map<String, Item> String is an ID of some Item from the online shop. According to documentations Map has the next Subinterfaces:
    Bindings;
  • ConcurrentMap<K,V>;
  • ConcurrentNavigableMap<K,V>;
  • LogicalMessageContext;
  • MessageContext;
  • NavigableMap<K,V>;
  • SOAPMessageContext;
  • SortedMap<K,V>.
And Implements Classes:
  • AbstractMap
  • Attributes
  • AuthProvider
  • ConcurrentHashMap
  • ConcurrentSkipListMap
  • EnumMap
  • HashMap
  • Hashtable
  • IdentityHashMap
  • LinkedHashMap
  • PrinterStateReasons
  • Properties
  • Provider
  • RenderingHints
  • SimpleBindings
  • TabularDataSupport
  • TreeMap
  • UIDefaults
  • WeakHashMap
  • Java AbstractMap is an abstract class that implements most of the Map interface.
  • Java HashMap is a data structure for storing key-value pairs using a hash table.
  • Java TreeMap is a data structure to use a tree, i.e. display with sorted keys.
  • WeakHashMap to use a hash table with weak keys, display with values ​​that can be deleted by the garbage collector if they are no longer used.
  • LinkedHashMap is a map with the order of adding elements, allows iteration in the insertion order.
  • EnumMap extends the AbstractMap class for use with enum keys.
    • IdentityHashMap uses referential equivalence checking when comparing documents, mapping with keys compared using == operation instead of equals() method
Here we are interested in the most popular implementations of Map Interface: HashMap, TreeMap and LinkedHashMap. By the way, the order of map elements depends on specific implementations. Say, TreeMap and LinkedHashMap have predictable order of the elements, while HashMap doesn’t.

Map methods

The main operations of any Map are insertion, remove, and search of elements.
  • public Object put(Object key, Object value) inserts an element into the map.
  • public void putAll(Map map) inserts the specified map inside the map.
  • public Object remove(Object key) deletes an entry according to the specified key.
  • public Object get(Object key) returns the value for the specified key.
  • public boolean containsKey(Object key) searches the specified key from this map
  • public Set keySet() returns a Set view that contains all the keys
  • public Set entrySet() returns a Set view with all the keys and values.

What is HashMap

What is HashMap? It is the most popular implementation of Map<Key,Value> interface. This data structure is based on the hashing principle.

The main principle of HashMap work: hashing

To understand what is a hashmap and how it works, let’s talk about hashing and hash functions first. A hash function is just a function in a mathematical sense. So there is some input value (an object, a piece of data) and function converts it using a proper rule into output value - a hash. Pretty often hash is a hexadecimal number of a proper length. Rules of converting processes could be different, but they are subject to the following principles:
  1. A particular input (object) has a particular hash code.
  2. If two objects are equal, their hash codes are equal as well. The reverse is not true.
  3. If the hash codes are different, the objects are definitely not equal.
  4. Sometimes different objects can have the same hash code. It is a very unlikely event, named “collision” and a good quality hash function should minimize the probability of collisions.
In Java, every object has a hash code. It is calculated by the hashCode method of the Object class, parental class of all Java Objects. Usually, developers override this method for their own classes as well as equals methods associated with it.

HashMap: how it works

So Class HashMap<K,V> as every Map implementation consists of keys and values. It stores keys using hashing principles. Inside the HashMap Key-value pairs are stored in "buckets", these buckets together construct a "table", an internal array of linked lists and its initial size is 16. HashMap in Java uses the key’s hashcode to determine a bucket where the key/value pair should map: The tricky feature of HashMap is that each cell (bucket) of the table [] keeps not only one pair but several. They are not stored as an explicit object (like LinkedList), but as an implicit chain. The chain is created due to the fact that each pair stores a link to the next pair. That is, all HashMap pairs are scattered across 16 chains. When you put a new pair into the table, the hash of the key is considered. This hash is not a hashcode function built into the key object. It is considered to be in the range of 0-15. The pair is added to the chain of pairs stored in the bucket with the hash index. This approach gives us search acceleration. While searching for a pair by key, there is no need to go through the entire table. The hash of the key is considered and only the chain that is stored in the cell with the hash index is checked. If there are too many pairs in the HashMap, the chains become too long. Then the size of the array increases, the hash of all stored objects is recalculated, and they are scattered along new chains.

HashMap Declaration

If you go to the class HashMap code you will find the next declaration: 
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
Where K is the type of keys maintained by this map and V - the type of mapped values. This is an example of HashMap declaration with Integer key and String value in your code: 
HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();

HashMap methods

Here is the list of HashMap methods.
  • Object get(Object key) returns the value for the specified key;
  • Object put(Key k, Value v) inserts key value mapping into the map;
  • Object remove(Object key) removes the mapping for the specified key from this map if present;
  • void clear() removes all the key-value pairs from the HashMap;
  • Object clone() returns a shallow copy of this HashMap instance without cloning the keys and values;
  • boolean containsKey(Object key) returns true if the specified key is found in the map, false if isn’t;
  • boolean containsValue(Object Value) returns true if the specified key is found in the map, false if isn’t;
  • boolean isEmpty() returns true if the map is empty, false if isn’t;
  • Set keySet() returns the Set of the keys fetched from the map;
  • int size() returns the quantity of key-value mapping;
  • Collection values() returns a collection of the map’s values;
  • Object remove(Object key) removes the key-value pair for the specified key;
  • void putAll(Map m) copies all elements of the map to the other map.

Java HashMap Example

Let’s create a program with Java HashMap Example to demonstrate how it works: 
import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;
import java.util.Set;

public class HashMap {

   public static void main(String[] args) {

       {

           // HashMap declaration
           HashMap<Integer, String> myHashMap = new HashMap<Integer, String>();

           //Adding elements into HashMap
           myHashMap.put(7, "Johnny");
           myHashMap.put(8, "Ivy");
           myHashMap.put(1, "Rick");
           myHashMap.put(4, "Stan");
           myHashMap.put(3, "Kyle");

           //print out the map content using Iterator
           Set set = myHashMap.entrySet();
           Iterator iterator = set.iterator();
           while (iterator.hasNext()) {
               Map.Entry mapEntry = (Map.Entry) iterator.next();
               System.out.print("key: " + mapEntry.getKey() + " value: ");
               System.out.println(mapEntry.getValue());
           }
           System.out.println("get an element from myHashMap via key and print the value out:");
           System.out.println(myHashMap.get(8));
           //print out hashMap on standard way:
           System.out.println(myHashMap);

           // Get values based on key
           String var = myHashMap.get(2);
           //here we'll get null, we don't have such a key
           System.out.println("Value with key 2: " + var);
           var = myHashMap.get(7);
           System.out.println("Value with key 7: " + var);

           // Remove values based on key
           myHashMap.remove(4);
           System.out.println("myHashMap after removing element:");
           System.out.println(myHashMap);
           myHashMap.clear();
           System.out.println("myHashMap after total clearing:");
           System.out.println(myHashMap);
       }

   }
}
The result of running the program: 
key: 1 value: Rick
key: 3 value: Kyle
key: 4 value: Stan
key: 7 value: Johnny
key: 8 value: Ivy
get an element from myHashMap via key and print the value out:
Ivy
{1=Rick, 3=Kyle, 4=Stan, 7=Johnny, 8=Ivy}
Value with key 2: null
Value with key 7: Johnny
myHashMap after removing element:
{1=Rick, 3=Kyle, 7=Johnny, 8=Ivy}
myHashMap after total clearing:
{}

TreeMap

TreeMap in Java also implements Map<Key,Value> interface, but it is based on Red-Black tree data structure. A Tree consists of "nodes" and lines that connect nodes - branches". The "root" node is at the top of the tree. From the root, there can be branches and nodes. It is a hierarchical structure, you may think of these nodes as "children" of the root. Child node can have its own children - lower nodes. Nodes without children are called "end-nodes" or "leaves". A binary tree is a tree, where every node has zero, one, or two children. The binary search tree is a structure, where every internal node stores a key, and sometimes an associated value, and has two distinguished sub-trees ("left" and "right"). A self-balancing binary search tree is a node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. A red-black tree is a balanced binary tree with the properties:
  • Every node is either red or black
  • The root is always black
  • Every leaf is a NIL (kind of empty, null) node and it is black
  • If a node is red, its children are definitely black.
  • Every simple path from a node to a descendant leaf contains the same number of black nodes.

A TreeMap features

A TreeMap uses a tree data structure to store the keys as the nodes and sorts the keys using the Red-Black Tree algorithm. So, TreeMap keeps its entries sorted according to the natural ordering of its keys. For numbers natural is ascending order, for strings — alphabetical order. You can use a comparator if you need to change the logic of ordering. Sorting objects in a natural way is a big advantage of TreeMap, as well as finding some objects using different filters and conditions.

TreeMap methods

  • Object get(Object key) returns the value of the corresponding key;
  • Object put(Object key, Object value) inserts a mapping into a map;
  • Object remove(Object key) removes the mapping for this key from if the TreeMap contains it;
  • boolean containsKey(Object key) returns true if this map contains a mapping for the specified key;
  • boolean containsValue(Object value) returns true if the TreeMap maps one or more keys to the specified value;
  • Object firstKey() returns the first key currently in the sorted map;
  • Object lastKey() returns the last key currently in the sorted map;
  • void putAll(Map map) copies all mappings from the specified map to the map;
  • Set entrySet() returns a set view of the mappings
  • int size() returns the quantity of key-value mappings
  • Collection values() returns a collection view of the values
  • Object clone() returns a shallow copy of the TreeMap
  • void clear() removes all mappings from the TreeMap
  • SortedMap headMap(Object key_value) returns a view of the portion of the map less than the parameter key_value
  • Set keySet() returns a Set view of the keys contained in the treemap
  • SortedMap subMap(K fromKey, K toKey) returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive
  • Object firstKey() returns the first key from the TreeMap.

TreeMap example

import java.util.TreeMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;

public class TreeMapExample {

   public static void main(String args[]) {

       //TreeMap declaration
       TreeMap<Integer, String> myTreeMap = new TreeMap<Integer, String>();

       //put elements to TreeMap
       myTreeMap.put(1, "Stuart");
       myTreeMap.put(23, "Michael");
       myTreeMap.put(7, "Johnny");
       myTreeMap.put(5, "Ivy");
       myTreeMap.put(2, "Alex");

       //Display and print out myTreeMap using Iterator
       Set set = myTreeMap.entrySet();
       Iterator iterator = set.iterator();
       while (iterator.hasNext()) {
           Map.Entry myEntry = (Map.Entry) iterator.next();
           System.out.print("key: " + myEntry.getKey() + " value: ");
           System.out.println(myEntry.getValue());
       }
       //TreeMap printed in classical way
       System.out.println(myTreeMap);
       //removing an element with the key =2
       myTreeMap.remove(2);
       //myTreeMap after removing:
       System.out.println(myTreeMap);
   }
}
The result of running the program: 
key: 1 value: Stuart
key: 2 value: Alex
key: 5 value: Ivy
key: 7 value: Johnny
key: 23 value: Michael
{1=Stuart, 2=Alex, 5=Ivy, 7=Johnny, 23=Michael}
{1=Stuart, 5=Ivy, 7=Johnny, 23=Michael}

LinkedHashMap

LinkedHashMap is a data structure that combines linked lists and hash maps. Indeed, LinkedHashMap extends the HashMap class and implements the Map interface, but what is it about linked lists? The declaration of LinkedHashMap: 
Map <Integer, String> linkedHashMap = new LinkedHashMap <Integer, String>();
This new linkedHashMap inherits properties from HashMap (such as table, loadFactor, threshold, size, entrySet), also gets two special properties:
  • header is the head of a doubly linked list. During the initialization, it indicates itself
  • accessOrder indicates how to get access to elements using iterator. If true, in the order of the last access. If false, access will be in the order the elements were inserted.
This linked list defines the iteration ordering. Usually, it is the order of keys insertion into the map.

LinkedHashMap Methods

  • Object get(Object key) returns the value to which the specified key is mapped, or null if this map contains no mapping for the key
  • void clear() removes all the mappings from the map.
  • boolean containsKey(Object key) returns true if the specified element is mapped by one or more keys
  • boolean removeEldestEntry(Map.Entry eldest) returns true if the map removes its eldest entry from the map
  • Set<Map.Entry7lt;K,V>> entrySet() returns a Set view of the mappings contained in this map
  • void forEach(BiConsumer<? super K,? super V> action) performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
  • Object getOrDefault(Object key, V defaultValue) returns the value to which the specified key is mapped. If the map doesn’t contain a mapping for the key returns defaultValue.
  • Set<K> keySet() returns a Set view of the keys contained in the map
  • boolean removeEldestEntry(Map.Entry<K,V> eldest) returns true if this map should remove its eldest entry
  • void replaceAll(BiFunction<? super K,? super V,? extends V> function) replaces each entry value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
  • Collection<v>values() returns a Collection view of the values contained in the map

LinkedHashMap example

import java.util.LinkedHashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;
   public class HashLinkedListExample {
       public static void main(String args[]) {
           // LinkedHashMap Declaration
           LinkedHashMap<Integer, String> myLinkedHashMap =
                   new LinkedHashMap<Integer, String>();

           //Adding elements into LinkedHashMap
           myLinkedHashMap.put(7, "Johnny");
           myLinkedHashMap.put(12, "Rick");
           myLinkedHashMap.put(1, "Kyle");
           myLinkedHashMap.put(5, "Percy");
           myLinkedHashMap.put(85, "Sebastian");

           // Generate a Set of entries
           Set set = myLinkedHashMap.entrySet();

           // Display and print out the nodes  of LinkedHashMap
           Iterator iterator = set.iterator();
           while(iterator.hasNext()) {
               Map.Entry me = (Map.Entry)iterator.next();
               System.out.print("key: "+ me.getKey() +
                       " value: "+me.getValue()+"\n");
           }
           //print out HashLinkedMap on standard way:
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.put(21, "Ivy");
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.remove(12);
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.put(12, "Ronny");
           System.out.println(myLinkedHashMap);
           myLinkedHashMap.put(1, "Stan");
           System.out.println(myLinkedHashMap);
       }
   }
Here we create a new LinkedHashMap, adding five elements, then print it out using iterator and in a classical way. As you can see, LinkedHashMap maintains the insertion order. After it we delete an element from our Map, then add the new one and later - one more element with the key, that is already on the map. It replaces the old value mapped to this key. The result of running program: 
key: 7 value: Johnny
key: 12 value: Rick
key: 1 value: Kyle
key: 5 value: Percy
key: 85 value: Sebastian
{7=Johnny, 12=Rick, 1=Kyle, 5=Percy, 85=Sebastian}
{7=Johnny, 12=Rick, 1=Kyle, 5=Percy, 85=Sebastian, 21=Ivy}
{7=Johnny, 1=Kyle, 5=Percy, 85=Sebastian, 21=Ivy}
{7=Johnny, 1=Kyle, 5=Percy, 85=Sebastian, 21=Ivy, 12=Ronny}
{7=Johnny, 1=Stan, 5=Percy, 85=Sebastian, 21=Ivy, 12=Ronny}

HashMap, TreeMap, LinkedHashMap Comparison

HashMap, TreeMap, and LinkedHashMap are the implementations of Map interfaces. HashMap and LinkedHashMap are data structures that hashes keys. TreeMap uses the natural order of its keys to organizing a search tree. Order:
  • HashMap doesn’t maintain any order.
  • TreeMap sorts the entries in ascending order of keys.
  • LinkedHashMap maintains the insertion order.
Null keys:
  • HashMap and LinkedHashMap allows having one null key.
  • LinkedHashMap doesn’t allow null keys in case of the keys use natural ordering or Comparator doesn’t support comparison on null leys.
Let’s have a Java map example that includes all three implementations reviewed in this article: 
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.TreeMap;

public class CompMapImpl {


    public static void main(String[] args) {
        HashMap<Integer, String> hashMap = new HashMap<>();
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();
        hashMap.put(5, "Ivy");
        hashMap.put(null, "Joker");
        hashMap.put(1, "First");
        hashMap.put(2, "Kyle");
        hashMap.put(-2, "Paul");
        hashMap.put(3, "Sandy");


        treeMap.put(5, "Ivy");
        //treeMap.put(null,"Joker");
        treeMap.put(1, "First");
        treeMap.put(2, "Kyle");
        treeMap.put(-2, "Paul");
        treeMap.put(3, "Sandy");

        linkedHashMap.put(5, "Ivy");
        linkedHashMap.put(null, "Joker");
        linkedHashMap.put(1, "First");
        linkedHashMap.put(2, "Kyle");
        linkedHashMap.put(-2, "Paul");
        linkedHashMap.put(3, "Sandy");
        System.out.println("HashMap");
        System.out.println(hashMap);
        System.out.println("TreeMap");
        System.out.println(treeMap);
        System.out.println("LinkedHashMap");
        System.out.println(linkedHashMap);


        LinkedHashMap<String, String> linkedHashMap1= new LinkedHashMap<> ();
        linkedHashMap1.put(null, "Andy");
        System.out.println(linkedHashMap1);
    }
}
Here is the result of running this program: 
HashMap
{null=Joker, 1=First, -2=Paul, 2=Kyle, 3=Sandy, 5=Ivy}
TreeMap
{-2=Paul, 1=First, 2=Kyle, 3=Sandy, 5=Ivy}
LinkedHashMap
{5=Ivy, null=Joker, 1=First, 2=Kyle, -2=Paul, 3=Sandy}
{null=Andy}
As we can see, the order of elements in HashMap is not obvious, in treeMap it depends on keys, in LinkedHashMap it is about insertion order. If we try to put null key into linkedHashMap, we’ll get NullPointerException, but in linkedHashMap1, where keys are String, we can do it. A hash map is the best general-purpose map implementation. It provides maximum search speed, fast storage, and retrieval operations, but you should remember about its chaotic ordering. A linked hash map inherits HashMap advantages and gets an order for the keys. However, it contains linkedList, which is relatively costly in terms of memory. it is slower than HashMap in searching and a little bit slower for add/remove because of maintaining linked list. A tree map stores keys sorted in ascending order. However, it offers worse general performance than HashMap and LinkedHashMap.
at

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.