Codecademy Logo

Hash Maps

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 size as an argument
  • creates and stores hashmap, which is an array of Strings of size that is filled with null

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

Related Courses

Skill Path

Pass the Technical Interview with Java

Intermediate

36 Lessons