Поиск полный хэш-таблицу

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, и если вы не найдете его в списке, сделайте новый h_value и добавьте его в конец. В худшем случае у вас будет одиночный список, но в типичном случае вы равномерно распределите свои ценности среди всех ковшей.

Если вы заранее знаете свои ценности, вы можете взглянуть на идеальное хеширование, например gperf.