Hashing

Hashing

a WimpyPoint presentation owned by Mark Dettinger

a + b = K ?


    
    
    
    

First Attempt: O(n2)


int a[N+1];

for i=1 to N-1 {
  for j=i+1 to N {
    if (a[i] + a[j] == K) {
      print(a[i]+ " and "+a[j]);
      return;
    }
  }
}
print("no such integers");
    
    
    
    

How about this algorithm?


int a[N+1];
boolean checked[K+1];

for i=0 to K { checked[i] = false; }
for i=1 to N {
  checked[a[i]] = true;
  if (checked[K-a[i]]==true) {
    print(a[i]+" and "+(K-a[i]));
    return;
  }
}
print("no such integers");
    
    
    
    

Analysis


    
    
    
    

Hashtables


    
    
    
    

The basic idea


int hashtable[M];  // M > N

void store (int key, int value) {
  hashtable[h(key)] = value;
}

void get_value (int key) {
  return hashtable[h(key)];
}

int h (int key) {
  return h % M;
}
    
    
    
    

How likely are collisions?


    
    
    
    

Ways to resolve collisions


    
    
    
    

Open Hashing


    
    
    
    

Linear Probing


    
    
    
    

Quadratic Probing


    
    
    
    

Double Hashing


    
    
    
    

Universal Hashing


    
    
    
    

Second Attempt: O(n)


t = new Hashtable;
for i=1 to N {
  t.put(a[i],1);
  if (t.get(K-a[i])!=NULL) {
    print(a[i]+" and "+(K-a[i]));
    return;
  }
}
print("no such integers");
    
    
    
    

Mark Dettinger