搜索一个完整的哈希表

Question

考虑下面的代码片段：

#include<stdio.h> 
#include<conio.h> 
#define TABLESIZE 100 

sturct record{ 
     int k; 
     int r; 
     }table[TABLESIZE]; 

int tcount=0; 

int search_and_insert(int key,int rec){ 
    int i; 
    i=h(key); 
    while(table[i].k!=key && table[i].k!=NULL) 
               i=rh(i); 

    if(table[i].key==NULL){ 
          table[i].k=key; 
          table[i].r=rec; 
          tcount++; 
          } 
    return i; 
    } 

int h(int key){ 

    return key%1000; 

    } 

int rh(int hkey){ 

    int k; 
    if(hkey==99) 
    return 0; 
    return ((hkey+1)%1000); 

    } 

的while循环可能无限循环，如果表已经满了，要解决这个问题，我可以 引入if声明是这样的：

if(tcount<TABLESIZE){ 
    while(table[i].k!=key && table[i].k!=NULL) 
               i=rh(i);/*Rehash*/ 

    if(table[i].key==NULL){ 
          table[i].k=key; 
          table[i].r=rec; 
          tcount++; 
         } 
} 

但根据我这引起了另一个问题，即我将无法搜索已经存在于表中的记录，当表已满或搜索将提供一个错误的结果。

可以解决这个问题吗？

Answer 1

由于您正在进行简单的线性探测，因此您可以通过比较当前散列值与原始散列值，轻松检查您是否围绕散列表进行了整圈。

int h0 = hash(key); 
int h = h0; 

do { 
    if (found_in_bucket(key, h)) 
     return value_in_bucket(h); 
    h = rehash(h); 
} while (h != h0); 

Answer 2

典型的解决方案，以这种问题链接，这是有你的散列键指向一个链接结构：

struct h_value 
{ 
    int rec; 
    struct h_value *next; 
}; 

插入时，如果您查找的位置和REC是不是你'插入你通过rec的所有下一个指针，如果你没有在列表中找到它，请创建一个新的h_value并将其添加到结尾。在最糟糕的情况下，你会得到一个单链表，但在典型情况下，你会平均分配你的值到所有桶中。

如果你提前知道你的值，你可能想要看看完美的哈希，如gperf。