Hash Maps
Hash maps are a common data structure used to store key-value pairs for efficient retrieval. A value stored in a hash map is retrieved using the key under which it was stored.
# `states` is a Hash Map with state abbreviation keys and state name values.
states = {
'TN': "Tennessee",
'CA': "California",
'NY': "New York",
'FL': "Florida"
}
west_coast_state = states['CA']Hash map underlying data structure
Hash maps are built on top of an underlying array data structure using an indexing system.
Each index in the array can store one key-value pair. If the hash map is implemented using chaining for collision resolution, each index can store another data structure such as a linked list, which stores all values for multiple keys that hash to the same index.
Hash function
Hash map data structures use a hash function, which turns a key into an index within an underlying array. The hash function can be used to access an index when inserting a value or retrieving a value from a hash map.
hash map only one value
Each Hash Map key can be paired with only one value. However, different keys can be paired with the same value.
#This is a valid Hash Map where 2 keys share the same value
correct_hash_map = {
"a" : 1,
"b" : 3,
"c" : 1
}
#This Hash Map is INVALID since a key cannot have more than 1 value
incorrect_hash_map = {
"a" : 1,
"a" : 3,
"b" : 2
}The retrieve() method in Java
A Java HashMap class can implement a .retrieve() instance method for retrieving a value associated with a key. It takes a key and returns a value using the .hash() method.
public String retrieve(String key) {
int arrayIndex = this.hash(key);
Node current = this.hashmap[arrayIndex].head;
while (current != null) {
if (current.key == key) {
return current.value;
}
current = current.getNextNode();
}
return null;
}The assign() method in Java
A Java HashMap class can implement an .assign() instance method for assigning a value to a key using the .hash() method. It takes key and value and returns nothing.
public void assign(String key, String value) {
int arrayIndex = this.hash(key);
LinkedList list = this.hashmap[arrayIndex];
if (list.head == null) {
list.addToHead(key, value);
return;
}
Node current = list.head;
while (current != null) {
if (current.key == key) {
current.setKeyValue(key, value);
}
if (current.getNextNode() == null) {
current.setNextNode(new Node(key, value));
break;
}
current = current.getNextNode();
}
}A Java HashMap constructor with no collisions
A Java HashMap class can implement a constructor that:
- takes
sizeas an argument - creates and stores
hashmap, which is an array of Strings ofsizethat is filled withnull
Note that this implementation does not allow for collisions.
public HashMap(int size) {
this.hashmap = new String[size];
}A Java HashMap constructor with collisions
In Java, to create a Hash Map that allows for collisions, a constructor can be implemented that creates and stores hashmap, which is an array of LinkedLists.
If a collision occurs, that value will be added to the end of the LinkedList at the proper index.
public HashMap(int size) {
this.hashmap = new LinkedList[size];
for (int i = 0; i < size; i++) {
this.hashmap[i] = new LinkedList();
}
}The Java hash() method
A Java HashMap class can implement a .hash() instance method for hashing a given key. It takes key and returns hashCode.
public int hash(String key) {
int hashCode = 0;
for (int i = 0; i < key.length(); i++) {
hashCode += hashCode + Character.codePointAt(key, i);
}
hashCode = hashCode % this.hashmap.length;
return hashCode;
}