Rice University - Comp 212 - Intermediate Programming

Spring 2007

Lecture 31 - Hash Functions


Hash Functions



Review: Comparing the four IDictionary implementations



Expected-case Cost Worst-case Cost





lookup() O(n) O(n)
DictLRS insert() O(n) O(n)

remove() O(n) O(n)





lookup() O(log n) O(n)
DictBT insert() O(log n) O(n)

remove() O(log n) O(n)





lookup() O(log n) O(log n)
DictArray insert() O(n) O(n)

remove() O(n) O(n)





lookup() O(1) O(n)
DictHash insert() O(1)* O(n)

remove() O(1) O(n)
*Calculated by amortizing the cost of doubling the hash table size over the subsequent inserts.