Coconote
AI notes
AI voice & video notes
Export note
Try for free
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.
📄
Full transcript