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 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 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 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;
}