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

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

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;
}

c++ prefix hash hash-collision
person user977154    schedule 05.12.2011    source источник
comment
создать гистограмму без знака [tablesize], сгенерировать некоторые (все) возможные строки и вычислить их хэш-значение, и соответствующим образом обновить гистограмму histogram[hashval] +=1;   -  person wildplasser    schedule 06.12.2011
comment
@wildplasser, это был бы самый простой способ. Мой ответ будет быстрее. Если это не критично для производительности, я бы выбрал идею wild's. (Возможно, вам следует опубликовать это как ответ, чтобы помочь другим найти его, когда они найдут эту страницу.)   -  person Brigand    schedule 06.12.2011

Ответы (3)


arrow_upward
1
arrow_downward

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

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

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

person Alexander Wood    schedule 05.12.2011
comment
я использую stl, можете ли вы показать мне, как это будет выглядеть с учетом stl. - person user977154; 06.12.2011
comment
Самый простой способ - наследовать его и переопределить его вызов: HashTable_qt::PreHash в производном классе, но создать экземпляр производного класса и присвоить ему значение и дать производному классу переменную поля с именем CollisionCount, и прежде чем добавить новое значение, инициализируйте его 0 и после его вызова, и оно должно иметь новое значение, если больше 1 функция была вызвана с новым ключом - person Alexander Wood; 07.12.2011
comment
int Prehash(string & key, int tableSize) { HashMap_qt::Prehash(key, tablesize); Счетчик столкновений++; } в основной HashTable_qt2* map = new HashMap_qt2() map.CollisionCount = 0; карта.Добавить(...); cout ‹‹ map.CollisionCount; - person Alexander Wood; 07.12.2011

arrow_upward
1
arrow_downward

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

 unsigned histogram[tablesize] = {0};

сгенерировать некоторые (все) возможные строки и вычислить их хэш-значение и соответствующим образом обновить гистограмму:

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

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

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

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

person wildplasser    schedule 06.12.2011

arrow_upward
0
arrow_downward

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

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

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

person Brigand    schedule 05.12.2011