Let’s get back to implementing our MyHashMap class. Our hash map needs a function to check if the hash map contains a particular key.
This function will input a key and return true or false depending on if the hash map contains the key. The function declaration is as follows:
First we need to get the index of the bucket that would contain this key if it is in the hash map.
If the index is invalid we need to return false (ie the hashmap doesn’t contain the key).
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return false;
}Next get the bucket that the key could be potentially stored in.
If the list is not equal to null and the key is contained within the list then we have found the key we are looking for. We loop though each HashPair in the list and if the key is equal to the key we are looking for: return true.
Finally if we make it to the end of the function simply return false as we were unable to find the key in our hash map.
The finished contains function is as follows:
public boolean contains(T key) {
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 = map.get(index);
if(list != null) {
for(HashPair<T, U> p : list) {
if(p.key.equals(key))
return true;
}
}
return false;
}Next let’s work on a function that allows us to remove an item from our hash map. This function will input in the key of the object to be removed and return the value removed. If the key is not within our hash map we will return null.
The function declaration is as follows:
Similarly to our contains function we will first get the index of the bucket the key could potentially be stored in and return null if the index is invalid.
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return null;
}Next lets get the bucket at that particular index. If it is not equal to null we will then do further processing to it.
List<HashPair<T, U>> list = map.get(index);
if(list != null) {
//add code to find the hash pair and remove if from the hash map here
}Now we’ll write the code to find the correct hash pair and remove it from the hash map. First we’ll declare a null HashPair named pair. We’ll loop through each HashPair in the bucket and if we find the key we’re looking for we’ll set pair equal to it and break out of our for loop. If at the end of the for loop we haven’t found a HashPair that corresponds to our key then there is nothing to remove from our hashmap because it doesn’t contain the key.
HashPair<T, U> pair = null;
for(HashPair<T, U> p : list) {
if(p.key.equals(key)) {
pair = p;
break;
}
}If we found the hash pair to remove (ie pair is not equal to null) we will first declare a new variable named value and set it to the pair’s value. We’ll then remove the pair from the list, decrement the size of our hash map (ie set it to be 1 lower then it currently is), and return the value.
Finally if we reach the end of our function we need to return null as the key is not in the hash map. Therefore we cannot remove it.
The finished remove function is as follows:
public U remove(T key) {
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return null;
}
List<HashPair<T, U>> list = map.get(index);
if(list != null) {
HashPair<T, U> pair = null;
for(HashPair<T, U> p : list) {
if(p.key.equals(key)) {
pair = p;
break;
}
}
if(pair != null) {
U value = pair.value;
list.remove(pair);
size--;
return value;
}
}
return null;
}Next let’s add a function to get the value associated with a key. When input a key it will return the value associated with that key or null if the key is not contained within the hash map.
The finished function is as follows:
public U get(T key) {
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return null;
}
List<HashPair<T, U>> list = map.get(index);
if(list != null) {
for(HashPair<T, U> p : list) {
if(p.key.equals(key))
return p.value;
}
}
return null;
}You should notice that it is almost identical to the contains function accept that instead of returning a boolean (ie true or false) it returns the value found instead (or null if the key isn’t in the hash map).
Let’s add a toString() function for our hash map. This function will print out the contents of our hash map into a string. The function definition looks as follows:
Declare a StringBuilder s to build our string. Append ‘[’ to the beginning of our string, ’]’ to the end of our string, and return the string version of the built StringBuilder at the end of the function.
StringBuilder s = new StringBuilder();
s.append("[");
// insert the rest of the code to convert the hash map to a string here
s.append("]");
return s.toString();First get the size of the hash map and make sure that it’s greater then 0. If it’s equal to zero then we don’t need to do anything as the hash map is empty.
int theSize = getSize();
if(theSize > 0) {
// insert the rest of the code to convert the hash map to a string here
}Declare an integer counter to store the number of items that we have added to the string.
Loop through each bucket inside the hash map. Get the bucket at the index and check if it is equal to null. (if it’s equal to null then there are no items in this bucket, so no processing to do).
for(int i = 0; i < capacity; i++) {
List<HashPair<T, U>> list = map.get(i);
if(list != null) {
// add each item in the list to the string here
}
}Loop through each hash pair in the bucket. Append the key & value along with some pretty formatting to the StringBuilder s. Increment the counter by one. Then if theSize is not equal to counter (ie we are not at the last item in the hash map) append a comma and a space to the StringBuilder. This helps with formatting the string so that it is readable.
for(HashPair<T, U> p : list) {
s.append("{");
s.append(p.key);
s.append(", ");
s.append(p.value);
s.append("}");
counter++;
if(theSize != counter)
s.append(", ");
}The finished toString() function is as follows:
public String toString() {
StringBuilder s = new StringBuilder();
s.append("[");
int theSize = getSize();
if(theSize > 0) {
int counter = 0;
for(int i = 0; i < capacity; i++) {
List<HashPair<T, U>> list = map.get(i);
if(list != null) {
for(HashPair<T, U> p : list) {
s.append("{");
s.append(p.key);
s.append(", ");
s.append(p.value);
s.append("}");
counter++;
if(theSize != counter)
s.append(", ");
}
}
}
}
s.append("]");
return s.toString();
}The finished MyHashMap class is as follows:
import java.util.*;
public class MyHashMap<T, U> {
private class HashPair<R, S> {
public R key;
public S value;
public HashPair(R key, S value) {
this.key = key;
this.value = value;
}
}
private int maxCapacity = 1 << 30;
private int capacity = 2;
private float loadFactor = 0.75f;
private int size = 0;
private List<List<HashPair<T, U>>> map;
public MyHashMap() {
initHashMap();
size = 0;
}
private void initHashMap() {
map = new ArrayList<List<HashPair<T, U>>>();
for(int i = 0; i < capacity; i++)
map.add(null);
}
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;
}
}
}
public void add(T key, U value) {
if(addToHashMap(key, value, map)) {
size++;
resizeIfNecessary();
}
}
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;
}
public boolean contains(T key) {
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 = map.get(index);
if(list != null) {
for(HashPair<T, U> p : list) {
if(p.key.equals(key))
return true;
}
}
return false;
}
public U get(T key) {
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return null;
}
List<HashPair<T, U>> list = map.get(index);
if(list != null) {
for(HashPair<T, U> p : list) {
if(p.key.equals(key))
return p.value;
}
}
return null;
}
public U remove(T key) {
int index = getHashIndex(key);
if(index < 0 || index >= capacity) {
//this should never happen if we have a good hash function
return null;
}
List<HashPair<T, U>> list = map.get(index);
if(list != null) {
HashPair<T, U> pair = null;
for(HashPair<T, U> p : list) {
if(p.key.equals(key)) {
pair = p;
break;
}
}
if(pair != null) {
U value = pair.value;
list.remove(pair);
size--;
return value;
}
}
return null;
}
public void clear() {
if(getSize() > 0) {
for(int i = 0; i < capacity; i++)
map.set(0, null);
size = 0;
}
}
public int getSize() {
return size;
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append("[");
int theSize = getSize();
if(theSize > 0) {
int counter = 0;
for(int i = 0; i < capacity; i++) {
List<HashPair<T, U>> list = map.get(i);
if(list != null) {
for(HashPair<T, U> p : list) {
s.append("{");
s.append(p.key);
s.append(", ");
s.append(p.value);
s.append("}");
counter++;
if(theSize != counter)
s.append(", ");
}
}
}
}
s.append("]");
return s.toString();
}
private int getHashIndex(T key) {
return key.hashCode() % capacity;
}
}