The second major Java data structure is the HashMap. As you probably recall, HashMaps differ from ArrayLists in that you can access items in a HashMap (also called a “map” for short) by a key rather than a position. Later in this book you will see that there are many ways to implement a HashMap. The thing that is most important to notice right now is that the get and put methods on a HashMap are \(O(1)\text{.}\) Another important HashMap operation is the containsKey operation. Checking to see whether a key is in the HashMap or not is also \(O(1)\text{.}\) The efficiency of common HashMap operations is summarized in Table 2.7.1. One important side note on dictionary performance is that the efficiencies we provide in the table are for average performance. In some rare cases the contains, get, and set operations can degenerate into \(O(n)\) performance, but we will get into that in Chapter 8 when we talk about the different ways that a dictionary could be implemented.
Table2.7.1.Big O Efficiency of Java HashMap Operations
Operation
Big O Efficiency
putAll (copy to another HashMap)
O(n)
get
O(1)
put (set item)
O(1)
remove
O(1)
containsKey
O(1)
iteration
O(n)
For our last performance experiment, we will compare the performance of the contains method for ArrayLists and the containsKey operation for HashMaps. In the process we will confirm that the operation for ArrayLists is \(O(n)\) and the operation for HashMaps is \(O(1)\text{.}\) The experiment we will use to compare the two is as follows: we’ll make a list with a range of numbers in it, then we will pick numbers at random and check to see if the numbers are in the list. If our performance tables are correct, the bigger the list, the longer it should take to determine if any one number is contained in the list.
We will repeat the same experiment for a HashMap that contains numbers as the keys. In this experiment we should see that determining whether or not a number is in the HashMap is not only much faster, but the time it takes to check should remain constant even as the HashMap grows larger.
Listing 2.7.2 implements this comparison. Notice that we are performing exactly the same operation, even though they have different names: list.contains(number) and map.containsKey(number).
Listing2.7.2.
Figure 2.7.3 summarizes the results of running Listing 2.7.2. You can see that the dictionary is consistently faster. For the smallest size of 10,000 elements, a HashMap is 58.2 times faster than an ArrayList. For the largest size of 990,000 elements the HashMap is 3,972 times faster! You can also see that the time it takes for the contains method on the ArrayList grows linearly with the size of the list. This verifies the assertion that the contains method on a list is \(O(n)\text{.}\) It can also be seen that the time for the containsKey method on a HashMap is constant even as the dictionary size grows.
Figure2.7.3.Comparing Time to Find Elements for Java ArrayList and HashMap
ExercisesSelf Check
1.
Q-1: Which of the ArrayList operations shown below is not O(1)?
myList.remove(0)
When you remove the first element of a list, all the other elements of the list must be shifted forward.
myList.remove(myList.size() - 1)
Removing an element from the end of the list is a constant operation.
myList.add()
Appending to the end of the list is a constant operation
myList.get(10)
Indexing a list is a constant operation
all of the above are O(1)
There is one operation that requires all other list elements to be moved.
2.
Q-2: Which of the HashMap operations shown below is O(1)?
myMap.containsKey("x")
in is a constant operation for a HashMap because you do not have to iterate but there is a better answer.
myMap.remove("x")
removing an element from a HashMap is a constant operation but there is a better answer.
myMap.put("x", 22)
Assignment to a HashMap key is constant but there is a better answer.
all of the above are O(1)
The only dictionary operations that are not O(1) are those that require iteration.
