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
• Decide if a key is inside the collection quickly
• We are using space in exchange for better performance
• Hash Set is another variant
• LeetCode Questions

Hash Collision

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

Complexity

---

Time

• 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

Tips

---

Use Array to save space

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

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