Hash Map

Abstract

---

• Make use of Hash Function to convert a key into an index which points to a Bucket. To avoid Hash Collision, we want the hash function to evenly distribute the outputs

Unique Point

Hash map allows us to allocate any data inside in $O(1)$ time, with a higher space cost

Risk of Hash Collision

When input space is much bigger than the output space, it is very likely we will have Hash Collision

For example, when all the possible keys are all the integers, the output space is just the total number of buckets inside the underlying Array

Use Array to save space & time

When keys are fixed & manageable, we can use the Array index as keys. This will give us constant space and avoid the extra computation used by Hash Function

Info

• Hash Set is another variant
• LeetCode Questions

Time Complexity

• O(1) to Insert
• O(1) to Delete
• O(1) to Search for a value - where the value we want to search is the key

3 ways to iterate

---

1. Key-value pairs

for (Map.Entry<Integer, String> kv: map.entrySet()) {
	System.out.println(kv.getKey() + " -> " + kv.getValue());
}

2. Key

for (int key: map.keySet()) {
	System.out.println(key);
}

3. Value

for (String val: map.values()) {
	System.out.println(val);
}

Terminologies

---

Bucket

• A memory space for the output space of Hash Map that can be used to hold a value