我只是在尝试为应该适用于任何表大小的哈希表实现二次探测。我在下面编写的代码仅在哈希表大小为 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 tablen");
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 insertedn");
}
}
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 %dn ",ind);
return ind;
// break;
}s=s++;
i=(s*s)%TS;
}
if(s==6)
{
printf("value not foundn");
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 tablen");
scanf("%d",&s);
*/
while(1)
{
printf("nPress 1. Insertt 2. Display t3. Search t4.Deletet 5.exit n");
scanf("%d",&opt);
switch(opt)
{
case 1:printf("Enter how many values you want to entern");
scanf("%d",&n);
printf("enter valuesn");
for(int j=0;j<n;j++)
{insert();}
// insert();
break;
case 2:
display();
break;
case 3:
printf("Enter search elementn");
scanf("%d",&key); search(key);
break;
case 4:
printf("Enter element to be deletedn");
scanf("%d",&key);//search(key);
del(key);
break;
case 5:exit(0);
}
}
}
当涉及到任何其他表格大小时，重复索引位置的数量各不相同。因此，我无法决定在哪里停止迭代。请告诉我是否有其他方法可以解决此问题。
有工作台大小和探针功能的组合，可以对每个可能的偏移进行采样。 因此，如果您允许完全自由选择表大小，那么探测函数周期长度的唯一确定上限是哈希表大小。 尽管当周期长度实际上较短时使用该边界效率低下，但它仍然会产生正确的结果。
或者，探测函数的周期长度与键无关，因此您可以根据经验计算，无论是在首次初始化表时还是在插入第一个键时。
但请注意，不允许任意表大小可能对您有利。 如果您对表大小和匹配的探测函数稍加小心，则可以确保探测将采样每个哈希桶。 这将具有以下优势：
-
只要表具有打开的存储桶，您就可以插入任意键。 另一方面，如果探测函数没有对所有存储桶进行采样，那么即使有空存储桶，您也可以轻松达到无法插入某些键的状态。
可以 简单地说，给定键所需的最大探测数等于哈希表大小。
您可以实现这一点，同时通过多种方式避免有界的表大小。 关于该主题的维基百科文章明确列出了两个，其中第一个似乎特别有希望：
- 选择表大小作为 2 的幂，并且结合此类表大小，
- 使用三角形数字作为探针(0、1、3、6、10 等(。 这是一个真正的二次探头，因为它们对应于二次函数p= (i +i2(/2的值
请注意，三角形数也很容易作为一个系列计算：如果 T i 指定第 i 个三角形数(索引从 0 开始，使得 T 0 =0(，则 T i =Ti-1+ i 对于所有i大于 0。