A couple weeks ago, during a meeting, someone mentioned an interval hashmap. I decided to check if Java had a class implementing a version of an interval hashmap. As you can imagine, it does and is called NavigableMap.
In this post I explored some of the features available in the NavigableMap interface.
If interested, I would suggest to first take a look at the Interface NavigableMap<K, V> in the Oracle Java documentation which can be found here.
After reading the Oracle documentation and some articles in GeeksforGeeks and StackOverflow I decided to start experimenting.
In this post I am using the VSCode IDE and using the Java programming language on a Windows 11 computer.
Let’s first take a look at the screen capture of the input and output used by and generated by the test scaffold.
9
S 700
A 100
C 200
K 400
L 500
O 600
U 800
G 300
W 900
main <<< n: 9
main <<< nm: {A=100, C=200, G=300, K=400, L=500, O=600, S=700, U=800, W=900}
main <<< nm: {A=100, C=200, G=300, K=400, L=500, O=600, S=700, U=800, W=900}
main <<< size: 9
main <<< descending key set: [W, U, S, O, L, K, G, C, A]
main <<< first key: A
main <<< last key: W
main <<< descending map: {W=900, U=800, S=700, O=600, L=500, K=400, G=300, C=200, A=100}
main >>> add key val: B 150
main <<< key ==>B<== val: 150
main <<< nm: {A=100, B=150, C=200, G=300, K=400, L=500, O=600, S=700, U=800, W=900}
main <<< size: 10
main >>> floor key: Kilo
main <<< floor key ==>Kilo<==
main <<< floor entry: K=400
main <<< first entry: A=100
main <<< lower key: K
main <<< floor key: K
main <<< ceiling key: L
main <<< higher key: L
main >>> remove key: Papa
main <<< key ==>Papa<==
main <<< key ==>Papa<== NOT found
main <<< nm: {A=100, B=150, C=200, G=300, K=400, L=500, O=600, S=700, U=800, W=900}
main <<< size: 10
main >>> get key: Lima
main <<< key ==>Lima<==
main <<< key ==>Lima<== NOT found
main <<< entry: A 100
main <<< entry: B 150
main <<< entry: C 200
main <<< entry: G 300
main <<< entry: K 400
main <<< entry: L 500
main <<< entry: O 600
main <<< entry: S 700
main <<< entry: U 800
main <<< entry: W 900
main <<< ent: A 100
main <<< ent: B 150
main <<< ent: C 200
main <<< ent: G 300
main <<< ent: K 400
main <<< ent: L 500
main <<< ent: O 600
main <<< ent: S 700
main <<< ent: U 800
main <<< ent: W 900
main >>> head key: Kilo
main <<< key ==>Kilo<==
main <<< ent: A 100
main <<< ent: B 150
main <<< ent: C 200
main <<< ent: G 300
main <<< ent: K 400
main >>> tail key: Kilo
main <<< key ==>Kilo<==
main <<< ent: L 500
main <<< ent: O 600
main <<< ent: S 700
main <<< ent: U 800
main <<< ent: W 900
We start by specifying the number of pairs we will provide. After that we have a set of String, Integer pairs. The string represents a key and the integer the associated value.
The actual test scaffold is labeled with single digits which map to the blank lines we see in the screen capture.
I experimented with different values. To get a good feeling of the features and how they might be used, I suggest spending some time experimenting with different initial values. The same holds true for the values entered when the program requests keys.
In addition, there are so many other methods that you might want to experiment with. Just expand the code as you see fit.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.Map.Entry;
/**
* TreeMap is a Red-Black tree based NavigableMap implementation
* and it is sorted according to the natural ordering of its keys.
* The TreeMap has the expected time cost of log(n) for insertion, deletion, and access operations.
* TreeMap is not synchronized and it has to be done externally.
* The insertion order is not retained.
*/
public class IntervalHashmap {
// ???? main goes in here ????
}
In this code snippet I show the header files. Nowadays most IDEs can include them when a reference for a class is not found. That is what I typically do when using VSCode.
In this example we are using a TreeMap for the NavigableMap interface. Feel free to try others and find out how they fit the interface of interest.
/**
* Test scaffold.
* @throws IOException
*/
public static void main (String[] args) throws IOException {
// **** initialization ****
int val = 0;
NavigableMap<String, Integer> nm = new TreeMap<String, Integer>();
String key = "";
Entry<String, Integer> entry = null;
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** [0] read number of pairs ****
int n = Integer.parseInt(br.readLine().trim());
// **** populate the map ****
for (int i = 0; i < n; i++) {
// **** split line ****
String[] strs = br.readLine().trim().split(" ");
strs[1] = strs[1].trim();
// **** for ease of use ****
key = strs[0];
val = Integer.parseInt(strs[1]);
// **** put pair in map ****
nm.put(strs[0], Integer.parseInt(strs[1]));
}
// ???? ????
System.out.println("main <<< n: " + n);
// **** ???? ???? ****
System.out.printf("main <<< nm: %s\n", nm);
System.out.printf("main <<< nm: %s\n", nm.toString());
System.out.printf("main <<< size: %d\n", nm.size());
System.out.printf("main <<< descending key set: %s\n", nm.descendingKeySet());
System.out.printf("main <<< first key: %s\n", nm.firstKey());
System.out.printf("main <<< last key: %s\n", nm.lastKey());
System.out.printf("main <<< descending map: %s\n", nm.descendingMap());
// **** [1] prompt user ****
System.out.print("\nmain >>> add key val: ");
String strs[] = br.readLine().trim().split(" ");
// **** for ease of use ****
key = strs[0];
val = Integer.parseInt(strs[1]);
// ???? ????
System.out.printf("main <<< key ==>%s<== val: %d\n", key, val);
// **** put the pair in the hashmap ****
//nm.put(key, val);
nm.putIfAbsent(key, val);
// ???? ????
System.out.printf("main <<< nm: %s\n", nm.toString());
System.out.printf("main <<< size: %d\n", nm.size());
// **** [2] get floor key from user ****
System.out.print("\nmain >>> floor key: ");
key = br.readLine().trim();
// ???? ????
System.out.printf("main <<< floor key ==>%s<==\n", key);
// **** get the floor entry ****
entry = nm.floorEntry(key);
// **** display the floor entry (if needed) ****
if (entry != null)
System.out.printf("main <<< floor entry: %s\n", entry.toString());
else
System.out.printf("main <<< entry not found for key ==>%s<==\n", key);
// **** ****
System.out.printf("main <<< first entry: %s\n", nm.firstEntry());
System.out.printf("main <<< lower key: %s\n", nm.lowerKey(key));
System.out.printf("main <<< floor key: %s\n", nm.floorKey(key));
System.out.printf("main <<< ceiling key: %s\n", nm.ceilingKey(key));
System.out.printf("main <<< higher key: %s\n", nm.higherKey(key));
// **** [3] remove a key-value pair by key ****
System.out.print("\nmain >>> remove key: ");
key = br.readLine();
// ???? ????
System.out.printf("main <<< key ==>%s<==\n", key);
// **** ****
if (!nm.containsKey(key))
System.out.printf("main <<< key ==>%s<== NOT found\n", key);
// **** remove element using remove() ****
nm.remove(key);
// **** display map ****
System.out.printf("main <<< nm: %s\n", nm.toString());
System.out.printf("main <<< size: %d\n", nm.size());
// **** [4] get key-value pair ****
System.out.print("\nmain >>> get key: ");
key = br.readLine();
// ???? ????
System.out.printf("main <<< key ==>%s<==\n", key);
// **** check if key is in map ****
if (nm.containsKey(key)) {
// **** ****
val = nm.get(key);
// ???? ????
System.out.printf("main <<< key ==>%s<== val: %d\n", key, val);
} else
System.out.printf("main <<< key ==>%s<== NOT found\n", key);
// **** [5] to navigate through the map entries ****
Iterator<NavigableMap.Entry<String, Integer>> it = nm.entrySet().iterator();
// **** display all entries in the map ****
System.out.println();
while (it.hasNext()) {
// **** get next entry ****
entry = it.next();
// **** display entry ****
System.out.printf("main <<< entry: %s %d\n", entry.getKey(), entry.getValue());
}
// **** [6] traverse map using for-each ****
System.out.println();
for (Entry<String, Integer> ent : nm.entrySet())
System.out.printf("main <<< ent: %s %d\n", ent.getKey(), ent.getValue());
// **** [7] display head of map ****
System.out.print("\nmain >>> head key: ");
key = br.readLine();
// ???? ????
System.out.printf("main <<< key ==>%s<==\n", key);
// **** head map ****
NavigableMap<String, Integer> headNm = nm.headMap(key, true);
// **** traverse the head map ****
for (Entry<String, Integer> ent : headNm.entrySet())
System.out.printf("main <<< ent: %s %d\n", ent.getKey(), ent.getValue());
// **** [8] traverse tail of map ****
System.out.print("\nmain >>> tail key: ");
key = br.readLine();
// ???? ????
System.out.printf("main <<< key ==>%s<==\n", key);
// **** head map ****
NavigableMap<String, Integer> tailNm = nm.tailMap(key, true);
// **** traverse the head map ****
for (Entry<String, Integer> ent : tailNm.entrySet())
System.out.printf("main <<< ent: %s %d\n", ent.getKey(), ent.getValue());
// **** close the buffered reader ****
br.close();
}
We start our test scaffold by declaring a NavigableMap of type <String, Integer> and open a buffered reader to get the input from the user (that would be you).
We read the number of pairs followed by the actual string-integer values. As we read the pairs we populate of NavigableMap which we name nm in the code.
After we populate nm we make use of some of the methods in the nm class. None of the calls used take arguments.
In section [1] the program requires a key-value pair. With the pair in hand, we make a call to putIfAbsent(). This allows us to keep previous pairs. We could just have used put() to override existing values. It all depends on your requirements. Keep in mind that software engineering is all about properly handling trade offs, and to do that you need to know and understand your requirements, programming language, and platform.
In section [2] we are prompted to provide a floor key. It will be used to find the floor entry associate for that key in your nm. Try experimenting with strings of different lengths and values. Note that depending on the key the floor entry may or may not be found.
Next (in section [3]) we enter a key and the associated key-value pair is removed. Note that if one calls the remove() method with a key that does not match a key-value pair, no harm is done.
In section [4] we are interested in getting the associated value with a specified key. In this case if the value is not found we cannot display the pair. To address the issue we check if the key is not in nm.
In section [5] we get an iterator and navigate through nm one entry at a time. There are advantages and disadvantages of traversing a map with an iterator. For starters you need to write a few more lines of code. Let’s take a look at the next section for a simpler approach.
In section [6] we traverse / iterate through the map using a for-each loop. It is a simpler approach than the one we used in the previous section.
So far most maps support the same two approaches to traverse \ iterate through the key-value pairs.
In section [7] the program requests a key which will be used to traverse the head pairs up to the specified key. The last element may or may not be displayed.
In section [8] the program requests a key. In the example we use the same key. Note that we wish to display the last entry. This selection is hardcoded.
Using the methods in the last two sections we can split the contents of the map in multiple different ways. We just did so in two but it could have been done in three or four. It seems that there are many options at our fingertips.
When all is said and done, we close the buffered reader.
Hope you enjoyed the contents of this post and if you did not know about this class in Java know you do. Who knows when you might need such functionality. It is simpler and more robust to always use standard classes. Of course in some occasions due to different performance requirements, you might need to implement a simpler class with less features.
BTW if you use C++, the Boost library has a similar class.
As usual I have posted this code in the IntervalHashmap GitHub repository.
Keep on reading and experimenting, it is the best way to learn and refresh your knowledge.
John