Rice University - Comp 212 - Intermediate Programming

Spring 2008

Lecture 31 - Hash Functions

Hash Functions

Applications of Hash Functions"

Hash functions have many applications besides Hash Tables. For example, Bloom Filters


are an application of hash functions to the implementation of sets.

Some applications rely on hash functions with special properties:


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.