How to debug a quadratic probing implementation for hash tables in C without using pointers?

Question

I'm just trying to implement quadratic probing for hash tables that should work for any table size. The code that I wrote below is working only if the hash table size is 10.

Basically, I have to put a limit to the while loop, up to which the probing can occur upmost. I checked manually, and I found that, for a table size of 10, every 6 index positions are repeating. So I put the limit of 6 to the while loop.

When it comes to any other table size, the repeating index positions are varying in number. So, I can't decide when to stop the iteration. I am open to any other method to solve this problem.

#include <stdio.h>
#include<stdlib.h>
#define TS 10

int ht[TS]={};

void insert()
{
  int key,i=0,ind,s=0,hk;
  // printf("\nenter a value to insert into htasht table\n");
  scanf("%d",&key);
  hk=key%TS;

  while(s!=6)// limit=6 which is working only for table size 10
  {
    ind=(hk+i)%TS;
    if(ht[ind] == 0 )
    {
      ht[ind]=key;
      break;
    }
    s=s++;
    i=(s*s)%TS;
  }
  if(s==6)
  {
    printf("value cant be inserted\n");
  }
}

int search(int key)
{

  int ind,i=0,hk,s=0;
  hk=key%TS;
  while(s!=6)
  {
    ind=(hk+i)%TS;
    if(ht[ind]==key)
    {
      printf("value is found at ind %d\n ",ind);
      return ind;
      //      break;
    }s=s++;
    i=(s*s)%TS;
  }
  if(s==6)
  {
    printf("value not found\n");
    return 0;
  }
  //  return 0;
}

void display()
{

  int i;

  printf("\nelements in thte htasht table are \n");

  for(i=0;i< TS; i++)

  printf("\n ind %d -- value = %d",i,ht[i]);

}

void del(int key)
{
  int i,ind;
  ind=search(key);
  if(ind)
  {
    ht[ind]=0;
    printf("deleted");
  }

  ind=0;
}


void main()
{
  int opt,key,n;

  /*printf("Enter step size of hash table\n");
scanf("%d",&s);
*/
  while(1)
  {
    printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Delete\t 5.exit \n");
    scanf("%d",&opt);
    switch(opt)
    {
    case 1:printf("Enter how many values you want to enter\n");
      scanf("%d",&n);
      printf("enter values\n");
      for(int j=0;j<n;j++)
      {insert();}
      // insert();
      break;
    case 2:
      display();
      break;
    case 3:
      printf("Enter search element\n");
      scanf("%d",&key);                search(key);
      break;
    case 4:
      printf("Enter element to be deleted\n");
      scanf("%d",&key);//search(key);
      del(key);
      break;
    case 5:exit(0);
    }
  }
}

Answer 1

When it comes to any other table size, the repeating index positions are varying in number. So, I can't decide where to stop the iteration. Please tell me if any other method is there to solve this problem.

There are combinations of table size and probe function that sample every possible offset. Therefore, if you're allowing for completely free choice of table size then the only sure upper bound on the cycle length of your probe function is the hash table size. Although it is inefficient to use that bound when the cycle length is actually shorter, it will still produce correct results.

Alternatively, the cycle length of the probe function is independent of key, so you could compute that empirically, either when the table is first initialized or when the first key is inserted.

But consider that it might be to your advantage not to allow arbitrary table sizes. If you exercise a bit of care with table sizes and matching probe functions then you can ensure that the probe will sample every hash bucket. This would have the advantageous properties that

• You can insert arbitrary keys as long as the table has open buckets. If, on the other hand, the probe function does not sample all buckets then you can easily reach states where some keys cannot be inserted even though there are empty buckets.

• It follows trivially that the maximum number of probes required for a given key is equal to the hash table size.

You can achieve that yet avoid bounded table sizes in a variety of ways. The Wikipedia article on the topic lists two explicitly, of which the first seems particularly promising:

• Choose the table size as a power of 2, AND, in conjunction with such table sizes,
• Use the triangular numbers as your probes (0, 1, 3, 6, 10, ...). This is a bona fide quadratic probe because these correspond to the values of the quadratic function p = (i + i²) / 2

Note that the triangular numbers are also very easy to compute as a series: if T_i designates the i^th triangular number (with indexes starting at 0, such that T₀ = 0), then T_i = T_i-1 + i for all for i greater than 0.