Our complexity track record:

makoto’s question

Hash table

• hashing function
  • determinism, uniformity. range? invertible?
• the space / time tradeoff
• table with buckets modulo (%) ( collision )

collision

• separate chaining
• open addressing
  • Linear probing, quadratic probing
  • double hashing

Hash table

• O(c) but no iteration
• load factor and resize add some links for iteration

linear probing example

char[] table = new char[table_size];

void insert(char c) {
  int probe = 0;
  while(table[(hash(c)+probe)%table_size]!=null) {
    probe++;
    if(probe>=table_size) break;
  }
  table[(hash(c)+probe)%table_size] = c;
}

boolean contains(char c) {
  int probe = 0;
  while(probe<table_size) {
    if(table[(hash(c)+probe)%table_size]==null) return false;
    else if((table[hash(c)+probe)%table_size]==c) return true;
    probe++;
  }
  return false;
}

Assignment

ACSL style. Coming Monday

hash ACSL assignment

DUE MONDAY, 12/7 AT THE BEGINNING OF CLASS

resubmissions until winter break