Hash Tables

A Hash Table (Hash Map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Basic Concepts

Hash Function

A hash function is a method that takes a key and converts it into an array index. A good hash function should:

• Be deterministic (same input = same output)
• Distribute values uniformly
• Handle different data types
• Be fast to compute

Collision Handling

When two keys hash to the same index, we have a collision. There are two main ways to handle collisions:

1. Chaining: Store multiple key-value pairs at the same index using a linked list
2. Open Addressing: Find the next empty slot in the array (linear probing, quadratic probing, etc.)

Implementation Example

Here's a complete implementation of a Hash Table using chaining for collision handling:

class HashTable {
	constructor(size = 53) {
		this.keyMap = new Array(size);
	}

	_hash(key) {
		let total = 0;
		let WEIRD_PRIME = 31;
		for (let i = 0; i < Math.min(key.length, 100); i++) {
			let char = key[i];
			let value = char.charCodeAt(0) - 96;
			total = (total * WEIRD_PRIME + value) % this.keyMap.length;
		}
		return total;
	}

	set(key, value) {
		let index = this._hash(key);
		if (!this.keyMap[index]) {
			this.keyMap[index] = [];
		}
		this.keyMap[index].push([key, value]);
		return index;
	}

	get(key) {
		let index = this._hash(key);
		if (this.keyMap[index]) {
			for (let i = 0; i < this.keyMap[index].length; i++) {
				if (this.keyMap[index][i][0] === key) {
					return this.keyMap[index][i][1];
				}
			}
		}
		return undefined;
	}

	keys() {
		let keysArr = [];
		for (let i = 0; i < this.keyMap.length; i++) {
			if (this.keyMap[i]) {
				for (let j = 0; j < this.keyMap[i].length; j++) {
					if (!keysArr.includes(this.keyMap[i][j][0])) {
						keysArr.push(this.keyMap[i][j][0]);
					}
				}
			}
		}
		return keysArr;
	}

	values() {
		let valuesArr = [];
		for (let i = 0; i < this.keyMap.length; i++) {
			if (this.keyMap[i]) {
				for (let j = 0; j < this.keyMap[i].length; j++) {
					if (!valuesArr.includes(this.keyMap[i][j][1])) {
						valuesArr.push(this.keyMap[i][j][1]);
					}
				}
			}
		}
		return valuesArr;
	}
}

Time Complexities

Operation	Average Case	Worst Case
Insert	O(1)	O(n)
Delete	O(1)	O(n)
Search	O(1)	O(n)

Advantages and Disadvantages

Advantages

• Fast lookups (average case O(1))
• Flexible keys (can use strings, numbers, etc.)
• Dynamic size
• Efficient for large datasets

Disadvantages

• Unordered structure
• Possible collisions
• Memory overhead
• Need for a good hash function

Common Use Cases

1. Caching

   • Web browsers
   • Database queries
   • Content Delivery Networks (CDN)

2. Symbol Tables

   • Compiler implementations
   • Language interpreters

3. Database Indexing

   • Quick data retrieval
   • Unique constraints

4. Counting/Frequency Tracking

   • Character frequency
   • Word occurrence
   • Data deduplication

Practice Problems

To master hash tables, try solving these common problems:

1. Implement a hash table from scratch
2. Find first non-repeating character
3. Group anagrams
4. Two sum problem
5. Design a LRU cache

Additional Resources

• JavaScript Algorithms - Hash Table Implementation
• Hash Table Video Tutorial

Visual Representation

A hash table with chaining can be visualized as:

index    buckets
  0  ->  [k,v] -> [k,v]
  1  ->  [k,v]
  2  ->  null
  3  ->  [k,v] -> [k,v] -> [k,v]
  4  ->  [k,v]

Best Practices

1. Choose an appropriate initial size
2. Implement resizing when load factor exceeds threshold
3. Use a good hash function
4. Handle collisions efficiently
5. Consider the trade-off between array size and chain length