Как я могу считать столкновения в этой хэш-функции? - PullRequest
Новая
       59

Как я могу считать столкновения в этой хэш-функции?

0 голосов
/ 06 декабря 2011

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

int HashTable_qp::preHash(string & key, int tableSize )
{
    string pad = "AA";
    //some words in the input are less than 3 letters
    //I choose to pad the string with A because all padded characters 
    //have same ascii val, which is low, and will hopefully alter the results less
    if (key.length() < 3)
    {
        key.append(pad);
    }
    return ( key[0] + 27 * key[1] + 729 * key[2] ) % tableSize;
}

Ответы [ 3 ]

1 голос
/ 06 декабря 2011

Если это массив в качестве базовой структуры данных, сделайте: int hash = preHash(&key, array.length); if(array[hash] != null) this.count++; Если это массив связанных списков, выполните: 

if(array[hash] != null && *(array[hash]) != null)
this.count++

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

1 голос
/ 06 декабря 2011

создать гистограмму: 

 unsigned histogram[tablesize] = {0};

генерирует некоторые (все) возможные строки и вычисляет их hashval, и соответственно обновляет гистограмму: 

for(iter=0; iter < somevalue; iter++) {
 hashval = hashfunc( string.iterate(iter) ); // I don't know c++
 histogram[hashval] +=1;
 }

Теперь вам нужно проанализировать хеш-таблицу для кусков / кластеров. Основное правило таково, что для (tablesize==iter) вы ожидаете около 30% ячеек с числом = 1 и около 30% пустых; у остальных есть два или больше.

Если вы сложите все (count*(count+1))/2 и поделите на размер таблицы, вы должны ожидать около 1,5. Плохая хэш-функция дает более высокие значения, а идеальный хеш-код будет иметь только ячейки с числом = 1 (и, следовательно, с отношением = 1). При линейном зондировании вы, конечно, никогда не должны использовать tableize = niter, но увеличивать размер таблицы, скажем, в два раза. Вы можете использовать ту же метрику (количество проб / число записей), чтобы проанализировать ее производительность.

ОБНОВЛЕНИЕ: отличное введение в хэш-функции и их производительность можно найти по адресу http://www.strchr.com/hash_functions.

0 голосов
/ 06 декабря 2011

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

[0] -> 13
[1] -> 5
[2] -> 12
[3] -> 7
[4] -> 5

Для каждого элемента i в 0..n , отметьте элементы i + 1..n для матчей.На английском языке это будет: проверьте, равен ли каждый элемент любому из элементов после it.

...