Hash Tables (Mar 15)
Practice, practice, practice
Familiarize yourself with the four hash functions described in class:
- Chaining
- Linear Probing
- Quadractic Probing
- Double Hashing
Chaining is refered to as a open addressing (open hashing aka. separate chaining), because it uses addresses/storage outside the original hash table. It uses linked lists to keep track of the values in each bucket.
Linear Probing, Quadractic Probing, and Double Hashing are closed addressing (open addressing aka. closed hashing), because all the values are hashed to some index in the hash table.
You should go through some examples to make sure you are familiar with each of these methods. If you are asked to draw a hash table, and insert/delete values, you should be able to do it extremely quickly.
You can use the handout below to complete Q2, Q3, and Q4 of the tutorial.
Download tutorial handout [xlsx spreadsheet][13KB] OR [PDF][57KB]
Hashing should be a very easy topic (and grade booster) in this course, IF you practice a bit.
Running times
Reference sheet: http://bigocheatsheet.com/
Note that in the lectures, we compared Hash Tables with BALANCED Binary Search Trees. If you want to use a reference like the big-O cheat sheet, you can look at B-Trees or Red-Black Trees, which are relatively balanced BSTs. The worst case for a generic (unbalanced) BST is much slower, and not worth comparing.