Hashing Introduction
In this page:
What is Hashing
Hashing is a technique for mapping a key, like a string or a number, to a specific position in a table, so that data associated with that key can be stored and found almost instantly.
Example: What is Hashing
#include <iostream>
#include <string>
using namespace std;
int hashFn(string key, int size) {
int sum = 0;
for (char c : key) sum += c;
return sum % size;
}
int main() {
cout << "Index for 'cat': " << hashFn("cat", 10);
return 0;
}public class Main {
static int hashFn(String key, int size) {
int sum = 0;
for (char c : key.toCharArray()) sum += c;
return sum % size;
}
public static void main(String[] args) {
System.out.println("Index for 'cat': " + hashFn("cat", 10));
}
}def hash_fn(key, size):
return sum(ord(c) for c in key) % size
print("Index for 'cat':", hash_fn("cat", 10))#include <stdio.h>
#include <string.h>
int hashFn(char *key, int size) {
int sum = 0;
for (int i = 0; i < strlen(key); i++) sum += key[i];
return sum % size;
}
int main() {
printf("Index for 'cat': %d", hashFn("cat", 10));
return 0;
}Login to try C/C++/Java code in the editor
Hash Function
A hash function takes a key as input and produces an integer index as output, and a good hash function spreads different keys out evenly across the available table positions to minimize collisions.
Example: Hash Function
#include <iostream>
#include <string>
using namespace std;
int hashFn(string key, int size) {
int sum = 0;
for (char c : key) sum += c;
return sum % size;
}
int main() {
string keys[] = {"cat", "dog", "bird"};
for (string k : keys) cout << k << " -> " << hashFn(k, 7) << endl;
return 0;
}public class Main {
static int hashFn(String key, int size) {
int sum = 0;
for (char c : key.toCharArray()) sum += c;
return sum % size;
}
public static void main(String[] args) {
String[] keys = {"cat", "dog", "bird"};
for (String k : keys) System.out.println(k + " -> " + hashFn(k, 7));
}
}def hash_fn(key, size):
return sum(ord(c) for c in key) % size
for k in ("cat", "dog", "bird"):
print(k, "->", hash_fn(k, 7))#include <stdio.h>
#include <string.h>
int hashFn(char *key, int size) {
int sum = 0;
for (int i = 0; i < strlen(key); i++) sum += key[i];
return sum % size;
}
int main() {
char *keys[] = {"cat", "dog", "bird"};
for (int i = 0; i < 3; i++) printf("%s -> %d\n", keys[i], hashFn(keys[i], 7));
return 0;
}Login to try C/C++/Java code in the editor
Hash Table
A hash table is the data structure that actually stores values at the positions their keys hash to, combining an array with a hash function to give it fast, index-like access using arbitrary keys instead of just numbers.
Example: Hash Table
#include <iostream>
#include <string>
using namespace std;
int main() {
string table[10] = {};
int idx = 3;
table[idx] = "apple";
cout << "Stored at index " << idx << ": " << table[idx];
return 0;
}public class Main {
public static void main(String[] args) {
String[] table = new String[10];
int idx = 3;
table[idx] = "apple";
System.out.println("Stored at index " + idx + ": " + table[idx]);
}
}table = [None] * 10
idx = 3
table[idx] = "apple"
print("Stored at index", idx, ":", table[idx])#include <stdio.h>
int main() {
char *table[10] = {0};
int idx = 3;
table[idx] = "apple";
printf("Stored at index %d: %s", idx, table[idx]);
return 0;
}Login to try C/C++/Java code in the editor
Hashing Benefits
Because a hash function computes an index directly instead of searching through data, hashing gives average-case O(1) lookup, insertion, and deletion, dramatically faster than the O(n) search a plain list would need.
Example: Hashing Benefits
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> m;
m["apple"] = 5;
cout << "Direct hash lookup: " << m["apple"] << " (no scanning needed)";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
HashMap<String, Integer> m = new HashMap<>();
m.put("apple", 5);
System.out.println("Direct hash lookup: " + m.get("apple") + " (no scanning needed)");
}
}m = {"apple": 5}
print("Direct hash lookup:", m["apple"], "(no scanning needed)")#include <stdio.h>
int main() {
printf("Direct hash lookup: 5 (no scanning needed)");
return 0;
}Login to try C/C++/Java code in the editor
Hashing Uses
Hashing underlies hash maps and hash sets directly, and shows up indirectly all over computing, including caches, databases, password storage, and detecting duplicates efficiently in large datasets.
Example: Hashing Uses
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 2, 4, 1};
unordered_set<int> seen;
for (int x : arr) {
if (seen.count(x)) cout << "Duplicate found: " << x << endl;
seen.insert(x);
}
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 4, 1};
Set<Integer> seen = new HashSet<>();
for (int x : arr) {
if (seen.contains(x)) System.out.println("Duplicate found: " + x);
seen.add(x);
}
}
}arr = [1, 2, 3, 2, 4, 1]
seen = set()
for x in arr:
if x in seen:
print("Duplicate found:", x)
seen.add(x)#include <stdio.h>
int main() {
int arr[] = {1, 2, 3, 2, 4, 1};
int seen[10] = {0};
for (int i = 0; i < 6; i++) {
if (seen[arr[i]]) printf("Duplicate found: %d\n", arr[i]);
seen[arr[i]] = 1;
}
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: