Map is an interface in java. Present in java.util package. The map is the collection of keys and values and it stores the data as a Key-Value pair. It is implemented by HashMap, TreeMap, and LinkedHashMap. Each class has its own features. It doesn’t keep the order of keys.
What is TreeMap in java?
TreeMap is used to implement the Map interface in java. It is also stored as a Kay-Value pair but this gives an extra feature that is sorting. It keeps all keys in a sorted manner. It takes O(log n) time to insert a key in the TreeMap.
What is MultiMap?
MultiMap is used to keep multiple same keys with different values. Unfortunately, java does not provide this functionality. In this article, we will learn How we can implement it in java. The C++ language supports it.
MultiMap can be implemented in java using TreeMap because it keeps the keys in sorted order and multimap also stores the keys in sorted order, but the advantage of the multimap is to support multiple same key-value pairs.
We implemented the below methods in MultiMap:
void put(char Key, int value); // To put a new Key-Value pair
void get(char key); // To get the values mapped with key
void removeAll(char key); // To remove all values mapped with given key
boolean remove(char key, int value); // To remove specific Key-Value pair
int size(); // To get Size of MultiMap
boolean containsKey(char key); // To check key is present in MultiMap
String toString(); // This method is override to print the multimap
The Time Complexity of all above operations is O(log n) except size() it’s O(1) and toString is O(key*values).
Below is the implementation of MultiMap in Java using TreeMap
Java
/*package whatever //do not write package name here */import java.util.*;// MultiMap Implementationclass MultiMap { // Key is a Type of Character // Value is a Type of Integer private TreeMap<Character, List<Integer> > treeMap; private int size; // Constructor public MultiMap() { treeMap = new TreeMap<Character, List<Integer> >(); size = 0; } // to Add key-value public void put(char key, int value) { treeMap.computeIfAbsent(key, k -> new ArrayList<>()) .add(value); ++size; } // get function -> returns a values mapped with key public List<Integer> get(char key) { return this.containsKey(key) ? treeMap.get(key) : new ArrayList<Integer>(); } // this will remove key and all values associated with // it public void removeAll(char key) { if (this.containsKey(key)) { size -= treeMap.get(key).size(); treeMap.remove(key); } } // this will remove a specific pair of key and value if // value is mapped with same key a // and return true if same key and value removed from // MultiMap else false. public boolean remove(char key, int value) { boolean isKeyPresent = this.containsKey(key); // If key not present then return false; if (!isKeyPresent) { return false; } boolean isValuePresent = treeMap.get(key).contains(value); if (isValuePresent) { treeMap.get(key).remove(new Integer(value)); --size; } return isKeyPresent && isValuePresent; } // this function will return the size of MultiMap public int size() { return this.size; } // To check key is present or not public boolean containsKey(char key) { return treeMap.containsKey(key); } // Override toString method to print MultiMap with key // and value rather in object form @Override public String toString() { String printMultiMap = "{\n"; for (char key : treeMap.keySet()) { printMultiMap += key + " = " + treeMap.get(key).toString() + "\n"; } printMultiMap += "}"; return printMultiMap; }}public class GFG { public static void main(String[] args) { // initializing multimap MultiMap multiMap = new MultiMap(); // adding values in multimap multiMap.put('A', 1); multiMap.put('B', 2); multiMap.put('C', 3); multiMap.put('A', 4); multiMap.put('B', 5); multiMap.put('A', 6); multiMap.put('D', 7); multiMap.put('D', 8); // Printing Multimap System.out.println("Key and Values in MultiMap : "); System.out.println(multiMap); // Printing size System.out.println("\nSize Of multiMap : " + multiMap.size()); // Remove specific key-value pair multiMap.remove('A', 4); // MultiMap After performing remove operations System.out.println( "\nAfter performing remove operation"); System.out.println("Key and Values in MultiMap : "); System.out.println(multiMap); System.out.println("\nSize Of multiMap : " + multiMap.size()); // Remove all value associated with key multiMap.removeAll('D'); // MultiMap After performing remove operations System.out.println( "\nAfter performing removeAll operation"); System.out.println("Key and Values in MultiMap : "); System.out.println(multiMap); System.out.println("\nSize Of multiMap : " + multiMap.size()); // get values System.out.println( "Values in MultiMap associated with key: "); System.out.println(multiMap.get('B')); // check key is present or not System.out.println("\nIs 'A' Present?" + multiMap.containsKey('A')); // MultiMap After performing all operations System.out.println( "\nKey and Values in MultiMap : "); System.out.println(multiMap); }} |
Key and Values in MultiMap :
{
A = [1, 4, 6]
B = [2, 5]
C = [3]
D = [7, 8]
}
Size Of multiMap : 8
After performing remove operation
Key and Values in MultiMap :
{
A = [1, 6]
B = [2, 5]
C = [3]
D = [7, 8]
}
Size Of multiMap : 7
After performing removeAll operation
Key and Values in MultiMap :
{
A = [1, 6]
B = [2, 5]
C = [3]
}
Size Of multiMap : 5
Values in MultiMap associated with key:
[2, 5]
Is 'A' Present?true
Key and Values in MultiMap :
{
A = [1, 6]
B = [2, 5]
C = [3]
}
