How to use Java TreeMap with Examples

[no_toc]
In the tutorial, Grokonez introduces about Java TreeMap and how to use it by examples:
– Explore Java TreeMap’s hierarchy.
– Do examples with Java TreeMap method APIs

Let’s start with more details!

Related posts:
– How to use Java PriorityQueue with Examples

Java TreeMap

public class TreeMap
	extends AbstractMap
		implements NavigableMap, Cloneable, Serializable
		
public interface NavigableMap
	extends SortedMap

– Java TreeMap extends AbstractMap class and implements NavigableMap interface. Here is Java TreeMap hierarchy:

– Java TreeMap use a Red-Black tree based NavigableMap implementation.

– Java TreeMap is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

– Java TreeMap provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

– Java TreeMap’s implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

– Java TreeMap has all the functionalities of SortedMap and NavigableMap interface. A SortedMap extended with navigation methods returning the closest matches for given search targets:

+ Methods lowerEntry, floorEntry, ceilingEntry, and higherEntry return Map.Entry objects associated with keys respectively less than, less than or equal, greater than or equal, and greater than a given key, returning null if there is no such key.
+ Methods lowerKey, floorKey, ceilingKey, and higherKey return only the associated keys
+ Methods firstEntry, pollFirstEntry, lastEntry, and pollLastEntry that return and/or remove the least and greatest mappings, if any exist, else returning null.

– Java TreeMap cannot contain duplicate keys; each key can map to at most one value.

– Java TreeMap cannot contain the null key. BUT It can have null values.

Construct Java TreeMap

Setup for Examples

– Create 2 classes KeyInfo and Employee:

class KeyInfo{
	Integer id;
	String name;
	
	public KeyInfo(Integer id, String name) {
		this.id = id;
		this.name = name;
	}
	
	public int getId() {
		return this.id;
	}
	
	public String getName() {
		return this.name;
	}
	
	public String toString() {
		return String.format("[id = %d, name = %s]", id, name);
	}
}

class Employee{
	Integer id;
	String name;
	Double salary;
	String city;
	
	public Employee(Integer id, String name, Double salary, String city){
		this.id = id;
		this.name = name;
		this.salary = salary;
		this.city = city;
	}
	
	public int getId() {
		return this.id;
	}
	
	public String getName() {
		return this.name;
	}
	
	public Double getSalary() {
		return this.salary;
	}
	
	public String getCity() {
		return this.city;
	}
	
	public String toString() {
		return String.format("[id = %d, name = %s, salary = %.2f, city = %s]", id, name, salary, city);
	}
}

1. TreeMap() Constructor

Detail:

public TreeMap()

– Constructs a new, empty Java Tree Map, using the natural ordering of its keys.
– All keys inserted into the map must implement the Comparable interface.

Example:

Map 	numberMap = new TreeMap();

numberMap.put(1, "one");
numberMap.put(9, "nine");
numberMap.put(5, "five");
numberMap.put(2, "two");
numberMap.put(7, "seven");
numberMap.put(4, "four");

System.out.println(numberMap);

-> Output:

{1=one, 2=two, 4=four, 5=five, 7=seven, 9=nine}

Java TreeMap with Comparable Object Keys

Add Comparable interface to KeyInfo class:

class KeyInfo implements Comparable{
	...
	
	@Override
	public int compareTo(KeyInfo o) {
		if(id == o.id)  
			return 0;  
		else if(id > o.id)  
			return 1;  
		else
			return -1; 
	}

	...
}

– Create Java TreeMap Example:

Map employeeMap = new TreeMap();

employeeMap.put(new KeyInfo(1, "Jack"), new Employee(1, "Jack", 6000.0, "Fall River"));
employeeMap.put(new KeyInfo(4, "Joe"), new Employee(4, "Joe", 7000.0, "Wilmington"));
employeeMap.put(new KeyInfo(10, "Davis"), new Employee(10, "Davis", 6500.0, "Hammond"));
employeeMap.put(new KeyInfo(7, "Mary"), new Employee(6, "Mary", 5700.0, "Duluth"));
employeeMap.put(new KeyInfo(9, "Jane"), new Employee(8, "Jane", 8000.0, "Albany"));
employeeMap.put(new KeyInfo(3, "Harry"), new Employee(3, "Harry", 6800.0, "Parma"));

System.out.println(employeeMap);

-> Output:

//	{	
//		[id = 1, name = Jack]=[id = 1, name = Jack, salary = 6000,00, city = Fall River], 
// 		[id = 3, name = Harry]=[id = 3, name = Harry, salary = 6800,00, city = Parma], 
//		[id = 4, name = Joe]=[id = 4, name = Joe, salary = 7000,00, city = Wilmington], 
//		[id = 7, name = Mary]=[id = 6, name = Mary, salary = 5700,00, city = Duluth], 
//		[id = 9, name = Jane]=[id = 8, name = Jane, salary = 8000,00, city = Albany], 
//		[id = 10, name = Davis]=[id = 10, name = Davis, salary = 6500,00, city = Hammond]
//	}

2. TreeMap(comparator) Constructor

Detail:

public TreeMap(Comparator comparator)

– Constructs a new, empty tree map, ordered according to the given comparator.
– All keys inserted into the map must be mutually comparable by the given comparator.
– The comparator that will be used to order this map. If null, the natural ordering of the keys will be used.

Example: reverse order of entries

Map 	numberMap = new TreeMap(Comparator.reverseOrder());

numberMap.put(1, "one");
numberMap.put(9, "nine");
numberMap.put(5, "five");
numberMap.put(2, "two");
numberMap.put(7, "seven");
numberMap.put(4, "four");

System.out.println(numberMap);

-> Output:

// {9=nine, 7=seven, 5=five, 4=four, 2=two, 1=one}

Create Java TreeMap Example with Object Keys using Comparator

– Implement Comparator class in Java TreeMap constructor:

Map employeeMap = new TreeMap(new Comparator() {

	@Override
	public int compare(KeyInfo o1, KeyInfo o2) {
		if (o1.id == o2.id) 
		    return 0; 
		else if(o1.id < o2.id)
			return 1;
		else 
			return -1;
	}
});

- Add entries to the TreeMap:

employeeMap.put(new KeyInfo(1, "Jack"), new Employee(1, "Jack", 6000.0, "Fall River"));
employeeMap.put(new KeyInfo(4, "Joe"), new Employee(4, "Joe", 7000.0, "Wilmington"));
employeeMap.put(new KeyInfo(10, "Davis"), new Employee(10, "Davis", 6500.0, "Hammond"));
employeeMap.put(new KeyInfo(7, "Mary"), new Employee(6, "Mary", 5700.0, "Duluth"));
employeeMap.put(new KeyInfo(9, "Jane"), new Employee(8, "Jane", 8000.0, "Albany"));
employeeMap.put(new KeyInfo(3, "Harry"), new Employee(3, "Harry", 6800.0, "Parma"));

System.out.println(employeeMap);

-> Output:

//	{
//		[id = 10, name = Davis]=[id = 10, name = Davis, salary = 6500,00, city = Hammond], 
//		[id = 9, name = Jane]=[id = 8, name = Jane, salary = 8000,00, city = Albany], 
//		[id = 7, name = Mary]=[id = 6, name = Mary, salary = 5700,00, city = Duluth], 
//		[id = 4, name = Joe]=[id = 4, name = Joe, salary = 7000,00, city = Wilmington], 
//		[id = 3, name = Harry]=[id = 3, name = Harry, salary = 6800,00, city = Parma], 
//		[id = 1, name = Jack]=[id = 1, name = Jack, salary = 6000,00, city = Fall River]
//	}

3. TreeMap(Map m) Constructor

Detail:

public TreeMap(Map m)

- Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys
- All keys inserted into the new map must implement the Comparable interface.
- BigO = n*log(n) time.

Example:

- Add Comparable to KeyInfo:

class KeyInfo implements Comparable{
	...

	@Override
	public int compareTo(KeyInfo o) {
		if(id == o.id)  
			return 0;  
		else if(id > o.id)  
			return 1;  
		else
			return -1; 
	}
	
	...
}

- Create a Java TreeMap:

Map employeeMap = new TreeMap(new HashMap() {
	{
		put(new KeyInfo(1, "Jack"), new Employee(1, "Jack", 6000.0, "Fall River"));
		put(new KeyInfo(4, "Joe"), new Employee(4, "Joe", 7000.0, "Wilmington"));
		put(new KeyInfo(10, "Davis"), new Employee(10, "Davis", 6500.0, "Hammond"));
		put(new KeyInfo(7, "Mary"), new Employee(6, "Mary", 5700.0, "Duluth"));
		put(new KeyInfo(9, "Jane"), new Employee(8, "Jane", 8000.0, "Albany"));
		put(new KeyInfo(3, "Harry"), new Employee(3, "Harry", 6800.0, "Parma"));
	}
});

System.out.println(employeeMap);

-> Output:

//	{
//		[id = 10, name = Davis]=[id = 10, name = Davis, salary = 6500,00, city = Hammond], 
//		[id = 9, name = Jane]=[id = 8, name = Jane, salary = 8000,00, city = Albany], 
//		[id = 7, name = Mary]=[id = 6, name = Mary, salary = 5700,00, city = Duluth], 
//		[id = 4, name = Joe]=[id = 4, name = Joe, salary = 7000,00, city = Wilmington], 
//		[id = 3, name = Harry]=[id = 3, name = Harry, salary = 6800,00, city = Parma], 
//		[id = 1, name = Jack]=[id = 1, name = Jack, salary = 6000,00, city = Fall River]
//	}

4. TreeMap(SortedMap m) Constructor

Detail:

public TreeMap(SortedMap m)

- Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.
- This method runs in linear time.

Example:

+ Create SortedMap:

SortedMap sortedMap = new TreeMap();

sortedMap.put(new KeyInfo(1, "Jack"), new Employee(1, "Jack", 6000.0, "Fall River"));
sortedMap.put(new KeyInfo(4, "Joe"), new Employee(4, "Joe", 7000.0, "Wilmington"));
sortedMap.put(new KeyInfo(10, "Davis"), new Employee(10, "Davis", 6500.0, "Hammond"));
sortedMap.put(new KeyInfo(7, "Mary"), new Employee(6, "Mary", 5700.0, "Duluth"));
sortedMap.put(new KeyInfo(9, "Jane"), new Employee(8, "Jane", 8000.0, "Albany"));
sortedMap.put(new KeyInfo(3, "Harry"), new Employee(3, "Harry", 6800.0, "Parma"));

+ Then init a Java TreeMap:

Map newEmployeesMap = new TreeMap(sortedMap);

System.out.println(newEmployeesMap);

-> Output:

//	{	
//		[id = 1, name = Jack]=[id = 1, name = Jack, salary = 6000,00, city = Fall River], 
// 		[id = 3, name = Harry]=[id = 3, name = Harry, salary = 6800,00, city = Parma], 
//		[id = 4, name = Joe]=[id = 4, name = Joe, salary = 7000,00, city = Wilmington], 
//		[id = 7, name = Mary]=[id = 6, name = Mary, salary = 5700,00, city = Duluth], 
//		[id = 9, name = Jane]=[id = 8, name = Jane, salary = 8000,00, city = Albany], 
//		[id = 10, name = Davis]=[id = 10, name = Davis, salary = 6500,00, city = Hammond]
//	}

Find/Search Key-Value Pair in Java TreeMap

Following the example, We use a set of TreeMap functionalities:

- ceilingEntry(K key):
-> returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

- ceilingKey(K key):
-> returns the least key greater than or equal to the given key, or null if there is no such key.

- containsKey(Object key):
-> returns true if this map contains a mapping for the specified key.

- containsValue(Object value):
-> returns true if this map maps one or more keys to the specified value.

- firstEntry():
-> returns a key-value mapping associated with the least key in this map, or null if the map is empty.

- firstKey():
-> returns the first (lowest) key currently in this map.

- floorEntry(K key):
-> returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

- floorKey(K key):
-> returns the greatest key less than or equal to the given key, or null if there is no such key.

- get(Object key):
-> returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

- lastEntry():
-> Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

- lastKey():
-> Returns the last (highest) key currently in this map.

- lowerEntry(K key):
-> Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

- lowerKey(K key):
-> Returns the greatest key strictly less than the given key, or null if there is no such key.

Example:

TreeMap numberMap = new TreeMap();

numberMap.put(1, "one");
numberMap.put(9, "nine");
numberMap.put(5, "five");
numberMap.put(2, "two");
numberMap.put(7, "seven");
numberMap.put(4, "four");

Entry keyValue = numberMap.ceilingEntry(6);
System.out.println(keyValue); // 7=seven

Integer key = numberMap.ceilingKey(6);
System.out.println(key); // 7

boolean c =numberMap.containsKey(6);
System.out.println(c); // false

c = numberMap.containsValue("seven");
System.out.println(c); // true

keyValue = numberMap.firstEntry();
System.out.println(keyValue); // 1=one

Integer firstKey = numberMap.firstKey();
System.out.println(firstKey); // 1

keyValue = numberMap.floorEntry(6);
System.out.println(keyValue); // 5=five

key = numberMap.floorKey(6);
System.out.println(key); // 5

String value = numberMap.get(5);
System.out.println(value); // five

keyValue = numberMap.lastEntry();
System.out.println(keyValue); // 9=nine

key = numberMap.lastKey();
System.out.println(key); // 9

keyValue = numberMap.lowerEntry(9);
System.out.println(keyValue); // 7=seven

key = numberMap.lowerKey(9);
System.out.println(key); // 7

Modify/Remove Entries of Java TreeMap

List of method APIs to modify and remove entries of Java TreeMap Collection:

- pollFirstEntry(): Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
- pollLastEntry(): Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
- put(K key, V value): Associates the specified value with the specified key in this map.
- putAll(Map map): Copies all of the mappings from the specified map to this map.

Example:

TreeMap numberMap = new TreeMap();

numberMap.put(1, "one");
numberMap.put(9, "nine");
numberMap.put(5, "five");
numberMap.put(2, "two");
numberMap.put(7, "seven");
numberMap.put(4, "four");

numberMap.pollFirstEntry();

System.out.println(numberMap); 
// {2=two, 4=four, 5=five, 7=seven, 9=nine}

numberMap.pollLastEntry();

System.out.println(numberMap);
// {2=two, 4=four, 5=five, 7=seven}

numberMap.put(2, "TWO");

System.out.println(numberMap);
// {2=TWO, 4=four, 5=five, 7=seven}

TreeMap addingNumberMap = new TreeMap();
addingNumberMap.put(10, "ten");
addingNumberMap.put(11, "eleven");

numberMap.putAll(addingNumberMap);

System.out.println(numberMap);
// {2=TWO, 4=four, 5=five, 7=seven, 10=ten, 11=eleven}

Getting a View of Java TreeMap

List of method APIs to get a view portion of Java TreeMap:

- descendingKeySet():
-> Returns a reverse order NavigableSet view of the keys contained in this map.

- descendingMap():
-> Returns a Set view of the mappings contained in this map.

- headMap(K toKey):
-> Returns a view of the portion of this map whose keys are strictly less than toKey.

- headMap(K toKey, boolean inclusive):
-> Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.

- subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive):
-> Returns a view of the portion of this map whose keys range from fromKey to toKey.

- subMap(K fromKey, K toKey):
-> Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

- tailMap(K fromKey):
-> Returns a view of the portion of this map whose keys are greater than or equal to fromKey.

- tailMap(K fromKey, boolean inclusive)
-> Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.

- values():
-> Returns a Collection view of the values contained in this map.

Example:

TreeMap numberMap = new TreeMap();

numberMap.put(1, "one");
numberMap.put(9, "nine");
numberMap.put(5, "five");
numberMap.put(2, "two");
numberMap.put(7, "seven");
numberMap.put(4, "four");

NavigableSet descendingKeySet = numberMap.descendingKeySet();
System.out.println(descendingKeySet);
// [9, 7, 5, 4, 2, 1]

NavigableMap descendingMap = numberMap.descendingMap();
System.out.println(descendingMap);
// {9=nine, 7=seven, 5=five, 4=four, 2=two, 1=one}

SortedMap headMap = numberMap.headMap(9);
System.out.println(headMap);
// {1=one, 2=two, 4=four, 5=five, 7=seven}

NavigableMap subMap = numberMap.subMap(2, false, 9, true);
System.out.println(subMap);
// {4=four, 5=five, 7=seven, 9=nine}

SortedMap tailMap = numberMap.tailMap(5);
System.out.println(tailMap);
// {5=five, 7=seven, 9=nine}

tailMap = numberMap.tailMap(5, false);
System.out.println(tailMap);
// {7=seven, 9=nine}

Collection values = numberMap.values();
System.out.println(values);
// [one, two, four, five, seven, nine]

Conclusion

We had learned how to use Java TreeMap by examples:

• Explore Java TreeMap hierarchy.
• How to construct Java TreeMap with difference constructors.
• Create Java TreeMap and through almost Java TreeMap's method APIs.

Happy Learning! See you later!