c - 搜索完整的哈希表

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 不是您要插入的内容，则查看所有 next 指针，如果您在列表中找不到它，则创建一个新的 h_value 并将其添加到末尾。在最坏的情况下，您将拥有一个单链表，但在典型情况下，您将在所有存储桶中平均分配您的值。

如果您提前知道您的值，您可能想要研究完美的散列，例如gperf。