CSC148H1 Lecture Notes - Lecture 32: Hash Table, Functional Programming, Binary Search Algorithm
CSC148: Lecture 32: Hashing and Exam Review
References: Pictures seen can be found on the CSC148 website:
http://www.teach.cs.toronto.edu/~csc148h/winter
Other Use Cases of Hashing
- Passwords stored as hashed values
- When you forget password, hard to retrieve even for admin
o Same hash value
▪ Two different original passwords
- During log in, hash values are matched for given and store
- Odds are low for two passwords to have same hash value
- Hackers still follow brute force approach
Coding Hash Table
- Completed has table has expected performance in 𝛩(𝑛) for a dictionary with n entries
- self.table = [[] for _in range(self.capacity)]
o Not self.table = [[]]* capacity
- old_table = self.table
o Temporarily save self.table
- self.items, self.collisions = 0, 0
o Reset items and collisions
- self.capacity *= 2
o Create double-sized table
- for bucket in old_table: …
o Insert old items into new table
1
CSC148H1 Full Course Notes
Verified Note
1 document
