What are HashMaps— You Might be Asked These in an Interview — Examples in Java
Let’s quickly go over what a HashMap is.
Simply speaking it is a Collection object which uses Key and Value pairs, where both parameters are objects declared on creation. Each Key maps to a corresponding Value. E.g. the key “foo” maps the value “bar”.
It is declared as HashMap<Key, Value>.
Consider you’re making a HashMap of players on a football team, and each of them is identified by a unique number. We would create this map by using an Integer as the Key, and a String of the player’s name as the Value.
HashMap<String, Integer> playerMap = new HashMap<String, Integer>();// Put players into our HashMap where they can be found with an int
playerMap.put(23, "David Beckham");
playerMap.put(7, "Cristiano Ronaldo");
playerMap.put(10, "Lionel Mess");
playerMap.put(31, "Neymar");// Return a specific player
System.out.print(playerMap.get(23)); // "David Beckham"
As a note, a HashMap does not make any guarantees of order or sorting. When you add a Key to your HashMap, there is no reason it will be returned to you at the same location or even at a constant speed. As well, HashMaps are not thread safe so if you’re working in a multi-threaded environment consider using a different data object. But we’ll get to that later.
Previously in versions of Java < 8, finding values of large HashMaps with the .get() method would have a worse case complexity of O(n). However, since Java 8 it is now O(log N). So there has been a substantial performance improvement, which make this data structure quite attractive to use.
Creating Different Types of HashMap
// You'll need to import a HashMap for this to work in your
// Java project
import java.util.HashMap; // Let's create a bunch of HashMaps// Creating vanilla HashMap
HashMap<String, Integer> map = new HashMap<String, Integer>();
// Creating HashMap with a capacity ... in this case 100
Integer capacity = 100;
HashMap<String, Integer> map_2 = new HashMap<String, Integer>(capacity);
// Creating HashMap with capacity and load factor
Integer capacity = 100;
Double loadFactor = .5
HashMap<String, Integer> map3 = new HashMap<String, Integer (capacity, loadFactor);
What is a capacity and load factor for a HashMap?
When a HashMap is instantiated there are two parameters that will affect its performance: initial capacity and load factor. Capacity is the number of buckets/bins in the hash table. While the load factor measures how many values the hash table is allowed to get before capacity is automatically increased. When the amount of items in the table is greater and the load factor and the capacity, the table is rehashed. Meaning the structure of the data is rebuilt with twice the number of buckets specified in the instantiation.
Think of it as, “At what capacity percentage of items in my HashMap will cause it to automatically expand?”
And, if you ever want to know which hash bucket you value lives in, you can use the key.hashCode() method to find out.
Printing All Values In The Map — EntrySet Vs. KeySet
There are two primary methods to loop through a HashMap, entrySet and keySet.
When using an keySet you’re returning a set of the key objects in your HashMap. Remember from our example above we were able to return the player we wanted by using .get(playerNumber). Now have a list of all the player’s number so getting all the players will be easy.
// Print all the players using a keySetfor (Integer key : playerMap.keySet()) {
System.out.println(key + ":" + map.get(key));
}// Results
23:David Beckham
7:Cristiano Ronaldo
...
By calling entrySet() on your map you create an Entry object that stores information in a structure that can easily be looped over. Looping over an entrySet is faster, as you’re not going to be asking the HashMap for the key twice. Notice how above we returned the key and then used it again in map.get(key)? With our entrySet we only need to call getKey() and getValue() as we loop through our Entry object.
Also, entrySet implementations usually implement the toString() method, so this saves you some time when printing to the console.
// Print all the players using a entrySetfor (Entry <Integer, String> entry : playerMap.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}// Results
23:David Beckham
7:Cristiano Ronaldo
...
So which one to use? Generally speaking using an entrySet is better practice as it has less overhead.
Adding Pairs to HashMap If Not Present?
This is fairly straightforward, as the putIfAbsent() method does most of the work for you. If the key is not yet used, the key will be successfully inserted and the method will return null. However, if the key is already in the HashMap the value will instead be returned.
// Add a football player to the playerMap if he is not in there
// already ... remember David Beckham is 23// Try adding to an existing key
String result = playerMap.putIfAbsent(23, "Thomas Müller");
System.out.print(result) // David Beckham// Try adding to a new key
String result = playerMap.putIfAbsent(5, "Thomas Müller");
System.out.print(result) // Null
How Do You Remove a Value? What About Changing the Value?
To remove values from the HashMap use the .remove() method, which works with just keys, or keys and values if you want an element removed only if it is equal to a specific value.
This is helpful when you want keys in your map only when certain conditions about those keys are in play.
// Remove a player from the HashMap
playerMap.remove(23);
playerMap.get(23); // Null// Remove a player only if the key maps to a specific name
// Remember 10 is mapped to Messi
playerMap.remove(10, "Thomas Müller");
playerMap.get(10) // "Lionel Messi"
Now that we know how to remove keys, what about changing their value? The .replace() method will help us out here. And, similar to the .remove() above, you’re able to replace value only if it is currently mapped to a specific you want to be replaced.
The syntax for both method signatures is quite similar, .replace(key, value) and .replace(key, oldValue, newValue).
// Replace a player
playerMap.replace(23, "Wayne Rooney");
playerMap.get(23) // "Wayne Rooney"// Replace a player only if it is currently mapped to a specific
// value ... won't replace because does not match
playerMap.replace(23, "Thomas Müller", "Wayne Rooney");
playerMap.get(23) // "David Beckham"
How Do You Check Whether a Specific Key-Value Pair Exist?
Using containsKey() and containsValue() methods.
// Check if a key exists
Boolean hasKey = playerMap.containsKey(23)
hasKey // True// Check if a value exists
Boolean hasValue = playerMap.containsKey("Foo Bar")
hasValue // False
How Do You Remove a Mapping While Looping?
Now that we can loop through our HashMap and can add, destroy, or modify sections of it, let’s look at combining all of those into a question. Let’s say you wanted to remove a key of your HashMap during a loop, how would you do that?
// Start with getting the entrySet and remove/edit the
// values you wantfor (Entry<Integer, String> entry : playerMap.entrySet()) { // You can set this to anything ... this is just an example
if entry.getKey().equals("23") {
playerMap.remove(entry.getKey())
}
}
Bonus: Some Specialized HashMaps
Keep in mind there are different flavours to HashMaps, and I’ll outline them below with their use cases.
1. ConcurrentHashMap: HashMap to be used in multithreaded applications. This solves the multithreading issue brought up previously, however, ConcurrentHashMap performance is low sometimes because sometimes threads are required to wait.
2. EnumMap: HashMap with Enum values as keys. Shown in the example below.
// Instantiation of EnumMap
EnumMap<Key extends Enum<Key>,Value>public enum STATE {
1, 2, 3, 4;
}
// Create the Map
EnumMap<STATE, String> enumMap = new EnumMap<STATE, String (STATE.class);
// Add values to the enumMap
enumMap.put(STATE.1, "DEFCON - 1");
enumMap.put(STATE.2, "DEFCON - 2");
enumMap.put(STATE.3, "DEFCON - 3");
enumMap.put(STATE.4, "DEFCON - 4");
3. LinkedHashMap: This HashMap has a predictable iteration order as it maintains a linked list of the entries in the map, which is great if you’re using the map for a FIFO/LIFO purposes. While looping through, the elements will be returned in the order in which they were inserted.
Final Thoughts
This was just a short article on HashMaps and how you might approach different problems associated with them. HashMaps are important data structures which have many more applications I laid out here. Especially since the performance has greatly improved in Java 8.
As always, I hope you learned something new.
Cheers,
Additional Reading
https://medium.com/@dhruvamsharma/how-hashmap-works-a-missing-piece-of-hood-29dd28c4c01e
