A hash table is an efficient data storage and retrieval structure that uses a hash function to map keys to positions in the table for accessing records, enabling fast data access. Hash tables have wide applications in computer science, such as database indexing, cache implementation, dictionaries, etc.
Basic Concepts of Hash Tables
- Key-Value Pair: The basic unit stored in a hash table, where each key corresponds to a value
- Hash Function: A function that maps keys to array indices
- Collision: The situation where different keys are mapped to the same index by the hash function
- Load Factor: The proportion of filled positions in the hash table, which affects performance
Hash Table Implementations
Array-Based Hash Table Implementation
class HashTable {
constructor(size = 32) {
this.size = size;
this.buckets = new Array(size).fill(null).map(() => []);
}
// Hash function
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.size;
}
return hash;
}
// Set key-value pair
set(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
// Check if the same key already exists
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value; // Update value
return;
}
}
// Add new key-value pair
bucket.push([key, value]);
}
// Get value
get(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket[i][1];
}
}
return undefined; // Key does not exist
}
// Delete key-value pair
remove(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
return true;
}
}
return false; // Key does not exist
}
// Check if key exists
has(key) {
return this.get(key) !== undefined;
}
// Get all keys
keys() {
const keys = [];
for (const bucket of this.buckets) {
for (const [key, value] of bucket) {
keys.push(key);
}
}
return keys;
}
// Get all values
values() {
const values = [];
for (const bucket of this.buckets) {
for (const [key, value] of bucket) {
values.push(value);
}
}
return values;
}
// Get the number of key-value pairs
size() {
let count = 0;
for (const bucket of this.buckets) {
count += bucket.length;
}
return count;
}
}
// Usage example
const hashTable = new HashTable();
hashTable.set('name', 'Alice');
hashTable.set('age', 25);
hashTable.set('job', 'Developer');
console.log(hashTable.get('name')); // Alice
console.log(hashTable.has('age')); // true
console.log(hashTable.keys()); // ['name', 'age', 'job'] (order may vary)
console.log(hashTable.size()); // 3
hashTable.remove('age');
console.log(hashTable.size()); // 2
Linked List-Based Hash Table Implementation (Separate Chaining)
class HashNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}
class LinkedHashTable {
constructor(size = 32) {
this.size = size;
this.buckets = new Array(size).fill(null);
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.size;
}
return hash;
}
set(key, value) {
const index = this.hash(key);
let head = this.buckets[index];
if (!head) {
this.buckets[index] = new HashNode(key, value);
return;
}
let current = head;
while (current) {
if (current.key === key) {
current.value = value;
return;
}
if (!current.next) {
current.next = new HashNode(key, value);
return;
}
current = current.next;
}
}
get(key) {
const index = this.hash(key);
let current = this.buckets[index];
while (current) {
if (current.key === key) {
return current.value;
}
current = current.next;
}
return undefined;
}
remove(key) {
const index = this.hash(key);
let current = this.buckets[index];
let previous = null;
while (current) {
if (current.key === key) {
if (previous) {
previous.next = current.next;
} else {
this.buckets[index] = current.next;
}
return true;
}
previous = current;
current = current.next;
}
return false;
}
has(key) {
return this.get(key) !== undefined;
}
}
// Usage example
const linkedHash = new LinkedHashTable();
linkedHash.set('key1', 'value1');
linkedHash.set('key2', 'value2');
console.log(linkedHash.get('key1')); // value1
linkedHash.remove('key1');
console.log(linkedHash.has('key1')); // false
Open Addressing Hash Table Implementation (Linear Probing)
class OpenHashTable {
constructor(size = 32) {
this.size = size;
this.buckets = new Array(size).fill(null);
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.size;
}
return hash;
}
set(key, value) {
let index = this.hash(key);
while (this.buckets[index] !== null && this.buckets[index].key !== key) {
index = (index + 1) % this.size; // Linear probing
}
if (this.buckets[index] === null) {
this.buckets[index] = { key, value };
} else {
this.buckets[index].value = value;
}
}
get(key) {
let index = this.hash(key);
let startIndex = index;
while (this.buckets[index] !== null) {
if (this.buckets[index].key === key) {
return this.buckets[index].value;
}
index = (index + 1) % this.size;
if (index === startIndex) break; // Avoid infinite loop
}
return undefined;
}
remove(key) {
let index = this.hash(key);
let startIndex = index;
while (this.buckets[index] !== null) {
if (this.buckets[index].key === key) {
this.buckets[index] = null;
return true;
}
index = (index + 1) % this.size;
if (index === startIndex) break;
}
return false;
}
has(key) {
return this.get(key) !== undefined;
}
}
// Usage example
const openHash = new OpenHashTable();
openHash.set('a', 1);
openHash.set('b', 2);
console.log(openHash.get('a')); // 1
openHash.remove('a');
console.log(openHash.has('a')); // false
Collision Resolution Strategies
Separate Chaining
- Use linked lists or arrays at each bucket to store multiple key-value pairs
- Advantages: Simple, easy to handle large numbers of collisions
- Disadvantages: Additional memory for links, potential cache misses
Open Addressing
- Linear Probing: Search sequentially for the next available slot
- Quadratic Probing: Use quadratic function to probe
- Double Hashing: Use a second hash function for probing
- Advantages: Better cache performance, no extra memory for links
- Disadvantages: Clustering issues, more complex deletion
Hash Function Design
A good hash function should:
- Be fast to compute
- Produce uniform distribution
- Minimize collisions
- Be deterministic
Common hash functions in JavaScript:
- Simple string hash:
function simpleHash(key, size) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % size;
}
- djb2 hash function:
function djb2(key) {
let hash = 5381;
for (let i = 0; i < key.length; i++) {
hash = ((hash << 5) + hash) + key.charCodeAt(i);
}
return hash >>> 0; // Convert to unsigned 32-bit integer
}
- MurmurHash (advanced, requires implementation)
Dynamic Resizing
When load factor exceeds a threshold (e.g., 0.75), resize the hash table:
class ResizableHashTable extends HashTable {
constructor(size = 32, loadFactor = 0.75) {
super(size);
this.loadFactor = loadFactor;
}
set(key, value) {
super.set(key, value);
if (this.size() / this.size > this.loadFactor) {
this.resize();
}
}
resize() {
const oldBuckets = this.buckets;
this.size *= 2;
this.buckets = new Array(this.size).fill(null).map(() => []);
for (const bucket of oldBuckets) {
for (const [key, value] of bucket) {
this.set(key, value);
}
}
}
}
Hash Table Applications
Caching (LRU Cache)
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new HashTable(); // For O(1) access
this.order = []; // To track access order
}
get(key) {
if (!this.cache.has(key)) return -1;
// Update access order
this.order.splice(this.order.indexOf(key), 1);
this.order.push(key);
return this.cache.get(key);
}
put(key, value) {
if (this.cache.has(key)) {
// Update value and order
this.cache.set(key, value);
this.order.splice(this.order.indexOf(key), 1);
this.order.push(key);
} else {
if (this.order.length >= this.capacity) {
// Remove least recently used
const lruKey = this.order.shift();
this.cache.remove(lruKey);
}
this.cache.set(key, value);
this.order.push(key);
}
}
}
// Usage example
const cache = new LRUCache(2);
cache.put('a', 1);
cache.put('b', 2);
console.log(cache.get('a')); // 1
cache.put('c', 3); // Removes 'b'
console.log(cache.get('b')); // -1
Frequency Statistics
function countWordFrequency(text) {
const words = text.split(/\s+/);
const frequency = new Dictionary();
for (const word of words) {
if (frequency.has(word)) {
frequency.set(word, frequency.get(word) + 1);
} else {
frequency.set(word, 1);
}
}
return frequency;
}
// Usage example
const text = "hello world hello javascript";
const freq = countWordFrequency(text);
console.log(freq.keys()); // ["hello", "world", "javascript"]
console.log(freq.get("hello")); // 2
Fast Lookup of Object Properties
function createFastLookup(obj) {
const lookup = new Dictionary();
for (const key in obj) {
if (obj.hasOwnProperty(key)) {
lookup.set(key, obj[key]);
}
}
return {
get: (key) => lookup.get(key),
has: (key) => lookup.has(key)
};
}
// Usage example
const person = { name: 'Alice', age: 25, job: 'Developer' };
const fastLookup = createFastLookup(person);
console.log(fastLookup.get('name')); // Alice
console.log(fastLookup.has('age')); // true
Comparison of Hash Tables with Other Data Structures
| Feature | Hash Table | Array | Linked List | Binary Search Tree |
|---|---|---|---|---|
| Insertion | O(1) average | O(n) | O(1) | O(log n) average |
| Lookup | O(1) average | O(log n) after sorting | O(n) | O(log n) average |
| Deletion | O(1) average | O(n) | O(1) | O(log n) average |
| Sequential Access | Not supported | O(1) | O(n) | In-order traversal O(n) |
| Key-Value Storage | Supported | Not supported | Possible but inefficient | Possible but inefficient |
Optimization Techniques for Hash Tables
- Good Hash Function:
- Uniform distribution
- Fast computation
- Reduce collisions
- Dynamic Resizing:
- Resize when load factor exceeds threshold
- Usually double the size
- Collision Resolution Strategy Selection:
- Separate chaining suitable for most cases
- Open addressing suitable for memory-constrained scenarios
- Cache Friendliness:
- Consider data locality
- Reduce pointer jumps
- Concurrency Control:
- For multi-threaded environments, consider locking or using concurrent hash tables
Practical Application Scenarios
- Database Indexing: Fast record lookup
- Caching Systems: Such as Redis, Memcached
- Compiler Symbol Tables: Store variable and function information
- Routing Tables: Store IP to MAC address mappings in network devices
- Object Property Storage: Internal implementation in JavaScript engines
- Counters: Count element frequencies
- Sets Implementation: Fast lookup and deduplication
Summary
Hash tables are an extremely efficient data structure, particularly suitable for scenarios requiring fast lookup, insertion, and deletion. Understanding the working principles of hash tables, collision resolution strategies, and performance optimization techniques is crucial for developing high-performance applications. In practical development, although we usually use language-built-in Maps or objects to implement similar functionality, a deep understanding of the underlying implementation of hash tables helps us better use these tools and implement customized hash table structures when necessary.



