Hash Tables Lecture Notes

Jun 6, 2024

Hash Tables Lecture Notes

Introduction to Hash Tables

  • Hash Tables: A data structure that stores key-value pairs.
    • Handles collisions when multiple keys hash to the same value.

Types of Hash Tables

Separate Chaining

  • Uses linked lists to handle collisions within the same hash bucket (list).

Open Addressing

  • Finds another open slot within the table to insert the key-value pair when collisions occur.

Example: Implementing a Phonebook with Separate Chaining

  • Keys: Integers (e.g., phone numbers)
  • Values: Strings (e.g., names)

Initial Setup

  • Constant Amount of Lists: Set to 10
  • Table Size (hash groups): Defines the size of the hash table (10 lists)
  • Array of Lists: Each list stores key-value pairs

Public Functions

isEmpty

  • Returns: Boolean indicating if the hash table is empty.
  • Implementation: Check if cumulative size of all lists is zero.

Hash Function

  • Returns: Integer, calculated as key % hash_groups (results in a value between 0 and 9).

Insert Function

  • Parameters: Key, Value
  • Process:
    • Compute hash value of the key to determine corresponding list.
    • Iterate over the list to check if key exists.
    • If key exists, replace the value.
    • If key does not exist, insert the new key-value pair.

Remove Function

  • Parameter: Key
  • Process:
    • Compute hash value to identify the list where the key might be.
    • Iterate through the list and remove the key-value pair if found.

Search Function

  • Parameter: Key
  • Returns: Value associated with the key.

Print Function

  • Process:
    • Print the keys and values of all lists in the hash table.

Example Usage

Main Function

  • Actions:
    • Create hash table and check if it is empty.
    • Insert various key-value pairs (phone numbers and names).
    • Replace value for a specific key to test insertion logic.
    • Print the hash table contents.
    • Remove specific keys and re-check if table is empty.

Output Check

  • Validate correct insertion, removal, replacement, and empty check behaviors.

Conclusion

  • Recap: Covered implementing a hash table with separate chaining using linked lists.
  • Encouragement: Contact for further questions or comments.