rag/knowledge_base/hash_table.txt

TOPIC: Hash Table

DEFINITION: 
A hash table is a data structure that efficiently stores and retrieves key-value pairs by mapping keys to specific indices of an array using a hash function, allowing for fast lookups and insertions. This solves the problem of quickly finding and accessing specific data in a large collection. It enables constant-time performance for basic operations, making it a fundamental component in many algorithms.

TIME_COMPLEXITY: 
The average time complexity of a hash table is O(1) for search, insert, and delete operations, assuming a good hash function that minimizes collisions. However, in the worst-case scenario where all keys hash to the same index, the time complexity can degrade to O(n), where n is the number of elements in the table.

SPACE_COMPLEXITY: 
The space complexity of a hash table is O(n), where n is the number of key-value pairs stored, as each pair requires a constant amount of space.

USE_WHEN: 
Hash tables are particularly useful when you need to frequently look up, insert, or delete elements in a large dataset, and the keys are unique or can be made unique. They are also useful when memory is not a concern, and fast average-case performance is crucial.

AVOID_WHEN: 
Avoid using hash tables when the order of elements matters, or when the dataset is too large to fit into memory, as this can lead to page faults and slow performance; in such cases, consider using a balanced binary search tree or a disk-based database instead.

EXAMPLE: 
Suppose we have a hash table with 5 slots and we want to insert the following key-value pairs: (apple, 5), (banana, 7), (orange, 3), (grape, 2), (mango, 4). 
  Initially, the table is empty: 
    [ ] [ ] [ ] [ ] [ ]
  We insert (apple, 5) and the hash function maps 'apple' to index 2: 
    [ ] [ ] [(apple, 5)] [ ] [ ]
  Next, we insert (banana, 7) which maps to index 4: 
    [ ] [ ] [(apple, 5)] [ ] [(banana, 7)]
  Then, (orange, 3) maps to index 2, but since it's already occupied, we handle the collision: 
    [ ] [ ] [(apple, 5) -> (orange, 3)] [ ] [(banana, 7)]
  After inserting (grape, 2) to index 1 and (mango, 4) to index 3: 
    [ ] [(grape, 2)] [(apple, 5) -> (orange, 3)] [(mango, 4)] [(banana, 7)]
  The final state of the hash table is as shown above, with some collisions handled 
  Checkmark: 
    The hash table now contains all the inserted key-value pairs, allowing for fast lookup by key.

REAL_WORLD_ANALOGY: 
A hash table is similar to a library's catalog system, where each book is assigned a unique identifier (key) that maps to a specific shelf location (index), allowing for quick retrieval of the book.

SOURCE_NOTE: 
Concepts referenced from general knowledge of data structures and algorithms.