CSC148H1 Lecture Notes - Lecture 30: Hash Table, Double Hashing, Linear Probing
CSC148: Lecture 30: Hashing
References: Code seen in the picture can be found on the CSC148 website
http://www.teach.cs.toronto.edu/~csc148h/winter
Lists and Linear Search and Ordered Lists and Binary Search
Data Structure
search()
insert()
delete()
List
O(n)
O(n)
O(n)
Ordered List
O(lg n)
O(lg n)
O(lg n)
Complexity Comparisons
- Comparison of function growth:
- How does dictionary offer constant time search?
o By a technique called hashing
Why Hash
- Lists are contiguous (adjacent) sequences of references to objects -> so access to a list
position is fast (just arithmetic)
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
References: code seen in the picture can be found on the csc148 website http://www. teach. cs. toronto. edu/~csc148h/winter. Lists and linear search and ordered lists and binary search. How does dictionary offer constant time search: by a technique called hashing. Lists are contiguous (adjacent) sequences of references to objects -> so access to a list position is fast (just arithmetic) Once you hashed an object to a number, you can easily use part of that number as an index into a list to store the object or something related to that object. If the list is of length n, you might store information about object o at index hash(o) % n. What"s the time complexity of: finding the string ada" in this list, what if you knew the index of ada", but how do you know the index of ada" in the list. Index number = sum ascii codes, mod, size of array: find ada, 262 mod 11 = 9, mydata = array(9)
