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.