Map Interface in Java | HashMap Implementation in Java

Map interface in Java is not related to Collections and hence we are taking this as a separate topic. Although we are going to see it in a similar style just as we saw Java Collections Framework in the past.

So you might be wondering about the cardinal question:

What is a Map?

Generally speaking what is a map to you? Isn’t it something that helps you locate a place or an address?

In a similar context, Map is an object in Java that helps you to locate values, and it does so with the help of keys.

A map can’t have duplicate keys. Every key must map only one value. If you have a pair of key and values, you can store the value in a map object and later retrieve it using the key.

Key and value together constitute an entry.

Maps come in handy when you are trying to search, update and delete elements in a large database.

Since Maps are not a part of Collection, be prepared to experience some weirdness.

Here’s a hierarchical diagram representing where things actually stand:

We have got Hashtable, AbstractMap, HashMap and LinkedHashMap all implementing Map Interface.

Let’s check out the methods of map interface in Java.

Methods of Map Interface in Java

The following methods of map interface come in handy when you are dealing with maps:

1. clear()
2. containsKey(Object key)
3. containsValue(Object value)
4. entrySet()
5. equals(Object o)
6. get(Object key)
7. hashCode()
8. isEmpty()
9. keySet()
10. put(K key, V value)
11. putAll(Map m)
12. remove(Object key)
13. size()
14. values()

Entry Sub-Interface

There is a sub interface or a nested interface of Map interface in Java known as Entry.

As you might recall from the chapter of nested classes, referring to Entry would require the placement of a ‘.’ dot operator in between. So, Map.Entry<K, V> will be denoting your map entry meaning a key-value pair.

It returns a collection-view of the map.

There are some methods here as well that you could use:

1. equals(Object o)
2. getKey()
3. getValue()
4. hashCode()
5. setValue(V value)

Since we can’t instantiate an interface we are going to need a class here. So our Map interface in Java needs a class badly.

Let’s see our first class after which we will see some examples.

Hashtable Class

As seen earlier while learning about HashSet, a Hash table is nothing but a data structure that uses keys and values to store its elements. Hashtable class implements such a hash table.

In order to store and get values from a hashtable, hashCode() and equals() methods must be implemented by the objects used as keys.

Hashtable inherits the legacy Dictionary class and implements Map interface in Java. It is also synchronized.

Here are the constructors of Hashtable that you could use during instantiation:

• Hashtable()
• Hashtable(int initialCapacity)
• Hashtable(int initialCapacity, float LoadFactor)
• Hashtable(Map t)

Methods that fall here are:

1. clear()
2. clone()
3. contains(Object value)
4. containsKey(Object key)
5. containsValue(Object value)
6. elements()
7. entrySet()
8. equals(Object o)
9. get(Object key)
10. hashCode()
11. isEmpty()
12. keys()
13. keySet()
14. put(K key, V value)
15. putAll(Map t)
16. rehash()
17. remove(Object key)
18. size()
19. toString()
20. values()

We will quickly see an example of how to add entries or key-values and display them using entrySet().

Example of HashTable

I am creating an <Integer, String> Hashtable to see how to display set view of the mappings.

Hashtable <Integer, String>m = new Hashtable<Integer, String>(); 
m.put(1, "Bon Jovi"); 
m.put(2, "Maroon 5"); 
m.put(2, "Maroon 5"); 
m.put(4, "Coldplay");

for(Map.Entry<Integer, String>i: m.entrySet()) {
 System.out.println(i.getKey() + " " + i.getValue()); 
}

As you can see we are making use of the readily available put() method of the Map interface in Java to punch in keys and their respective values.

Observe the usage of Map.Entry to specify the Set type while defining a variable named ‘i’ in for each loop. m.entrySet() is going to give us a set and so it should be read like “for each ‘i’ in m.entrySet() get the key and value.”

If you run the above program you will get:

4 Coldplay
2 Maroon 5
1 Bon Jovi

Duplicate Logic

As you can see, trying to put the same value and same key was ignored since duplicates are not allowed here. However, if you change the key then the value can be identified as a separate entry.

m.put(2, "Maroon 5"); 
m.put(3, "Maroon 5");

The result would become:

4 Coldplay
3 Maroon 5
2 Maroon 5
1 Bon Jovi

If you use the same key but different values, it will overwrite it with the last entry.

m.put(2, "Maroon 5"); 
m.put(2, "Green Day");

Hence the result would become:

4 Coldplay
2 Green Day
1 Bon Jovi

keySet() method

You can alternatively use keySet() method to get a Set view of keys. Here’s how to do that:

Set k = m.keySet(); 
System.out.println(k);

If you run it you will get:

[4, 2, 1]

remove() Method

Let’s remove an entry by using the remove() method. Augment the following code in your existing code:

m.remove(4);

Now run the program; poor Coldplay will disappear.

2 Green Day
1 Bon Jovi

Elements() and keys() methods returning Enumeration

There is a method called elements() that provides you an Enumeration as the return type. Enumeration has all sorts of its own bunch of methods that you could use.

Here’s an example to depict the usage of elements():

Enumeration e = m.elements(); 
while(e.hasMoreElements()){ 
System.out.println(e.nextElement());
}

When you run the above you will get:

Green Day
Bon Jovi

Now that we have removed Coldplay.

Now what if you wished to grab the keys instead of values?

Simply use the keys() method that returns Enumeration.

Replace elements() with keys() in the above:

Enumeration e = m.keys(); 
while(e.hasMoreElements()){ 
System.out.println(e.nextElement());
}

and you will get:

2
1

values() method

Similarly, if you just want the values without using extra methods, values() method comes in handy.

Here’s how to use it:

Collection k = m.values();
System.out.println(k);

If you run the above program you will get:

[Green Day, Bon Jovi]

Rest of the methods are easy to understand, right? Let’s move on.

HashMap Class

A HashMap class is nothing but a hash table type of implementation for the Map interface in Java. It allows multiple null values and can have one null key. Duplicates are not entertained. So even if there are duplicates it will not be included in the result. There is no order to be maintained here.

It is unsynchronized and can be synchronized either by wrapping synchronized over the object as we had seen in Synchronization chapter. or there’s a better alternative provided in the form of:

Map m = Collections.synchronizedMap(hashMap);

Here are the constructors you should be watching out for:

• HashMap()
• HashMap(int initialCapacity)
• HashMap(int initialCapacity, float loadFactor)
• HashMap(Map m)

The following methods of HashMap come in handy when you are working with HashMap class in Java:

1. clear()
2. clone()
3. containsKey(Object key)
4. containsValue(Object value)
5. entrySet()
6. get(Object key)
7. isEmpty()
8. keySet()
9. put(K key, V value)
10. putAll(Map m)
11. remove(Object key)
12. size()
13. values()

I think we have seen all of the methods in Hashtable part so none needs to be shown here.

Of course whilst instantiating you just replace Hashtable with HashMap.

HashMap<Integer, String> m = new Hashmap<Integer, String>();

or if you are planning on using only Map Interface in Java methods:

Map<Integer, String>  m = new Hashmap<Integer, String>();

LinkedHashMap Class

When you wish to take the benefits of both a hash table and a linked list, you opt for the LinkedHashMap class. The iteration here is predictable so you kind of know already what the next element is going to be. LinkedHashMap isn’t synchronized.

LinkedHashMap class implements Map interface in Java too.

Here are the constructors that you could use to create a LinkedHashMap class:

• LinkedHashMap()
• LinkedHashMap(int capacity)
• LinkedHashMap(int capacity, float loadFactor)
• LinkedHashMap(int capacity, float loadFactor, boolean accessOrder)
• LinkedHashMap(Map m)

Some of the methods of LinkedHashMap are:

1. clear()
2. containsValue(Object value)
3. entrySet()
4. get(Object key)
5. keySet()
6. removeEldestEntry(Map.Entry<K, V> eldest)
7. values()

Of course, here in order to create an instance you need to type a constructor with new:

LinkedHashMap lhm = new LinkedHashMap();

or with generics:

LinkedHashMap<Integer, String> lhm = new LinkedHashMap<Integer, String>();

TreeMap class

As explained in the Map hierarchical diagram TreeMap extends AbstractMap and implements NavigableMap which goes on to extend SortedMap and Map interface. Since it implements NavigableMap it inherits all its methods designed for locating entries.

As its name might imply, it makes use of a tree for storing key-value pairs in sorted order(owing to SortedMap).

It contains no duplicates and cannot have a null key and but multiple null values. It is almost same as HashMap, but with ascending order.

It is not synchronized and can be synchronized using:

SortedMap m = Collections.synchronizedSortedMap(treeMap);

Here are the constructors to look out for:

• TreeMap()
• TreeMap(Comparator comp)
• TreeMap(Map m)
• TreeMap(SortedMap m)

You can check out the methods that it incorporates:

1. ceilingEntry(K key)
2. ceilingKey(K key)
3. clear()
4. clone()
5. comparator()
6. containsKey(Object key)
7. containsValue(Object value)
8. descendingKeySet()
9. descendingMap()
10. entrySet()
11. firstEntry()
12. firstKey()
13. floorEntry(K key)
14. floorKey(K key)
15. get(Object key)
16. headMap(K toKey)
17. headMap(K toKey, boolean inclusive)
18. higherEntry(K key)
19. higherKey(K key)
20. keySet()
21. lastEntry()
22. lastKey()
23. lowerEntry(K key)
24. lowerKey(K key)
25. navigableKeySet()
26. pollFirstEntry()
27. pollLastEntry()
28. put(K key, V value)
29. putAll(Map m)
30. remove(Object key)
31. size()
32. subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
33. subMap(K fromKey, k toKey)
34. tailMap(K fromKey)
35. tailMap(K fromKey, boolean inclusive)
36. values()

We will see some examples to understand some of these methods:

ceilingEntry(), ceilingKey(), floorEntry(), floorKey() Methods

ceilingEntry() and ceilingKey() give you the least key value greater than or equal to the given key and least key greater than or equal to the given key respectively.

TreeMap <Integer, Integer>m = new TreeMap<Integer, Integer>(); 
m.put(1, 4); 
m.put(2, 7); 
m.put(7, 6); 
m.put(4, 2); 
m.put(5, 10); 
System.out.println(m.ceilingEntry(3)); 
System.out.println(m.ceilingKey(3));

Here I am trying to enter a key as 3. What are the keys greater than 3? They are 4, 5 and 7 right? What’s the least no. from them? 4. So the result we will get:

4=2
4

Now let’s try that for floorEntry() and floorKey() methods. They will return the greatest key-value pair less than or equal to the given key and the greatest key less than or equal to the given key.

System.out.println(m.floorEntry(3)); 
System.out.println(m.floorKey(3));

Now, what are the keys less than or equal to 3? 1 and 2 of course. Out of that the greatest is 2. So the result will be:

2=7
2

higherEntry(), higherKey(), lowerEntry() and lowerKey() methods

A similar group of methods are higherEntry() and higherKey() with least key value or key greater than the given key.

The opposite of that is lowerEntry() and lowerKey() methods that give the greatest key value or key less than the given key.

Here an example would help:

System.out.println(m.higherEntry(4)); 
System.out.println(m.higherKey(4)); 
System.out.println(m.lowerEntry(4));
System.out.println(m.lowerKey(4));

Run it and you will get:

5=10
5
2=7
2

navigableKeySet(), descendingKeySet() and descendingMap() methods

If you want a navigableSet view of the keys and the reverse order of the same you can use navigableKeySet() and descendingKeySet() anytime. You want the values as well, you can make use of descendingMap() method.

System.out.println(m.navigableKeySet()); 
System.out.println(m.descendingKeySet()); 
System.out.println(m.descendingMap());

You run the above and you will get:

[1, 2, 4, 5, 7]
[7, 5, 4, 2, 1]
{7=6, 5=10, 4=2, 2=7, 1=4}

firstEntry(), firstKey(), lastEntry() and lastKey() methods

These are not so hard to get. A simple example will make it clear. I am using it on the above example:

System.out.println(m.firstEntry()); 
System.out.println(m.firstKey()); 
System.out.println(m.lastEntry()); 
System.out.println(m.lastKey());

The result would be:

1=4
1
7=6
7

headMap(), tailMap() and subMap() methods

If you wish to extract a portion of the map to have a proper and look and feel of things you could do so using headMap() and tailMap(). All you have to provide is a key. The second parameter is for if you want your key to be inclusive.

System.out.println(m.headMap(7)); 
System.out.println(m.headMap(7,true)); 
System.out.println(m.tailMap(4)); 
System.out.println(m.tailMap(4,true));

The result you will get here is:

{1=4, 2=7, 4=2, 5=10}
{1=4, 2=7, 4=2, 5=10, 7=6}
{4=2, 5=10, 7=6}
{4=2, 5=10, 7=6}

Notice the last one two are same, because by default tailMap() method includes “equal to key” results.

Similarly, if you wish a specific portion of your map to be displayed you can use subMap() method.

Here, an example would make it clear:

System.out.println(m.subMap(2, 7)); 
System.out.println(m.subMap(2,false, 7, false));

The second variant is when you wish some keys to remain or inclusive or exclusive.

You will get:

{2=7, 4=2, 5=10}
{4=2, 5=10}

That concludes our chapter for HashMap. Things in a nutshell:

• All classes herein are non-synchronized except the legacy Hashtable class.
• No duplicates are entertained.
• HashMap allows at most one null key and countless null values.
• TreeMap cannot have a null key but countless null values.

I think I need to rest a little. Where’s my key to rest?