У меня есть процедура хеширования C, которая ведет себя странно

Question

В этой процедуре хэширования: 1.) Я могу добавить строки. 2.) Я могу просмотреть мои добавленные строки. 3.) Когда я пытаюсь добавить дублируемую строку, это вызывает у меня ошибку, уже присутствующую. 4.) Но, когда я пытаюсь удалить ту же строку, которая уже присутствует в хэш-таблице, , тогда функция lookup_routine вызывает хэш-функцию для получения индекса. В это время он выдает другой индекс хеширования тому, который уже был добавлен. Следовательно, моя процедура удаления не работает?

Я могу понять причину, почему для той же строки хеш-функция каждый раз вычисляет другой индекс (тогда как та же самая логика работает в режиме хеш-таблицы)? Кто-нибудь может мне помочь?

Это выход, я получаю:

$ ./a 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 1 

Please enter the string :gaura 

enters in add_string 

DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 1 
hashval = 1 
enters in lookup_string 

str in lookup_string = gaura 
DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 1 
hashval = 1 

DEBUG ERROR :element not found in lookup string 

DEBUG Purpose 

NULL 

Inserting... 

DEBUG1 : enters here 

hashval = 1 
String added successfully 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 1 

Please enter the string :ayu 

enters in add_string 

DEBUG purpose in hash function: 

str passed = ayu 
Hashval returned in hash func= 1 
hashval = 1 
enters in lookup_string 

str in lookup_string = ayu 
DEBUG purpose in hash function: 

str passed = ayu 
Hashval returned in hash func= 1 
hashval = 1 

returns NULL in lookup_string 

DEBUG Purpose 

NULL 

Inserting... 

DEBUG2 : enters here 

hashval = 1 
String added successfully 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 1 

Please enter the string :gaurava 

enters in add_string 

DEBUG purpose in hash function: 

str passed = gaurava 
Hashval returned in hash func= 7 
hashval = 7 
enters in lookup_string 

str in lookup_string = gaurava 
DEBUG purpose in hash function: 

str passed = gaurava 
Hashval returned in hash func= 7 
hashval = 7 

DEBUG ERROR :element not found in lookup string 

DEBUG Purpose 

NULL 

Inserting... 

DEBUG1 : enters here 

hashval = 7 
String added successfully 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 4 
Index : i = 1 String = gaura ayu 
Index : i = 7 String = gaurava 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 2 

Please enter the string you want to delete :gaura 

String entered = gaura 
enters in delete_string 

DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 0 
hashval = 0 
enters in lookup_string 

str in lookup_string = gaura 
DEBUG purpose in hash function: 

str passed = gaura 
Hashval returned in hash func= 0 
hashval = 0 

DEBUG ERROR :element not found in lookup string 

DEBUG Purpose 

Item not present. So, cannot be deleted 

Item found in list: Deletion failed 

Press 1 to add an element to the hashtable 

Press 2 to delete an element from the hashtable 

Press 3 to search the hashtable 

Press 4 to view the hashtable 

Press 5 to exit 

Please enter your choice: 
============================================================== 

Моя рутина наклеена ниже:

#include<stdio.h> 
#include<string.h> 

struct list 
{ 
char *string; 
struct list *next; 
}; 

struct hash_table 
{ 
int size;  /* the size of the table */ 
struct list **table; /* the table elements */ 
}; 

struct hash_table * hashtable = NULL; 

struct hash_table *create_hash_table(int size) 
{ 
    struct hash_table *new_table; 
    int i; 

    if (size<1) return NULL; /* invalid size for table */ 

    /* Attempt to allocate memory for the table structure */ 
    if ((new_table = malloc(sizeof(struct hash_table))) == NULL) { 
     return NULL; 
    } 

    /* Attempt to allocate memory for the table itself */ 
    if ((new_table->table = malloc(sizeof(struct list *) * size)) == NULL) { 
     return NULL; 
    } 

    /* Initialize the elements of the table */ 
    for(i=0; i<size; i++) 
    new_table->table[i] = '\0'; 

    /* Set the table's size */ 
    new_table->size = size; 

    return new_table; 
} 


unsigned int hash(struct hash_table *hashtable, char *str) 
{ 
    printf("\n DEBUG purpose in hash function:\n"); 
    printf("\n str passed = %s", str); 

    unsigned int hashval = 0; 
    int i = 0; 

    for(; *str != '\0'; str++) 
    { 
    hashval += str[i]; 
    i++; 
    } 
    hashval = hashval % 10; 
    printf("\n Hashval returned in hash func= %d", hashval); 
    return hashval; 
} 


struct list *lookup_string(struct hash_table *hashtable, char *str) 
{ 
    printf("\n enters in lookup_string \n"); 
    printf("\n str in lookup_string = %s",str); 

    struct list * new_list; 
    unsigned int hashval = hash(hashtable, str); 

    printf("\n hashval = %d \n", hashval); 

    if(hashtable->table[hashval] == NULL) 
    { 
     printf("\n DEBUG ERROR :element not found in lookup string \n"); 
     return NULL; 
    } 

    /* Go to the correct list based on the hash value and see if str is 
    * in the list. If it is, return return a pointer to the list element. 
    * If it isn't, the item isn't in the table, so return NULL. 
    */ 


    for(new_list = hashtable->table[hashval]; new_list != NULL;new_list = new_list->next) 
    { 
     if (strcmp(str, new_list->string) == 0) 
      return new_list; 
    } 
    printf("\n returns NULL in lookup_string \n"); 
    return NULL; 
} 


int add_string(struct hash_table *hashtable, char *str) 
{ 
    printf("\n enters in add_string \n"); 

    struct list *new_list; 
    struct list *current_list; 
    unsigned int hashval = hash(hashtable, str); 
    printf("\n hashval = %d", hashval); 

    /* Attempt to allocate memory for list */ 
    if ((new_list = malloc(sizeof(struct list))) == NULL) 
    { 
    printf("\n enters here \n"); 
    return 1; 
    } 

    /* Does item already exist? */ 
    current_list = lookup_string(hashtable, str); 

    if (current_list == NULL) 
    { 
    printf("\n DEBUG Purpose \n"); 
    printf("\n NULL \n"); 
    } 

    /* item already exists, don't insert it again. */ 
    if (current_list != NULL) 
    { 
    printf("\n Item already present...\n"); 
    return 2; 
    } 

    /* Insert into list */ 
    printf("\n Inserting...\n"); 

    new_list->string = strdup(str); 
    new_list->next = NULL; 
    //new_list->next = hashtable->table[hashval]; 
    if(hashtable->table[hashval] == NULL) 
    { 
     printf("\n DEBUG1 : enters here \n"); 
     printf("\n hashval = %d", hashval); 
     hashtable->table[hashval] = new_list; 
    } 
    else 
    { 
     printf("\n DEBUG2 : enters here \n"); 
     printf("\n hashval = %d", hashval); 
     struct list * temp_list = hashtable->table[hashval]; 
     while(temp_list->next!=NULL) 
     temp_list = temp_list->next; 

     temp_list->next = new_list; 
     // hashtable->table[hashval] = new_list; 
    } 

    return 0; 
} 

int delete_string(struct hash_table *hashtable, char *str) 
{ 
    printf("\n enters in delete_string \n"); 

    struct list *new_list; 
    struct list *current_list; 
    unsigned int hashval = hash(hashtable, str); 
    printf("\n hashval = %d", hashval); 

    /* Does item already exist? */ 
    current_list = lookup_string(hashtable, str); 

    if (current_list == NULL) 
    { 
    printf("\n DEBUG Purpose \n"); 
    printf("\n Item not present. So, cannot be deleted \n"); 
    return 1; 
    } 

    /* item exists, delete it. */ 
    if (current_list != NULL) 
    { 
    struct list * temp = hashtable->table[hashval]; 
    if(strcmp(temp->string,str) == 0) 
    { 
     if(temp->next == NULL) 
     { 
     hashtable->table[hashval] = NULL; 
     free(temp); 
     } 
     else 
     { 
     hashtable->table[hashval] = temp->next; 
     free(temp); 
     } 
    } 
    else 
    { 
     struct list * temp1; 
     while(temp->next != NULL) 
     { 
     temp1 = temp; 

     if(strcmp(temp->string, str) == 0) 
     { 
      break; 
     } 
     else 
     { 
      temp = temp->next; 
     } 
     } 
     if(temp->next == NULL) 
     { 
     temp1->next = NULL; 
     free(temp); 
     } 
     else 
     { 
     temp1->next = temp->next; 
     free(temp); 
     } 
    } 
    } 
    return 0; 
} 

void free_table(struct hash_table *hashtable) 
{ 
    int i; 
    struct list *new_list, *temp_list; 

    if (hashtable==NULL) return; 

    /* Free the memory for every item in the table, including the 
    * strings themselves. 
    */ 
    for(i=0; i<hashtable->size; i++) { 
     new_list = hashtable->table[i]; 
     while(new_list!=NULL) { 
      temp_list = new_list; 
      new_list = new_list->next; 
      free(temp_list->string); 
      free(temp_list); 
     } 
    } 

    /* Free the table itself */ 
    free(hashtable->table); 
    free(hashtable); 
} 

void view_hashtable(struct hash_table * hashtable) 
{ 
    int i = 0; 
    if(hashtable == NULL) 
    return; 

    for(i =0; i < hashtable->size; i++) 
    { 
     if((hashtable->table[i] == 0) || (strcmp(hashtable->table[i]->string, "*") == 0)) 
     { 
      continue; 
     } 
     printf(" Index : i = %d\t String = %s",i, hashtable->table[i]->string); 
     struct list * temp = hashtable->table[i]->next; 
     while(temp != NULL) 
     { 
      printf("\t %s",temp->string); 
      temp = temp->next; 
     } 

     printf("\n"); 
    } 
} 



int main() 
{ 
    hashtable = create_hash_table(10); 
    if(hashtable == NULL) 
    { 
    printf("\n Memory allocation failure during creation of hash table \n"); 
    return 0; 
    } 

    int flag = 1; 

    while(flag) 
    { 
     int choice; 

     printf("\n Press 1 to add an element to the hashtable\n"); 
     printf("\n Press 2 to delete an element from the hashtable\n"); 
     printf("\n Press 3 to search the hashtable\n");   printf("\n Press 4 to view the hashtable\n");    printf("\n Press 5 to exit \n"); 
     printf("\n Please enter your choice: "); 

     scanf("%d",&choice); 

     if(choice == 5) 
     flag = 0; 

     else if(choice == 1) 
     { 
      char str[20]; 
      printf("\n Please enter the string :"); 
      scanf("%s",&str); 
      int i; 
      i = add_string(hashtable,str); 

      if(i == 1) 
      { 
       printf("\n Memory allocation failure:Choice 1 \n"); 
       return 0; 
      } 
      else if(i == 2) 
      { 
       printf("\n String already prsent in hash table : Couldnot add it again\n"); 
       return 0; 
      } 
      else 
      { 
       printf("\n String added successfully \n"); 

      } 
     } 


     else if(choice == 2) 
     { 
      int i; 
      struct list * temp_list; 
      char str[20]; 
      printf("\n Please enter the string you want to delete :"); 
      scanf("%s",&str); 

      printf("\n String entered = %s", str); 

      i = delete_string(hashtable,str); 

      if(i == 0) 
      { 
       printf("\n Item found in list: Deletion success \n"); 
      } 
      else 
       printf("\n Item found in list: Deletion failed \n"); 
     } 


     else if(choice == 3) 
     { 
      struct list * temp_list; 
      char str[20]; 
      printf("\n Please enter the string :"); 
      scanf("%s",&str); 
      temp_list = lookup_string(hashtable,str); 

      if(!temp_list) 
      { 
       printf("\n Item not found in list: Deletion failed \n"); 
       return 0; 
      } 
      printf("\n Item found: Present in Hash Table \n"); 
     } 


     else if(choice == 4) 
     { 
      view_hashtable(hashtable); 
     } 
     else if(choice == 5) 
     { 
      printf("\n Exiting ...."); 
      return 0; 
     } 
     else 
     printf("\n Invalid choice:"); 
    }; 

    free_table(hashtable); 
    return 0; 
} 

Answer 1

Ваш хэш-функция проходит мимо конца строки, просто сделать, например,

for(; *str != '\0'; str++) 
{ 
hashval += *str; 

}