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