SuperFastHash возвращает разные хэши для одинаковых строк, но только тогда, когда определяется различными вызовами функций

Question

Итак, моя SFH функция:

/* 
* Hash function (found at: 'http://www.azillionmonkeys.com/qed/hash.html') 
*/ 
int32_t SuperFastHash(const char * data, int len) { 
    uint32_t hash = len, tmp; 
    int rem; 

    if (len <= 0 || data == NULL) return 0; 

    rem = len & 3; 
    len >>= 2; 

    /* Main loop */ 
    for (;len > 0; len--) { 
     hash += get16bits (data); 
     tmp = (get16bits (data+2) << 11)^hash; 
     hash = (hash << 16)^tmp; 
     data += 2*sizeof (uint16_t); 
     hash += hash >> 11; 
    } 

    /* Handle end cases */ 
    switch (rem) { 
     case 3: hash += get16bits (data); 
       hash ^= hash << 16; 
       hash ^= ((signed char)data[sizeof (uint16_t)]) << 18; 
       hash += hash >> 11; 
       break; 
     case 2: hash += get16bits (data); 
       hash ^= hash << 11; 
       hash += hash >> 17; 
       break; 
     case 1: hash += (signed char)*data; 
       hash ^= hash << 10; 
       hash += hash >> 1; 
    } 

    /* Force "avalanching" of final 127 bits */ 
    hash ^= hash << 3; 
    hash += hash >> 5; 
    hash ^= hash << 4; 
    hash += hash >> 17; 
    hash ^= hash << 25; 
    hash += hash >> 6; 

    // Limits hashes to be within the hash table  
    return hash % HT_LENGTH; 
} 

Похоже, это работает отлично, (и это должно, так как все, но последняя строка нетронутый мной).

Вот функция, в которой я загружаю словарь в хэш-таблицу, которая также, похоже, работает денди.

bool load(const char* dictionary) 
{ 
    // declares file pointer 
    FILE* dictptr = fopen(dictionary, "r"); 

    // declare temp index 
    uint32_t index = 0; 

    // read words, one by one 
    while(true) 
    { 

     // malloc node 
     node* new_node = malloc(node_size); 

     // insert word into node, if fscanf couldn't scan word; we're done 
     if (fscanf(dictptr, "%s", new_node->word) != 1) 
     { 
      return true; 
     } 

     // hash word - HASH FUNCTION CALL - 
     index = SuperFastHash(&new_node->word[0], sizeof(new_node->word)); 

     // check if head node has been assigned with value 
     if (!strcmp(hashtable[index].word,"")) 
     { 
      // declare hashtable[index] to new_node 
      hashtable[index] = *new_node; 

      //increment size 
      hashtablesize++; 
     } 

     else 
     { 
      // if node is initialized, insert after head 
      new_node->next = hashtable[index].next; 
      hashtable[index].next = new_node; 

      //increment size 
      hashtablesize++; 
     } 
    } 
} 

И, наконец, моя функция проверки, которая проверяет слово на хэш-таблицу.

bool check(const char* keyword) 
{ 

    // gets index from SFH 
    uint32_t index = SuperFastHash(keyword, sizeof(keyword)); 

    // declares head pointer to the pointer of the index'd element of hashtable 
    node* head = &hashtable[index]; 

    // if word of head is equal to keyword, return true 
    // else continue down chain till head is null or key is found 
    while (head != NULL) 
    { 
     if (!strcmp(head->word, keyword)) 
     { 
      return true; 
     } 
     head = head->next; 
    } 
    return false; 
} 

ПРИМЕЧАНИЕ: При использовании другого хеш-функции все работает отлично, так что я подозреваю, что проблема проживать с лена аргументом или фактической функции ВДМ.

Я проверил с lldb, что индекс, возвращаемый для, скажем, «cat», не равен индексу, в котором «cat» находится в хэш-таблице. То есть индекс, возвращаемый вызовом функции в нагрузке.

Answer 1

Несколько вещей ...

1. Как комментатора упоминалось, используя sizeof() не даст вам правильную длину строки. Например, изменить

   index = SuperFastHash(&new_node->word[0], sizeof(new_node->word)); 
   

   в

   index = SuperFastHash(&new_node->word[0], strlen(new_node->word)); 
   

2. Вы не в состоянии назвать fclose() после прочтения вашего файла словаря. Если fopen() удастся, вы должны позвонить fclose().

3. Следующий код выглядит немного подозрительно:

   // check if head node has been assigned with value 
   if (!strcmp(hashtable[index].word,"")) 
   { 
       // declare hashtable[index] to new_node 
       hashtable[index] = *new_node; 
   
       //increment size 
       hashtablesize++; 
   } 
   

Если хеш-таблица полностью инициализирован в начале, вы должны увеличивать hashtablesize? Если хеш-таблица не полностью инициализирована, то вызов strcmp() для записей, которые еще не инициализированы, является потенциальной проблемой. Вы не указали код объявления или инициализации, поэтому на 100% не ясно, действительно ли это проблема, но может быть что-то двойное.