Хэш-функция для уменьшения количества коллизий - PullRequest
Новая
       44

Хэш-функция для уменьшения количества коллизий

0 голосов
/ 12 октября 2018

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

int hash(char* s)
{
    int hash = 0;
    while(*s)
    {
        hash = hash + *s;
        s++;
    }
    return hash;
}

Ответы [ 3 ]

0 голосов
/ 12 октября 2018

Хэш "foo bar" и "bar foo" с одинаковым значением, верно?Реализуйте его таким образом, чтобы значение ascii и его положение в строке использовались для вычисления хэша, я наивно полагаю, что это значительно уменьшит коллизию. 

int hash(char* s)
{
    int hash = 0;
    int pos = 0;
    while(*s)
    {
        pos++;
        hash += (*s * pos);
        s++;
    }
    return hash;
}

Попробуйте и посмотрите, поможет ли это.У меня нет много теоретических знаний за этот ответ.

РЕДАКТИРОВАТЬ * как упомянуто ниже, вы, вероятно, захотите, чтобы хеш был беззнаковым целым.Я проверил это на codechef.com, вот источник и результаты: 

#include <stdio.h>

unsigned int hash(char* s);
unsigned int hash2(char* s);

int main(void) {
    unsigned int temp1 = hash("foo bar");
    unsigned int temp2 = hash("bar foo");

    printf("temp1 is %d and temp2 is %d\n",temp1, temp2);

    temp1 = hash2("foo bar");
    temp2 = hash2("bar foo");

    printf("temp1 is %d and temp2 is %d\n",temp1, temp2);

    return 0;
}

unsigned int hash(char* s)
{
    unsigned int hash = 0;
    while(*s)
    {
        hash = hash + *s;
        s++;
    }
    return hash;
}

unsigned int hash2(char* s)
{
    unsigned int hash = 0;
    int pos = 0;
    while(*s)
    {
        pos++;
        hash += (*s * pos);
        s++;
    }
    return hash;
}

С выводом:

temp1 равен 665 и temp2 равен 665

temp1 равен 2655и temp2 составляет 2715

0 голосов
/ 12 октября 2018

Да, ваша функция "хэш" будет иметь коллизии для строк, которые состоят из одних и тех же букв, например, "безопасность рельса" и "сказки".Это потому, что вы используете только сложение, которое является коммутативным.

Вы можете использовать что-то вроде этого, которое включает в качестве простого числа фактор.

unsigned long int hashBetter(const char* s)
{
    unsigned long int hash = 1234567890ul;
    while(*s)
    {
        hash = (*s + hash) * 4294967291ul;
        s++;
    }
    return hash;
}

Или вы используете CRC, который широко распространяет входные данные в пределах допустимого диапазона возможных значений хеш-функции: 

unsigned long int hashGood(const char* s)
{
    unsigned long int hash = 1234567890ul;
    while(*s)
    {
        hash = crc(hash, *s);
        s++;
    }
    return hash;
}
0 голосов
/ 12 октября 2018

32-битный int имеет диапазон более 4 миллиардов.(Если ваши int s 64-битные, диапазон намного больше.) Но ваш код просто складывает значения каждого символа в строке, и он никогда не достигнет верхнего диапазона.Все ваши хеш-коды будут меньшими числами, сгущая нижний предел возможных значений и увеличивая вероятность коллизий.

Вот почему хороший алгоритм будет более сложным, чем этот.

Вот одна статья , которая появилась в быстром поиске Google.

...