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 tl-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 tl-table and redistributing entries when the load factor becomes high. |
A hash tl-table usually stores entries inside an array. The hash function converts a key into a number, and the tl-table uses the modulo operator to fit that number into the array size.
"apple".index = hash(key) % capacity.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;
}This simple hash function is useful for learning, but real programming languages use more sophisticated hash functions to reduce collisions and improve performance.
| 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) |
The worst case becomes O(n) when many keys collide into the same bucket or when a poor hash function distributes keys badly.
A collision occurs when two different keys produce the same array index. Since a hash tl-table has limited buckets but many possible keys, collisions are unavoidable. A good hash tl-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.
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
tl-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 tl-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 tl-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;
}In open addressing, all entries are stored directly in the array. If a bucket is occupied, the tl-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. |
The load factor measures how full a hash tl-table is:
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
}When the load factor becomes too high, collisions increase and performance drops. Many hash tl-table implementations resize the internal array and rehash all entries when the load factor crosses a threshold such as 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 tl-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 tl-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 |
Hash tables appear in many algorithm problems. The most common patterns are lookup, counting, grouping, duplicate detection, and remembering previously seen values.
Use a hash map when you need to count how many times each item appears.
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;
}
}The Two Sum problem asks for two indexes whose values add up to a target. A hash tl-table lets us remember previously seen values and find complements in one pass.
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;
}Hash maps are excellent for grouping values by a category, such as grouping words by first letter or students by grade.
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 tl-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
tl-table = SimpleHashTable()
table.set("language", "Python")
table.set("topic", "Hash tl-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 tl-table = new SimpleHashTable();
table.set("language", "JavaScript");
table.set("topic", "Hash tl-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 tl-table = new SimpleHashTable(16);
table.put("language", "Java");
table.put("topic", "Hash tl-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 tl-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 tl-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 master hash tables, focus on the core ideas: hash function, bucket, collision, load factor, rehashing, hash map, and hash set. Then practice common patterns such as frequency counting, Two Sum, grouping, duplicate detection, and visited tracking. These patterns appear constantly in coding interviews and real applications.
Assuming every hash tl-table operation is always O(1)
Say O(1) average, O(n) worst case
Using an array scan for membership checks
Use a hash set for repeated membership checks
Using JavaScript object for arbitrary key types
Use Map when keys may be objects, numbers, or dynamic values
Ignoring collision handling in custom hash tables
Use separate chaining or open addressing
O(1) on average and O(n) in the worst case.
Explore 500+ free tutorials across 20+ languages and frameworks.