Question

Write a program to compute the number of collisions required in a long random sequence of insertions using linear probing, quadratic probing, and double hashing.

Answer 1

ANSWER:--

GIVEN THAT:--

• linear probing function:--

  
  #include <iostream>
  #include <cstdio>
  #include <cstdlib>
  using namespace std;
  const int TABLE_SIZE = 5;

  class hashnodes
  {
  public:
  int key;
  int value;
  hashnodes(int key, int value)
  {
  this->key = key;
  this->value = value;
  }
  };

  class delnodes:public hashnodes
  {
  private:
  static delnodes *entry;
  delnodes():hashnodes(-1, -1)
  {}
  public:
  static delnodes *getNode()
  {
  if (entry == NULL)
  entry = new delnodes();
  return entry;
  }
  };
  delnodes *delnodes::entry = NULL;

  class HashMap
  {
  private:
  hashnodes **htable;
  public:
  HashMap()
  {
  htable = new hashnodes* [TABLE_SIZE];
  for (int i = 0; i < TABLE_SIZE; i++)
  {
  htable[i] = NULL;
  }
  }
  
  ~HashMap()
  {
  for (int i = 0; i < TABLE_SIZE; i++)
  {
  if (htable[i] != NULL && htable[i] != delnodes::getNode())
  delete htable[i];
  }
  delete[] htable;
  }
  
  int HashFunc(int key)
  {
  return key % TABLE_SIZE;
  }
  
  void Insert(int key, int value)
  {
  int hash_val = HashFunc(key);
  int init = -1;
  int deletedindex = -1;
  while (hash_val != init && (htable[hash_val]
  == delnodes::getNode() || htable[hash_val]
  != NULL && htable[hash_val]->key != key))
  {
  if (init == -1)
  init = hash_val;
  if (htable[hash_val] == delnodes::getNode())
  deletedindex = hash_val;
  hash_val = HashFunc(hash_val + 1);
  }
  if (htable[hash_val] == NULL || hash_val == init)
  {
  if(deletedindex != -1)
  htable[deletedindex] = new hashnodes(key, value);
  else
  htable[hash_val] = new hashnodes(key, value);
  }
  if(init != hash_val)
  {
  if (htable[hash_val] != delnodes::getNode())
  {
  if (htable[hash_val] != NULL)
  {
  if (htable[hash_val]->key == key)
  htable[hash_val]->value = value;
  }
  }
  else
  htable[hash_val] = new hashnodes(key, value);
  }
  }
    
  int search(int key)
  {
  int hash_val = HashFunc(key);
  int init = -1;
  while (hash_val != init && (htable[hash_val]
  == delnodes::getNode() || htable[hash_val]
  != NULL && htable[hash_val]->key != key))
  {
  if (init == -1)
  init = hash_val;
  hash_val = HashFunc(hash_val + 1);
  }
  if (htable[hash_val] == NULL || hash_val == init)
  return -1;
  else
  return htable[hash_val]->value;
  }
  
  void remove(int key)
  {
  int hash_val = HashFunc(key);
  int init = -1;
  while (hash_val != init && (htable[hash_val]
  == delnodes::getNode() || htable[hash_val]
  != NULL && htable[hash_val]->key != key))
  {
  if (init == -1)
  init = hash_val;
  hash_val = HashFunc(hash_val + 1);
  }
  if (hash_val != init && htable[hash_val] != NULL)
  {
  delete htable[hash_val];
  htable[hash_val] = delnodes::getNode();
  }
  }
  };

  int main()
  {
  HashMap hash;
  int key, value;
  int choice;
  while(1)
  {
  
  cout<<"Operations on Hash Table"<<endl;
  
  cout<<"1.Insert an element into the table"<<endl;
  cout<<"2.search an element from the key"<<endl;
  cout<<"3.Delete an element at a key"<<endl;
  cout<<"4.Exit"<<endl;
  cout<<"Enter your choice: ";
  cin>>choice;
  switch(choice)
  {
  case 1:
  cout<<"Enter element to be inserted: ";
  cin>>value;
  cout<<"Enter key at which element to be inserted: ";
  cin>>key;
  hash.Insert(key, value);
  break;
  case 2:
  cout<<"Enter key of the element to be searched: ";
  cin>>key;
  if(hash.search(key) == -1)
  {
  cout<<"No element found at key "<<key<<endl;
  continue;
  }
  else
  {
  cout<<"Element at key "<<key<<" : ";
  cout<<hash.search(key)<<endl;
  }
  break;
  case 3:
  cout<<"Enter key of the element to be deleted: ";
  cin>>key;
  hash.remove(key);
  break;
  case 4:
  exit(1);
  default:
  cout<<"\nEnter correct option\n";
  }
  }
  return 0;
  }

  --------------------------------

  quadratic probing:--

  
  #include <iostream>
  #include <cstdlib>
  #define MIN_TABLE_SIZE 10
  using namespace std;

  enum entrytype {Legitimate, Empty, Deleted};

  struct HashNode
  {
  int element;
  enum entrytype info;
  };

  struct HashTable
  {
  int size;
  HashNode *table;
  };

  bool isPrime (int n)
  {
  if (n == 2 || n == 3)
  return true;
  if (n == 1 || n % 2 == 0)
  return false;
  for (int i = 3; i * i <= n; i += 2)
  if (n % i == 0)
  return false;
  return true;
  }

  int nextPrime(int n)
  {
  if (n <= 0)
  n == 3;
  if (n % 2 == 0)
  n++;
  for (; !isPrime( n ); n += 2);
  return n;
  }

  int HashFunc(int key, int size)
  {
  return key % size;
  }

  HashTable *initializeTable(int size)
  {
  HashTable *htable;
  if (size < MIN_TABLE_SIZE)
  {
  cout<<"Table Size Too Small"<<endl;
  return NULL;
  }
  htable = new HashTable;
  if (htable == NULL)
  {
  cout<<"Out of Space"<<endl;
  return NULL;
  }
  htable->size = nextPrime(size);
  htable->table = new HashNode [htable->size];
  if (htable->table == NULL)
  {
  cout<<"Table Size Too Small"<<endl;
  return NULL;
  }
  for (int i = 0; i < htable->size; i++)
  {
  htable->table[i].info = Empty;
  htable->table[i].element = NULL;
  }
  return htable;
  }

  int Find(int key, HashTable *htable)
  {
  int pos = HashFunc(key, htable->size);
  int collisions = 0;
  while (htable->table[pos].info != Empty &&
  htable->table[pos].element != key)
  {
  pos = pos + 2 * ++collisions -1;
  if (pos >= htable->size)
  pos = pos - htable->size;
  }
  return pos;
  }

  void Insert(int key, HashTable *htable)
  {
  int pos = Find(key, htable);
  if (htable->table[pos].info != Legitimate)
  {
  htable->table[pos].info = Legitimate;
  htable->table[pos].element = key;
  }
  }

  HashTable *Rehash(HashTable *htable)
  {
  int size = htable->size;
  HashNode *table = htable->table;
  htable = initializeTable(2 * size);
  for (int i = 0; i < size; i++)
  {
  if (table[i].info == Legitimate)
  Insert(table[i].element, htable);
  }
  free(table);
  return htable;
  }

  void Retrieve(HashTable *htable)
  {
  for (int i = 0; i < htable->size; i++)
  {
  int value = htable->table[i].element;
  if (!value)
  cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
  else
  cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
  }
  
  }

  int main()
  {
  int value, size, pos, i = 1;
  int choice;
  HashTable *htable;
  while(1)
  {
  cout<<"Operations on Quadratic Probing"<<endl;
  cout<<"1.Initialize a size of the table"<<endl;
  cout<<"2.Insert an element into the table"<<endl;
  cout<<"3.Display the Hash Table"<<endl;
  cout<<"4.Rehash The Table"<<endl;
  cout<<"5.Exit"<<endl;
  cout<<"Enter your choice: ";
  cin>>choice;
  switch(choice)
  {
  case 1:
  cout<<"Enter size of the Hash Table: ";
  cin>>size;
  htable = initializeTable(size);
  cout<<"Size of Hash Table: "<<nextPrime(size);
  break;
  case 2:
  if (i > htable->size)
  {
  cout<<"Table is Full, Rehash the table"<<endl;
  continue;
  }
     cout<<"Enter the element to be inserted: ";
     cin>>value;
  Insert(value, htable);
  i++;
  break;
  case 3:
  Retrieve(htable);
  break;
  case 4:
  htable = Rehash(htable);
  break;
  case 5:
  exit(1);
  default:
  cout<<"\nEnter the correct option\n";
  }
  }
  return 0;
  }

  --------------------

  double hashing--

  ------------

  #include <iostream>
  #include <cstdlib>
  #define MIN_TABLE_SIZE 10
  using namespace std;

  enum entrytype {Legitimate, Empty, Deleted};

  struct hashnode
  {
  int element;
  enum entrytype info;
  };

  struct HashTable
  {
  int size;
  hashnode *table;
  };

  int HashFunc1(int key, int size)
  {
  return key % size;
  }

  int HashFunc2(int key, int size)
  {
  return (key * size - 1) % size;
  }

  HashTable *initializeTable(int size)
  {
  HashTable *htable;
  if (size < MIN_TABLE_SIZE)
  {
  cout<<"Table Size Too Small"<<endl;
  return NULL;
  }
  htable = new HashTable;
  if (htable == NULL)
  {
  cout<<"Out of Space"<<endl;
  return NULL;
  }
  htable->size = size;
  htable->table = new hashnode [htable->size];
  if (htable->table == NULL)
  {
  cout<<"Table Size Too Small"<<endl;
  return NULL;
  }
  for (int i = 0; i < htable->size; i++)
  {
  htable->table[i].info = Empty;
  htable->table[i].element = NULL;
  }
  return htable;
  }

  int Find(int key, HashTable *htable)
  {
  int hashVal= HashFunc1(key, htable->size);
  int stepSize= HashFunc2(key, htable->size);
  while (htable->table[hashVal].info != Empty &&
  htable->table[hashVal].element != key)
  {
  hashVal = hashVal + stepSize;
  hashVal = hashVal % htable->size;
  }
  return hashVal;
  }

  void Insert(int key, HashTable *htable)
  {
  int pos = Find(key, htable);
  if (htable->table[pos].info != Legitimate )
  {
  htable->table[pos].info = Legitimate;
  htable->table[pos].element = key;
  }
  }

  HashTable *Rehash(HashTable *htable)
  {
  int size = htable->size;
  hashnode *table = htable->table;
  htable = initializeTable(2 * size);
  for (int i = 0; i < size; i++)
  {
  if (table[i].info == Legitimate)
  Insert(table[i].element, htable);
  }
  free(table);
  return htable;
  }

  void Retrieve(HashTable *htable)
  {
  for (int i = 0; i < htable->size; i++)
  {
  int value = htable->table[i].element;
  if (!value)
  cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
  else
  cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
  }
  
  }

  int main()
  {
  int value, size, pos, i = 1;
  int choice;
  HashTable *htable;
  while(1)
  {
  cout<<"Operations on Double Hashing"<<endl;
  cout<<"1.Initialize the size of the table"<<endl;
  cout<<"2.Insert an element into the table"<<endl;
  cout<<"3.Display Hash Table"<<endl;
  cout<<"4.Rehash The Table"<<endl;
  cout<<"5.Exit"<<endl;
  cout<<"Enter your choice: ";
  cin>>choice;
  switch(choice)
  {
  case 1:
  cout<<"Enter size of the Hash Table: ";
  cin>>size;
  htable = initializeTable(size);
  break;
  case 2:
  if (i > htable->size)
  {
  cout<<"Table is Full, Rehash the table"<<endl;
  continue;
  }
     cout<<"Enter element to be inserted: ";
     cin>>value;
  Insert(value, htable);
  i++;
  break;
  case 3:
  Retrieve(htable);
  break;
  case 4:
  htable = Rehash(htable);
  break;
  case 5:
  exit(1);
  default:
  cout<<"\nEnter correct option\n";
  }
  }
  return 0;
  }