Let’s get back to implementing MyHashMap. Our hash map needs a function to add a key value pair to the hash map.
In the add function we’ll first need to get the bucket that our key value pair will be stored in using the getHashIndex() function defined in the last blog post. After getting the index of the correct bucket we will declare a new HashPair and add it to the end of the list in that bucket.
We’ll first declare a private addToHashMap() function that will be called by the public add() function. This will be done so that the addToHashMap() function can be reused later when resizing the hashmap. The function definition is as follows:
True will be returned if the key value pair is added correctly to the hash map. False will be returned elsewise.
Get the index of the bucket that the key value pair will be stored in. If the index is less then zero or is >= to the capacity then we are unable to add it to our hash map so return false.
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return false;
}Get the ‘bucket’ (list) the key value pair will be stored in. Return true at the end of the function. We will need different handling for null and non-null buckets.
if(list == null) {
//handle if the bucket is null here
} else {
//handle if the bucket is non null here
}
return true;If the list is equal to null then we will declare a new list and HashPair. We will add the hash pair to the list and set the index corresponding to the list in theMap to the newly declared list.
list = new LinkedList<HashPair<T, U>>();
HashPair<T, U> pair = new HashPair<T, U>(key, value);
list.add(pair);
theMap.set(index, list);If the list is not equal to null then we first need to make sure that the list doesn’t already contain the inputted key. To do this we will loop through each HashPair in the list and if any of their keys are equal to the inputted key we will return False. If the key is not already in the hashmap we will simply declare a new HashPair and add it to the list.
for(HashPair<T, U> p : list) {
if(p.key.equals(key)) {
//this hash-map already contains this key
return false;
}
}
HashPair<T, U> pair = new HashPair<T, U>(key, value);
list.add(pair);The finished addToHashMap() function is as follows:
private boolean addToHashMap(T key, U value, List<List<HashPair<T, U>>> theMap) {
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return false;
}
List<HashPair<T, U>> list = theMap.get(index);
if(list == null) {
list = new LinkedList<HashPair<T, U>>();
HashPair<T, U> pair = new HashPair<T, U>(key, value);
list.add(pair);
theMap.set(index, list);
} else {
for(HashPair<T, U> p : list) {
if(p.key.equals(key)) {
//this hash-map already contains this key
return false;
}
}
HashPair<T, U> pair = new HashPair<T, U>(key, value);
list.add(pair);
}
return true;
}Now before we get to implementing the add() function we need to first implement the resizeIfNecessary() function. What this function does is check if our currentLoadFactor is greater then the declared loadFactor. If this condition is true it then resizes the hashmap by adding more buckets to the hash map. When adding more buckets to the hash map it may change the bucket that a key value pair is in. Because of this we will make sure to replace all the hash pairs in their correct location when resizing the hashmap.
The function definition is as follows:
Make sure that the current capacity is less then the max capacity (maximum amount of buckets allowed) before attempting to resize.
Check the currentLoadFactor against the loadFactor and resize the hashmap if the currentLoadFactor is >= loadFactor. Resizing the hash map will lower the current load factor.
float currentLoadFactor = size/capacity;
if(currentLoadFactor >= loadFactor) {
//do the resizing here
}Set oldCapacity variable to the value of capacity. Multiply the capacity variable by 2.
Declare a newMap to hold the new buckets and set every index in the newMap to null.
List<List<HashPair<T, U>>> newMap = new ArrayList<List<HashPair<T, U>>>();
for(int i = 0; i < capacity; i++)
newMap.add(null);For each HashPair in each bucket of the map add it to the newMap.
for(int i = 0; i < oldCapacity; i++) {
List<HashPair<T, U>> list = map.get(i);
if(list != null) {
for(HashPair<T, U> p : list) {
addToHashMap(p.key, p.value, newMap);
}
}
}Finally, set the map to be equal to the newMap.
The finished resizeIfNecessary() function is as follows:
private void resizeIfNecessary() {
if(capacity < maxCapacity) {
float currentLoadFactor = size/capacity;
if(currentLoadFactor >= loadFactor) {
int oldCapacity = capacity;
capacity *= 2;
List<List<HashPair<T, U>>> newMap = new ArrayList<List<HashPair<T, U>>>();
for(int i = 0; i < capacity; i++)
newMap.add(null);
for(int i = 0; i < oldCapacity; i++) {
List<HashPair<T, U>> list = map.get(i);
if(list != null) {
for(HashPair<T, U> p : list) {
addToHashMap(p.key, p.value, newMap);
}
}
}
map = newMap;
}
}
}As a sidenote one could also implement their hashmap resizing function in place rather then declaring a new map if desired.
So now that the addToHashMap() and resizeIfNecessary() functions are written the add() function can now be completed. It is fairly simple.
The function definition is as follows:
Call our addToHashMap() function with the key, value, and internal map. If the key value pair is successfully added we need to increment the size and call the resizeIfNecessary() function.
The finished add() function is as follows:
public void add(T key, U value) {
if(addToHashMap(key, value, map)) {
size++;
resizeIfNecessary();
}
}That is a good place to wrap up this post. The MyHashMap implementation will be finished in the following post: Implementing a Hash Map in Java - Part Three, where we will implement the remove(), contains(), and toString() functions.