[C]Problema Doppio Hashing

[markg]

Salve,
ho due problemi con il doppio hashing:

1) Quando effettuo l'inserimento (Funzione Hash_Insert) mi restituisce l'errore di "Hash Table Overflow" anche quando la tabella non è piena.

2) Il tempo di esecuzione dell'Insert è molto diverso da quello della Search nel caso in cui l'elemento non è presente (Ricerca senza successo).

Gli input utilizzati sono:

Dimensione tabella = 60001 (numero primo)
Slot utilizzati in partenza = 20000
Incremento slot utilizzati = 1000


Il codice è il seguente:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 * Doppio HASHING . Nel main la dimensione massima da inserire deve essere un numero primo.
 */

int m;

struct table{
         int used_slot;
         float alpha;
         double Insert_time;
         double Search_time;
         double Search_WS_time;         
         };

//
int Hash_Insert(int T[], int k) {
     int i = 0;
     do {
         int j = Hash_Function_Double(k,i);
           if (T[j] == 0){
                    T[j] = k;
                    return j;
           }
           else {
                i++;
                }
     }
     while (i != m);           
     printf ("Hash Table Overflow");
}

//
int Hash_Search(int T[], int k) {
     int i = 0;
     int j = 0;
     do{
         j = Hash_Function_Double(k,i);
         if (T[j] == k)
                  return j;
         i++;
         }
     while(T[j] != 0 && i != m);
     return 0;
}

//
int Auxiliary_Hash_Function (int k) {
    int h;
    h = k % m; 
    return h;
}

//
int Auxiliary_Hash_Function2 (int k) {
    int h;
    h = 1 + (k % (m-1)); 
    return h;
}



//
int Hash_Function_Double(int k, int i){
    int h, x, y;
    x = Auxiliary_Hash_Function(k);
    y = Auxiliary_Hash_Function2(k);
    h = (x + i*y) % m;
    return h;
} 

int main(int argc, char *argv[]) {
  
  int MAX, i, j, k, l, n, N, random, ran;
  clock_t start,end;
  double Time,diff;
  FILE *result;

  
  //INSERTION INPUT DATA
  printf("Insert maximum array dimension: ");
  scanf("%d", &MAX);
  printf("Insert array start dimension: ");
  scanf("%d", &n);
  printf("Insert array increase step dimension: ");
  scanf("%d", &N);
  m = MAX;
  
  //CREATE DIMENSION ARRAY AND OUTPUT ARRAY(with results)
  int dim_input=((MAX-n)/N);
  int DIM[dim_input];
  struct table output[dim_input];
  DIM[0]=n;
  
  //FILLING DIMENSION ARRAY
  for(j=1;j<dim_input;j++){
          DIM[j]=DIM[j-1]+N;
          } 
  
  //CREATE INPUT ARRAY RANDOMLY 
  int *T;        
  srand (time(NULL));
  for (i=0; i<dim_input; i++){
     int dimension=DIM[i];
     T = malloc(MAX*sizeof(int));
     for (k=0;k<MAX;k++){
         T[k] = 0;
     }
     
     for(k=0;k<dimension;k++){
             random = rand();
             Hash_Insert(T,random);
     }
     
     output[i].used_slot=dimension;
     output[i].alpha = ((float)(dimension) /(float)(MAX));
     //ran = rand();
     
     diff=0;
     ran=rand();
     for(l=0;l<100000;l++){
        while (Hash_Search(T,ran) != 0) {
            ran = rand();
        }
        start = clock();          
        Hash_Search(T,ran);
        end = clock();
        diff = diff + difftime(end,start);
     } 
     printf("\nRicerca Senza Successo x 100000: %lf",diff);
     Time = ((double)(diff/100000)/CLK_TCK)*1000000000;
     output[i].Search_WS_time = Time;
     
     diff=0;
     for(l=0;l<1000000;l++){
        int index=rand()%dimension;
        int x=T[index];
        while (x == 0){
            index = rand()%dimension;
            x=T[index];
        }
        start = clock();
        Hash_Search(T,x);
        end = clock();
        diff = diff+difftime(end,start); 
        }
     printf("\nRicerca Con Successo x 1000000:  %lf",diff);
     Time = ((double)(diff/1000000)/CLK_TCK)*1000000000;
     output[i].Search_time = Time;

     diff=0;
     for(l=0;l<1000;l++){
        start = clock();
        Hash_Insert(T,ran);
        end = clock();
        diff = diff+difftime(end,start);
        } 
     //printf("\nInsert x 1000: %lf",diff);   
     Time = ((double)(diff/1000)/CLK_TCK)*1000000000;
     output[i].Insert_time = Time;
     
     
     free(T);
  }
 //SAVE RESULTS ON FILE
  result=fopen("D:\\ResultHASHdoublePROVA.txt","w+");
  fprintf(result,"Used Slot\tTotal Slot\tAlpha\t\tScan Insert\tScan Search\tScan Search Without Success\n");
  for(j=0;j<dim_input;j++){
          fprintf(result,"%d\t\t%d\t\t%lf\t%.0f\t\t%.0f\t\t\t%.0f\n",output[j].used_slot,m,output[j].alpha,output[j].Insert_time,output[j].Search_time,output[j].Search_WS_time); 
  }
  printf("\n");    
  printf("Results saved in: D:\\ResultHASHdouble.txt \n");
  system ("PAUSE");
  return 0;
}

Non riesco a trovare il problema.... Vi prego aiutatemi

Grazie

[Andrea Simonassi]

Ciao, fare il debug di un programma è un lavoro piuttosto oneroso, potresti limitare il posting alle parti di codice che pensi che possano creare problemi?

se ci limitiamo alla funzione seguente:

int Hash_Insert(int T[], int k) {
     int i = 0;
     do {
         int j = Hash_Function_Double(k,i);
           if (T[j] == 0){
                    T[j] = k;
                    return j;
           }
           else {
                i++;
                }
     }
     while (i != m);           /* Questo loop potrebbe non terminare mai. E' un errore piuttosto grave */



     printf ("Hash Table Overflow"); /*Questa printf viene eseguita sempre, non è condizionata.*/

/*manca il return.*/
}

Rivedi un po questa funzione perchè ha tanti errori, probabilmente dovuti a fretta.

Questi non sono nemmeno bug sono proprio errori che dovrebbero essere rilevati da warning del compilatore. Ma che razza di compilatore usi?

Ciao

[Andrea Simonassi]

Un ultima cosa, solo per cultura generale, non è un errore o che, è solo questione di potere poi riutilizzare il tuo codice... : quando scrivi un programma separa l'interfaccia utente dal resto del programma, non mettere printf in funzioni, caso mai scrivi sullo standard error o su un file di log, oppure fai che la tua funzione restituisca un codice di errore e demanda alla funzione chiamante l'onere di scrivere sul log o di avvisare l'utente..

Ciao a presto.