8.Hashing (1)§

Hashing: The process of mapping a key value to a position in a table.

A hash function maps key values to positions. It is denoted by \(h\).

A hash table is an array that holds the records. It is denoted by HT.

HT has \(M\) slots, indexed form 0 to \(M-1\).

Hashing (2)

For any value \(K\) in the key range and some hash function \(h\), \(h(K) = i\), \(0 <= i < M\), such that key(HT[i]) \(= K\).

Hashing is appropriate only for sets (no duplicates).

Good for both in-memory and disk-based applications.

Answers the question “What record, if any, has key value K?”

Simple Examples

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Collisions (1)

Collisions (2)

Hash Functions (1)

Hash Functions (2)

Simple Mod Function

int h(int x) {
  return x % 16;
}
Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Binning

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Mod vs. Binning

Binning vs. Mod Function

Mid-Square Method

Mid-square method example

Strings Function: Character Adding

int sascii(String x, int M) {
  char ch[];
  ch = x.toCharArray();
  int xlength = x.length();

  int i, sum;
  for (sum=0, i=0; i < x.length(); i++)
    sum += ch[i];
  return sum % M;
}

String Folding

// Use folding on a string, summed 4 bytes at a time
int sfold(String s, int M) {
  long sum = 0, mul = 1;
  for (int i = 0; i < s.length(); i++) {
    mul = (i % 4 == 0) ? 1 : mul * 256;
    sum += s.charAt(i) * mul;
  }
  return (int)(Math.abs(sum) % M);
}

Open Hashing

Bucket Hashing (1)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Bucket Hashing (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Closed Hashing

Collision Resolution

Insertion

// Insert e into hash table HT
void hashInsert(const Key& k, const Elem& e) {
  int home;                     // Home position for e
  int pos = home = h(k);        // Init probe sequence
  for (int i=1; EMPTYKEY != (HT[pos]).key(); i++) {
    pos = (home + p(k, i)) % M; // probe
    if (k == HT[pos].key()) {
      println("Duplicates not allowed");
      return;
    }
  }
  HT[pos] = e;
}

Probe Function

Linear Probing (1)

Linear Probing (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Problem with Linear Probing

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Linear Probing by Steps (1)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Linear Probing by Steps (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Pseudo-Random Probing (1)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Pseudo-Random Probing (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Quadratic Probing

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Double Hashing (1)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Double Hashing (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Analysis of Closed Hashing

The load factor is \(\alpha = N/M\) where \(N\) is the number of records currently in the table.

Hashing analysis plot

Deletion

Tombstones (1)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Tombstones (2)