Rice University - Comp 212 - Intermediate Programming

Spring 2005

Lecture 31 - Hash Functions; Interpolation Search

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.

Can We Improve On Binary Search?

Interpolation Search



  private int findIndex(Comparable key) {
    int lo = -1;
    int hi = _firstEmptyKeyValuePair;
    while (lo + 1 != hi) {
      ExtendedComparable loKey = _pairs[lo + 1].getKey();
      ExtendedComparable hiKey = _pairs[hi - 1].getKey();
      int mid = lo + key.sub(loKey)*(hi - lo)/hiKey.sub(loKey);
      int result = _pairs[mid].getKey().compareTo(key);
      if (result == 0)
        return (mid);
      else if (result > 0)
        hi = mid;
        lo = mid;
    return lo;

The Computational Cost of Interpolation Search