Функция хэша не дает желаемых результатов

Question

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

Выход:

key[148]:val[joy] 
key[174]:val[jam] 
key[294]:val[paula] 
key[13]:val[ulrich] 
key[174]:val[cat] 
key[174]:val[act] 
key[148]:val[yoj] 
key[265]:val[vij] 
key[265]:val[jiv] 

Здесь ключевое значение 174 отлично подходит для строк act и cat (анаграммы), но то же самое нельзя ожидать с jam.

Ниже приведен фрагмент кода.

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

unsigned long hash(char *str, size_t size) { 
    unsigned long hash_val = 5381; 
    unsigned long sum = 0; 
    char *val; 
    int i, j; 
    for (j = 0; j < 9; j++) { 
     val = malloc(strlen(str) + 1); 
     memset(val, '\0', strlen(str) + 1); 
     strcpy(val, str); 

     for (i = 0; val[i] != '\0'; i++) { 
      sum = sum + val[i]; 
     } 
     return size % sum; 
    } 
} 

int main() { 
    int i; 
    char *str[9] = { "joy", "jam", "paula", "ulrich","cat", "act","yoj", "vij", "jiv" }; 
    unsigned long key; 
    size_t size = 4542; // it may be anything just for test it is being used 
    for (i = 0; i < 9; i++) { 
     key = hash(str[i], size); 
     printf("\nkey[%ld]:val[%s]", key, str[i]); 
    } 
    return 1; 
} 

Answer 1

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

Проблема в том, что сумма кодов ASCII 'c' + 'a' + 't' равна 'j' + 'a' + 'm' (равна 312), поэтому вы получаете то же самое значение для вашего «хеша».

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

Для другого метода вы можете вычислить количество появлений каждой буквы в строке (гистограмме) и хеш (или просто сохранить как есть) вместо них.

Я рекомендую вам провести некоторое исследование по этой теме, поскольку это очень распространенная задача.

Кроме того, вы можете просто отсортировать строки и позволить unordered_set<string> выполнить эту работу за вас.

Answer 2

но такого же нельзя ожидать с замятием.

Ну, там вы ошибаетесь. Давайте посмотрим на ваш алго. То, что вы делаете, в основном суммирует значение ASCII элементов строк и возвращает результат модуля фиксированного значения, взятого относительно суммы.

разработать в соответствии с ASCII table,

j == 106 
a == 97 
m == 109 

и

c == 99 
a == 97 
t == 116 

Оба слова в конечном итоге, результат суммы 312. Теперь в соответствии с вашим алгоритмом,

4542 % 312 

предполагает, чтобы дать постоянной значения а, верно? Это то, что он дает.

Теперь, не "sad", а

s == 115 
a ==97 
d == 100 

, который также поставляется с 312.

Это, я вижу, у вас есть локальная переменная unsigned long hash_val = 5381;, определенная внутри вашей функции, но используемая в никуда.

Answer 3

Ваш хэш-функция имеет много проблем:

• Петля for (j = 0; j < 9; j++) совершенно бесполезно.
• Совершенно неадекватно выделять память для копии строки и забыть ее освободить! Просто используйте строку напрямую.
• Вы суммируете метод слишком много легких столкновений, как вы диагностировали: анаграммы производят одну и ту же сумму, но и много простых слов. Вы должны перетасовать сумму до того, как будет добавлено значение каждого символа.
• return size % sum; должно действительно быть return sum % size;, поэтому возвращаемое значение может использоваться как индекс в хеш-таблице размера size. На самом деле, size % sum будет вызывать неопределенное поведение, если sum произошло с вычислением до 0, что потребует очень длинную строку (> 16 МБ), но это возможно.

Вот улучшенный хэш-функция:

#include <limits.h> 

// constraints: str != NULL, size > 0 
size_t hash(const char *str, size_t size) { 
    size_t sum = 5381; // initial salt 
    while (*str != '\0') { 
     // rotate the current sum 2 places to the left 
     sum = (sum << 2) | (sum >> (CHAR_BIT * sizeof(sum) - 2)); 
     // add the next character value 
     sum += (unsigned char)*str++; 
    } 
    return sum % size; 
}