hashTable2.c

/*
   Description: This program creates a hash table that inserts 7 values using the quadratic probing method
   By: randerson112358
*/

//Libraries
#include<stdio.h>
#include<stdlib.h>

//The size of the hash table
# define SIZE 7 //NOTE: for the quadratic probing method, the size must be a primary number to make sure that we can insert keys on collisions
                // and the hash table must be at least half empty
                
//Define our functions
int quadratic_probing_insert(int *hashtable, int *empty,  int key);
                
int main(){
  int hashtable[SIZE]; //Creating the hash table
  int empty[SIZE] = {0}; //Initializing all elements in the array 'empty' to 0
  
  int i;
  for(i=0; i<SIZE; i++){
    quadratic_probing_insert(hashtable, empty, i);
  }
  
  for(i=0; i<SIZE; i++){
    printf("%d ", hashtable[i]);
  }
  
  
  
  return 0;
}
  
/*
   1. Get the key 'k'
   2. Set counter i=0
   3. Compute hash function h[k] = k % SIZE
   4. If the hashtable[ h[k] ] is empty
        (4.1) Insert key 'k' at hashtable[h[k]]
        (4.2) Stop
      Else
          (4.3) The key space at hashtable[ h[k] ] is occupied, so we need to find the next available key space
          (4.4) Increment i
          (4.5) Compute new hash function h[k] = (k + i * i) % SIZE
    5. The hash table is full
    6. Stop
*/        
int quadratic_probing_insert(int *hashtable, int *empty,  int key){
  
  int i, index;//index is the hash function 'h'
  
  for( i=0; i<SIZE; i++){
    index = (key + i * i)% SIZE;
    if(empty[index] == 0){
      
      //Insert the key at that index
      hashtable[index] = key;
      
      //Mark that the position in the hashtable has been taken, using the empty array.
      empty[index] = -1;
      return index;
    }
    
  }
  
  return -1;
}      

/*
1. Get the key k to be searched
 2. Set counter j = 0
 3. Compute hash function h[k] = k % SIZE
 4. If the key space at hashtable[h[k]] is occupied
         (4.1) Compare the element at hashtable[h[k]] with the key k.
         (4.2) If they are equal
         (4.2.1) The key is found at the bucket h[k]
         (4.2.2) Stop
    Else
         (4.3) The element might be placed at the next location given by the quadratic function
         (4.4) Increment j
         (4.5) Set k = ( k + (j * j) ) % SIZE, so that we can probe the bucket at a new slot, h[k].
         (4.6) Repeat Step 4 till j is greater than SIZE of hash table
 5. The key was not found in the hash table
 6. Stop
*/

int quadratic_probing_search(int *hashtable, int key, int *empty)
{
    /* If the key is found in the hash table, the function returns the index of the hashtable where the key is inserted, otherwise it 
       returns (-1) if the key is not found */

    int i, index;

    for (i = 0; i < SIZE; i++) {
        index = (key + i*i) % SIZE;
        if (empty[index] != 0 && hashtable[index] == key)
            return index;
    }
    return -1;
}