какое хеширование я должен использовать для генерации случайных значений из набора строк - PullRequest
Новая
       22

какое хеширование я должен использовать для генерации случайных значений из набора строк

1 голос
/ 07 марта 2012

У меня есть массив отпечатков пальцев в хэш-ведрах.Я хотел бы вставить в ведро и искать по нему без перехода от записи 0 до записи n.

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

Вот код, который я использовал для хеширования отпечатков пальцев в ведрах.Я пытался использовать один и тот же код с большим количеством символов, но он все еще дает мне большую коллизию.

he.fingerprint - 33 символа в ширину

количество блоков - 1024

количество записей в каждом блоке - 2048 

    char hph[32];
int bk,en;
unsigned long h = 0, g,i=0;
int j=0;
strncpy(hph,(const char*)(he).fing_print,32);

while ( j<32 ) 
{
    h  =h + hph[j]++;
     g = h & 0xFFf00000;
    h ^= g >> 24;
    h &= ~g;
    j++;
}
bk=h%buckets;
en=h%entries_per_bk;

1 Ответ

3 голосов
/ 07 марта 2012

В вашей функции хеширования есть некоторые лишние вещи. 

char hph[32];
int bk,en;
unsigned long h = 0, g,i=0;
int j=0;
strncpy(hph,(const char*)(he).fing_print,32);

while ( j<32 ) 
{
    h = h + hph[j]++;

Это, по сути, h += hph[j];.Символ с индексом j увеличивается, но, поскольку он больше никогда не используется, это никак не влияет на хеш.Возможно, вы хотите прекремнировать это?Но это не сильно изменится. 

    g = h & 0xFFf00000;

Длина отпечатка пальца (или, по крайней мере, той его части, которую вы используете) составляет максимум 32 символа.Каждый из этих символов меньше 256, поэтому общая сумма меньше 32*256 = 8192 = 0x2000, следовательно, h & 0xFFF00000 равно 0. Таким образом, следующие две строки ничего не делают для h.

    h ^= g >> 24;
    h &= ~g;
    j++;
}
bk=h%buckets;
en=h%entries_per_bk;

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

h = 0;
for(j = 0; j < 32; ++j)
    h = prime*h + hph[j];

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

...