搜索一個完整的哈希表

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。