Hash Tables for Efficient Data Retrieval
Learn about hash tables and hashing techniques to optimize search, insert, and deletion operations in data structures. Explore examples, collision resolution strategies, and the importance of good hash functions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ECE 244 Programming Fundamentals Lec.26: Hash Tables Ding Yuan ECE Dept., University of Toronto http://www.eecg.toronto.edu/~yuan
Searching for specific Example: when you login to Facebook, it needs to locate your friend list using your userID FriendList search(uint64_t userID) search should return the FriendList if the userID is found, or NULL if it is not found
Hash Table Provides O(1) average performance on search/insert/deletion Basic idea: Stores data in a very large array Typically 2x as many elements as the # of data elements to be stored Each key (e.g., userID) maps to a unique index User hash function , h(k) to map each element into an array index h(userID) -> [0..m] Example: h(k) = k % (m+1)
Example h(key) = key % 7 insert(16): h(16) = 2 insert(25): h(25) = 4 insert(77): h(77) = 0 0 1 2 3 4 5 6 77 search(16): h(16) = 2 16 search(33): h(33) = 5 search(32): h(32) = 4 25 insert(7): h(7) = 0??
Collision Problem: two keys may map to the same array entry Solution: hashing with chaining Each hash table entry contains a pointer to a linked list of keys that map to the same entry 77 7 0 1 2 3 4 5 6 16 Therefore the worst-case complexity for search is O(n)!!! 25
Good hash function A good hash function should avoid collision So that the average length of each list is 1 How? Use more spaces E.g., > 2x array elements Use smarter algorithms Real-world hashing algorithms usually involve multiply a large prime number E.g., h(k) = k * 31 % m
