Hash Table HashMap, HashSet, Collision Handling is an important Data Structure topic because it shows up in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
Focus on what problem Hash Table HashMap, HashSet, Collision Handling solves, where developers usually make mistakes, and how to verify the result with output, behavior, or a small test.
A strong understanding of Hash Table HashMap, HashSet, Collision Handling should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work.
Hash Table HashMap HashSet Collision Handling should be studied as a practical Data Structure lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the data-structure > hash-table page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
A hash table is a data structure that stores data as key-value pairs. It uses a hash function to convert a key into an array index, so values can be inserted, searched, updated, and deleted very quickly.
Hash tables are also known as hash maps, maps, dictionaries, or associative arrays, depending on the programming language. They are one of the most important data structures in computer science because many real-world problems require fast lookup by key.
Suppose you have a list of student records and want to find a student by roll number. With an array, you may need to scan many records one by one. With a hash table, the roll number becomes the key, and the hash table can usually jump directly to the correct storage location.
| Problem | Without Hash Table | With Hash Table |
|---|---|---|
| Find user by ID | Scan list: O(n) | Lookup by key: average O(1) |
| Count word frequency | Repeated searching | Update count by word key |
| Remove duplicates | Compare many pairs | Track seen values in a set |
| Check membership | Search array | Use hash set lookup |
| Term | Meaning |
|---|---|
| Key | The identifier used to store and retrieve a value, such as "email" or 101. |
| Value | The data associated with a key. |
| Hash function | A function that converts a key into a numeric hash code. |
| Bucket / Slot | A position in the internal array where entries are stored. |
| Collision | When two different keys map to the same bucket. |
| Load factor | The ratio of stored entries to bucket count: items / capacity. |
| Rehashing | Growing the table and redistributing entries when the load factor becomes high. |
A hash table usually stores entries inside an array. The hash function converts a key into a number, and the table uses the modulo operator to fit that number into the array size.
This simple hash function is useful for learning, but real programming languages use more sophisticated hash functions to reduce collisions and improve performance.
function hashString(key, capacity) {
let hash = 0;
for (const char of key) {
hash += char.charCodeAt(0);
}
return hash % capacity;
}
console.log(hashString("apple", 10)); // example index
console.log(hashString("banana", 10)); // example indexdef hash_string(key, capacity):
total = 0
for char in key:
total += ord(char)
return total % capacity
print(hash_string("apple", 10))
print(hash_string("banana", 10))public class SimpleHashFunction {
static int hashString(String key, int capacity) {
int hash = 0;
for (char ch : key.toCharArray()) {
hash += ch;
}
return hash % capacity;
}
public static void main(String[] args) {
System.out.println(hashString("apple", 10));
System.out.println(hashString("banana", 10));
}
}#include <iostream>
#include <string>
using namespace std;
int hashString(const string& key, int capacity) {
int hash = 0;
for (char ch : key) {
hash += ch;
}
return hash % capacity;
}
int main() {
cout << hashString("apple", 10) << endl;
cout << hashString("banana", 10) << endl;
}The worst case becomes O(n) when many keys collide into the same bucket or when a poor hash function distributes keys badly.
| Operation | Meaning | Average Time | Worst Time |
|---|---|---|---|
| Insert / Put | Add or update a key-value pair | O(1) | O(n) |
| Search / Get | Find value by key | O(1) | O(n) |
| Delete / Remove | Remove entry by key | O(1) | O(n) |
| Contains | Check if a key exists | O(1) | O(n) |
| Iteration | Visit all entries | O(n) | O(n) |
A collision occurs when two different keys produce the same array index. Since a hash table has limited buckets but many possible keys, collisions are unavoidable. A good hash table does not prevent all collisions; it handles them efficiently.
In separate chaining, each bucket stores a list of entries. If multiple keys map to the same bucket, all of them are kept in that bucket's list.
In open addressing, all entries are stored directly in the array. If a bucket is occupied, the table probes for another available slot. Common probing methods include linear probing, quadratic probing, and double hashing.
| Technique | How It Works | Note |
|---|---|---|
| Linear probing | Try next slot: index + 1, index + 2, ... | Simple, but can create clusters. |
| Quadratic probing | Try slots using squared jumps. | Reduces clustering compared with linear probing. |
| Double hashing | Use a second hash function for step size. | Usually distributes probes better. |
class HashTable:
def __init__(self, size=10):
self.buckets = [[] for _ in range(size)]
def hash(self, key):
hash_value = 0
for char in key:
hash_value = (hash_value * 31 + ord(char)) % len(self.buckets)
return hash_value
def set(self, key, value):
index = self.hash(key)
bucket = self.buckets[index]
for entry in bucket:
if entry[0] == key:
entry[1] = value
return
bucket.append([key, value])
def get(self, key):
index = self.hash(key)
bucket = self.buckets[index]
for stored_key, value in bucket:
if stored_key == key:
return value
return None
table = HashTable()
table.set("name", "Asha")
table.set("role", "Developer")
print(table.get("name")) # Ashaclass HashTable {
constructor(size = 10) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let hash = 0;
for (const char of key) {
hash = (hash * 31 + char.charCodeAt(0)) % this.buckets.length;
}
return hash;
}
set(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (const entry of bucket) {
if (entry.key === key) {
entry.value = value;
return;
}
}
bucket.push({ key, value });
}
get(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (const entry of bucket) {
if (entry.key === key) {
return entry.value;
}
}
return undefined;
}
}
const table = new HashTable();
table.set("name", "Asha");
table.set("role", "Developer");
console.log(table.get("name")); // Ashaimport java.util.*;
class HashTable {
private List<Entry>[] buckets;
static class Entry {
String key;
String value;
Entry(String key, String value) {
this.key = key;
this.value = value;
}
}
@SuppressWarnings("unchecked")
HashTable(int size) {
buckets = new ArrayList[size];
for (int i = 0; i < size; i++) {
buckets[i] = new ArrayList<>();
}
}
private int hash(String key) {
int hash = 0;
for (char ch : key.toCharArray()) {
hash = (hash * 31 + ch) % buckets.length;
}
return hash;
}
void put(String key, String value) {
List<Entry> bucket = buckets[hash(key)];
for (Entry entry : bucket) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
bucket.add(new Entry(key, value));
}
String get(String key) {
for (Entry entry : buckets[hash(key)]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
public static void main(String[] args) {
HashTable table = new HashTable(10);
table.put("name", "Asha");
table.put("role", "Developer");
System.out.println(table.get("name"));
}
}#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;
class HashTable {
vector<list<pair<string, string>>> buckets;
int hashKey(const string& key) {
int hash = 0;
for (char ch : key) {
hash = (hash * 31 + ch) % buckets.size();
}
return hash;
}
public:
HashTable(int size = 10) : buckets(size) {}
void put(const string& key, const string& value) {
int index = hashKey(key);
for (auto& entry : buckets[index]) {
if (entry.first == key) {
entry.second = value;
return;
}
}
buckets[index].push_back({key, value});
}
string get(const string& key) {
int index = hashKey(key);
for (auto& entry : buckets[index]) {
if (entry.first == key) {
return entry.second;
}
}
return "";
}
};
int main() {
HashTable table;
table.put("name", "Asha");
table.put("role", "Developer");
cout << table.get("name") << endl;
}The load factor measures how full a hash table is:
When the load factor becomes too high, collisions increase and performance drops. Many hash table implementations resize the internal array and rehash all entries when the load factor crosses a threshold such as 0.75.
number_of_items = 12
number_of_buckets = 16
load_factor = number_of_items / number_of_buckets
print(load_factor) # 0.75const numberOfItems = 12;
const numberOfBuckets = 16;
const loadFactor = numberOfItems / numberOfBuckets;
console.log(loadFactor); // 0.75public class LoadFactor {
public static void main(String[] args) {
double numberOfItems = 12;
double numberOfBuckets = 16;
double loadFactor = numberOfItems / numberOfBuckets;
System.out.println(loadFactor); // 0.75
}
}#include <iostream>
using namespace std;
int main() {
double numberOfItems = 12;
double numberOfBuckets = 16;
double loadFactor = numberOfItems / numberOfBuckets;
cout << loadFactor << endl; // 0.75
}A hash map stores key-value pairs. A hash set stores only unique keys. Internally, a hash set is often implemented using a hash table where only the key matters.
| Structure | Stores | Use Case |
|---|---|---|
| Hash Map | Key-value pairs | Frequency count, cache, user lookup, indexes |
| Hash Set | Unique keys only | Duplicate detection, membership checking, visited tracking |
# Hash map: key -> value
scores = {"Asha": 95, "Rohan": 88}
print(scores["Asha"])
# Hash set: unique values
seen = {"apple", "banana", "apple"}
print(seen) # {"apple", "banana"}// Hash map
const scores = new Map();
scores.set("Asha", 95);
scores.set("Rohan", 88);
// Hash set
const seen = new Set(["apple", "banana", "apple"]);
console.log([...seen]); // ["apple", "banana"]import java.util.*;
public class MapVsSet {
public static void main(String[] args) {
// Hash map: key -> value
HashMap<String, Integer> scores = new HashMap<>();
scores.put("Asha", 95);
scores.put("Rohan", 88);
System.out.println(scores.get("Asha"));
// Hash set: unique values
HashSet<String> seen = new HashSet<>();
seen.add("apple");
seen.add("banana");
seen.add("apple");
System.out.println(seen);
}
}#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
// Hash map: key -> value
unordered_map<string, int> scores;
scores["Asha"] = 95;
scores["Rohan"] = 88;
cout << scores["Asha"] << endl;
// Hash set: unique values
unordered_set<string> seen = {"apple", "banana", "apple"};
cout << seen.size() << endl; // 2
}Most languages provide built-in hash table structures. In interviews and real projects, you usually use these built-ins instead of implementing your own from scratch.
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
unordered_map<string, int> scores;
scores["Asha"] = 95;
scores["Rohan"] = 88;
if (scores.count("Asha")) {
cout << scores["Asha"] << endl;
}
unordered_set<int> visited;
visited.insert(10);
visited.insert(20);
cout << visited.count(10) << endl;
}import java.util.*;
public class HashTableDemo {
public static void main(String[] args) {
HashMap<String, Integer> scores = new HashMap<>();
scores.put("Asha", 95);
scores.put("Rohan", 88);
System.out.println(scores.getOrDefault("Asha", 0));
System.out.println(scores.containsKey("Meera"));
HashSet<Integer> visited = new HashSet<>();
visited.add(10);
visited.add(20);
System.out.println(visited.contains(10));
}
}scores = {
"Asha": 95,
"Rohan": 88
}
print(scores.get("Asha", 0))
print("Meera" in scores)
visited = set()
visited.add(10)
visited.add(20)
print(10 in visited)const scores = new Map();
scores.set("Asha", 95);
scores.set("Rohan", 88);
console.log(scores.get("Asha"));
console.log(scores.has("Meera"));
const visited = new Set();
visited.add(10);
visited.add(20);
console.log(visited.has(10));In JavaScript, both objects and Map can store key-value pairs, but they are not the same. Use Map when you need a general-purpose hash map. Use plain objects when you are modeling structured data with known property names.
| Feature | Object | Map |
|---|---|---|
| Key types | String or symbol keys | Any key type |
| Size | Object.keys(obj).length | map.size |
| Iteration | Needs helper methods | Directly iterable |
| Use case | Records and structured objects | Dynamic key-value storage |
A hash table turns a key into a bucket index so the program can find values without scanning the whole collection. That design makes it ideal for direct lookup, counting repeated items, and checking whether something has been seen before.
Use a hash map when you need to count how many times each item appears.
The Two Sum problem asks for two indexes whose values add up to a target. A hash table lets us remember previously seen values and find complements in one pass.
Hash maps are excellent for grouping values by a category, such as grouping words by first letter or students by grade.
def frequency_count(items):
freq = {}
for item in items:
freq[item] = freq.get(item, 0) + 1
return freq
print(frequency_count(["a", "b", "a", "c", "b", "a"]))
# {'a': 3, 'b': 2, 'c': 1}function frequencyCount(items) {
const freq = new Map();
for (const item of items) {
freq.set(item, (freq.get(item) || 0) + 1);
}
return freq;
}
console.log([...frequencyCount(["a", "b", "a", "c", "b", "a"])]);import java.util.*;
public class FrequencyCount {
static Map<String, Integer> frequencyCount(String[] items) {
Map<String, Integer> freq = new HashMap<>();
for (String item : items) {
freq.put(item, freq.getOrDefault(item, 0) + 1);
}
return freq;
}
public static void main(String[] args) {
String[] items = {"a", "b", "a", "c", "b", "a"};
System.out.println(frequencyCount(items));
}
}#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<string, int> frequencyCount(const vector<string>& items) {
unordered_map<string, int> freq;
for (const string& item : items) {
freq[item]++;
}
return freq;
}
int main() {
vector<string> items = {"a", "b", "a", "c", "b", "a"};
auto freq = frequencyCount(items);
for (auto& [item, count] : freq) {
cout << item << ": " << count << endl;
}
}def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) {
return [seen.get(need), i];
}
seen.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]import java.util.*;
public class TwoSum {
static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) {
return new int[] { seen.get(need), i };
}
seen.put(nums[i], i);
}
return new int[] {};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[] {2, 7, 11, 15}, 9)));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < nums.size(); i++) {
int need = target - nums[i];
if (seen.count(need)) {
return {seen[need], i};
}
seen[nums[i]] = i;
}
return {};
}
int main() {
vector<int> nums = {2, 7, 11, 15};
vector<int> result = twoSum(nums, 9);
cout << result[0] << ", " << result[1] << endl;
}def group_by_first_letter(words):
groups = {}
for word in words:
key = word[0]
if key not in groups:
groups[key] = []
groups[key].append(word)
return groups
print(group_by_first_letter(["apple", "ant", "bat", "ball"]))
# {'a': ['apple', 'ant'], 'b': ['bat', 'ball']}function groupByFirstLetter(words) {
const groups = new Map();
for (const word of words) {
const key = word[0];
if (!groups.has(key)) {
groups.set(key, []);
}
groups.get(key).push(word);
}
return groups;
}
console.log([...groupByFirstLetter(["apple", "ant", "bat", "ball"])]);import java.util.*;
public class GroupWords {
static Map<Character, List<String>> groupByFirstLetter(String[] words) {
Map<Character, List<String>> groups = new HashMap<>();
for (String word : words) {
char key = word.charAt(0);
groups.putIfAbsent(key, new ArrayList<>());
groups.get(key).add(word);
}
return groups;
}
public static void main(String[] args) {
String[] words = {"apple", "ant", "bat", "ball"};
System.out.println(groupByFirstLetter(words));
}
}#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<char, vector<string>> groupByFirstLetter(vector<string>& words) {
unordered_map<char, vector<string>> groups;
for (const string& word : words) {
char key = word[0];
groups[key].push_back(word);
}
return groups;
}
int main() {
vector<string> words = {"apple", "ant", "bat", "ball"};
auto groups = groupByFirstLetter(words);
for (auto& [letter, items] : groups) {
cout << letter << ": ";
for (const string& word : items) {
cout << word << " ";
}
cout << endl;
}
}A basic hash table implementation helps you understand how built-in maps work internally. The example below uses separate chaining and supports set, get, has, and delete.
class SimpleHashTable:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def hash(self, key):
text = str(key)
hash_value = 0
for char in text:
hash_value = (hash_value * 31 + ord(char)) % self.capacity
return hash_value
def set(self, key, value):
bucket = self.buckets[self.hash(key)]
for entry in bucket:
if entry[0] == key:
entry[1] = value
return
bucket.append([key, value])
self.size += 1
def get(self, key):
bucket = self.buckets[self.hash(key)]
for stored_key, value in bucket:
if stored_key == key:
return value
return None
def has(self, key):
return self.get(key) is not None
def delete(self, key):
bucket = self.buckets[self.hash(key)]
for index, entry in enumerate(bucket):
if entry[0] == key:
bucket.pop(index)
self.size -= 1
return True
return False
table = SimpleHashTable()
table.set("language", "Python")
table.set("topic", "Hash table")
print(table.get("language")) # Python
print(table.has("topic")) # True
table.delete("topic")
print(table.size) # 1class SimpleHashTable {
constructor(capacity = 16) {
this.capacity = capacity;
this.size = 0;
this.buckets = Array.from({ length: capacity }, () => []);
}
hash(key) {
const text = String(key);
let hash = 0;
for (const char of text) {
hash = (hash * 31 + char.charCodeAt(0)) % this.capacity;
}
return hash;
}
set(key, value) {
const bucket = this.buckets[this.hash(key)];
for (const entry of bucket) {
if (entry.key === key) {
entry.value = value;
return;
}
}
bucket.push({ key, value });
this.size++;
}
get(key) {
const bucket = this.buckets[this.hash(key)];
const entry = bucket.find(item => item.key === key);
return entry?.value;
}
has(key) {
return this.get(key) !== undefined;
}
delete(key) {
const bucket = this.buckets[this.hash(key)];
const index = bucket.findIndex(item => item.key === key);
if (index === -1) {
return false;
}
bucket.splice(index, 1);
this.size--;
return true;
}
}
const table = new SimpleHashTable();
table.set("language", "JavaScript");
table.set("topic", "Hash table");
console.log(table.get("language")); // JavaScript
console.log(table.has("topic")); // true
table.delete("topic");
console.log(table.size); // 1import java.util.*;
class SimpleHashTable {
private final List<Entry>[] buckets;
private int size = 0;
static class Entry {
String key;
String value;
Entry(String key, String value) {
this.key = key;
this.value = value;
}
}
@SuppressWarnings("unchecked")
SimpleHashTable(int capacity) {
buckets = new ArrayList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new ArrayList<>();
}
}
private int hash(String key) {
int hash = 0;
for (char ch : key.toCharArray()) {
hash = (hash * 31 + ch) % buckets.length;
}
return hash;
}
void put(String key, String value) {
List<Entry> bucket = buckets[hash(key)];
for (Entry entry : bucket) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
bucket.add(new Entry(key, value));
size++;
}
String get(String key) {
for (Entry entry : buckets[hash(key)]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
boolean has(String key) {
return get(key) != null;
}
boolean delete(String key) {
List<Entry> bucket = buckets[hash(key)];
for (int i = 0; i < bucket.size(); i++) {
if (bucket.get(i).key.equals(key)) {
bucket.remove(i);
size--;
return true;
}
}
return false;
}
int size() {
return size;
}
public static void main(String[] args) {
SimpleHashTable table = new SimpleHashTable(16);
table.put("language", "Java");
table.put("topic", "Hash table");
System.out.println(table.get("language"));
System.out.println(table.has("topic"));
table.delete("topic");
System.out.println(table.size());
}
}#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;
class SimpleHashTable {
vector<list<pair<string, string>>> buckets;
int itemCount = 0;
int hashKey(const string& key) {
int hash = 0;
for (char ch : key) {
hash = (hash * 31 + ch) % buckets.size();
}
return hash;
}
public:
SimpleHashTable(int capacity = 16) : buckets(capacity) {}
void put(const string& key, const string& value) {
int index = hashKey(key);
for (auto& entry : buckets[index]) {
if (entry.first == key) {
entry.second = value;
return;
}
}
buckets[index].push_back({key, value});
itemCount++;
}
string get(const string& key) {
int index = hashKey(key);
for (auto& entry : buckets[index]) {
if (entry.first == key) {
return entry.second;
}
}
return "";
}
bool has(const string& key) {
return get(key) != "";
}
bool remove(const string& key) {
int index = hashKey(key);
for (auto it = buckets[index].begin(); it != buckets[index].end(); ++it) {
if (it->first == key) {
buckets[index].erase(it);
itemCount--;
return true;
}
}
return false;
}
int size() {
return itemCount;
}
};
int main() {
SimpleHashTable table;
table.put("language", "C++");
table.put("topic", "Hash table");
cout << table.get("language") << endl;
cout << table.has("topic") << endl;
table.remove("topic");
cout << table.size() << endl;
}| Advantages | Disadvantages |
|---|---|
| Very fast average lookup, insert, and delete. | Worst-case time can become O(n). |
| Excellent for key-based search and membership checking. | Does not naturally maintain sorted order. |
| Useful for counting, grouping, caching, and indexing. | Requires extra memory for buckets and resizing. |
| Available as built-in structures in most languages. | Performance depends on hash function quality and load factor. |
A hash table is one of the most practical data structures because it provides fast average-case search, insertion, and deletion. It works by hashing keys into array indexes, then resolving collisions when multiple keys land in the same bucket.
To understand hash tables well, follow the full chain from hash function to bucket selection to collision handling. The practical questions are how many items fit before resizing, what happens when two keys land in the same slot, and when a hash map is better than a hash set.
1. Define the input for Hash Table HashMap HashSet Collision Handling.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.1. Try empty, missing, duplicate, or invalid data.
2. Identify where Hash Table HashMap HashSet Collision Handling changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing Hash Table HashMap HashSet Collision Handling without the situation where it is useful.
Connect Hash Table HashMap HashSet Collision Handling to a concrete Data Structure task.
Testing Hash Table HashMap HashSet Collision Handling only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to Hash Table HashMap HashSet Collision Handling.
Memorizing Hash Table HashMap HashSet Collision Handling without the situation where it is useful.
Connect Hash Table HashMap HashSet Collision Handling to a concrete Data Structure task.
A hash table is the general data structure. A hash map is a common key-value implementation of a hash table. In many discussions, the terms are used almost interchangeably.
The hash function computes the bucket index directly from the key, so the table usually checks only a small number of entries instead of scanning all data.
If many keys collide into the same bucket, the table may need to search through many entries in that bucket. In the extreme case, all keys collide and lookup becomes linear.
Usually no. Hash tables are designed for fast lookup, not sorted ordering. Use a balanced tree, heap, or sorted array if order matters.
Explore 500+ free tutorials across 20+ languages and frameworks.