0

我只是想对应该适用于任何表大小的哈希表实现二次探测。我在下面编写的代码仅在哈希表大小为 10 时才有效。

基本上，我必须对 while 循环进行限制，最多可以进行探测。我手动检查，发现对于 10 的表大小，每 6 个索引位置都在重复。所以我把 6 的限制放到了 while 循环中。

当涉及到任何其他表大小时，重复索引位置的数量会有所不同。所以，我无法决定何时停止迭代。我愿意接受任何其他方法来解决这个问题。

#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);
    }
  }
}
4

1 回答 1

3

当涉及到任何其他表大小时，重复索引位置的数量会有所不同。所以，我无法决定在哪里停止迭代。请告诉我是否有其他方法可以解决此问题。

表格大小和探测功能的组合可以对每个可能的偏移量进行采样。因此，如果您允许完全自由选择表大小，那么探测函数循环长度的唯一确定上限是哈希表大小。尽管当循环长度实际上更短时使用该界限效率低下，但它仍然会产生正确的结果。

或者，探测函数的周期长度与键无关，因此您可以在表首次初始化时或插入第一个键时凭经验计算。

但考虑到不允许任意表大小可能对您有利。如果您对表大小和匹配的探针函数稍加注意，那么您可以确保探针将对每个哈希桶进行采样。这将具有以下优点：

  • 只要表有打开的存储桶，您就可以插入任意键。另一方面，如果探测功能没有对所有桶进行采样，那么即使有空桶，您也可以轻松达到无法插入某些键的状态。

  • 很简单，给定键所需的最大探测次数等于哈希表大小。

您可以通过多种方式实现这一目标，同时避免有界表大小。关于该主题的维基百科文章明确列出了两个，其中第一个似乎特别有希望：

  • 选择表格大小作为 2 的幂，并结合此类表格大小，
  • 使用三角形数字作为探针（0、1、3、6、10，...）。这是一个真正的二次探测，因为它们对应于二次函数p = ( i + i 2 ) / 2的值

请注意，三角数也很容易作为一个数列计算：如果T i指定第i个三角数（索引从 0 开始，使得 T 0 = 0），则T i = T i-1 + i为都为i大于 0。

于 2020-01-05T18:58:23.077 回答