Algorithms and Data Structures
Excercise 12
Search 3 (Hash)

Problem 1 ［PostScript for printing］

Hash function and double hash function are following:

int hash(char c){
  return (int)(c-64)%M;
}
int hash2(char c){
  return (int)8-(c-64)%8;
}

(1) Calculate the hash values of the following data and write the hash table hashed by using the separate chaining method. The length of the hash table M is 11.

W H I T E C H O C O L A T E

(2) Calculate the hash values of the following data and write the hash table hashed by using the linear probing method. The length of the hash table M is 9.

P U D D I N G

(3) Calculate the hash values of the following data and write the hash table hashed by using the double hashing method. The length of the hash table M is 9.

P U D D I N G

Problem 2

Write a program which hashes by using separate chaining method and uses the following function. Input data from keyboard, a hash table is displayed finally. The length of the hash table M is 5.

int hash(char c){
  return (int)(c-64)%M;
}

Example:
% ./a.out
Input data: CHOCOLATE
 0: E T O O 
 1: A 
 2: L 
 3: C H C 
 4: 

Problem 3

Write a program which hashes by using double hashing method and uses the following functions. Input data from keyboard, and display a hash table whenever data is inserted. The length of the hash table M is 5.

int hash(char c){
  return (int)(c-64)%M;
}
int hash2(char c){
  return (int)8-(c-64)%8;
}

Example:
% ./a.out
Input data: CHOCOLATE
      C               
      C         H     
      C O       H     
    C C O       H     
    C C O O     H     
  L C C O O     H     
A L C C O O     H     
A L C C O O     H T   
A L C C O O E   H T