Overview

A Hash Table (or Hash Map/Dictionary) is a data structure that maps keys to values using a hash function. It allows for extremely fast data retrieval by converting a key into an index in an underlying array.

Core Concepts

• Hash Function: An algorithm that takes an input (key) and returns a fixed-size integer (hash), which determines the index where the value is stored.
• Collision: Occurs when two different keys produce the same hash index.
• Collision Resolution Strategies:
  • Chaining: Each index in the array points to a linked list of all elements that hashed to that index.
  • Open Addressing: Searching for the next empty slot in the array (e.g., Linear Probing).
• Time Complexity:
  • Insertion: $O(1)$ average / $O(n)$ worst case.
  • Deletion: $O(1)$ average / $O(n)$ worst case.
  • Lookup: $O(1)$ average / $O(n)$ worst case.

Code Examples

// In JavaScript/TypeScript, the 'Map' object is a built-in Hash Table
const userEmails = new Map<number, string>();

userEmails.set(101, "alice@example.com");
userEmails.set(102, "bob@example.com");

console.log(userEmails.get(101)); // "alice@example.com"
console.log(userEmails.has(103)); // false

Use Cases

• Database Indexing: Quickly finding a record by its primary key.
• Caching: Storing the results of expensive computations (Memoization).
• Unique Element Tracking: Using a Set (which is usually a Hash Table without values) to ensure no duplicates in a list.

Gotchas

• Poor Hash Functions: If a hash function produces too many collisions, performance degrades from $O(1)$ to $O(n)$.
• Load Factor: As the table fills up, the chance of collisions increases. Hash tables must be “resized” (rehashing all elements into a larger array) to maintain performance.
• Unordered: Hash tables do not maintain the insertion order of elements (though some language implementations, like JS Maps, do).

Related Notes

• Array
• Linked List
• Big O Notation