Создание лучшей хэш-функции - PullRequest
Новая
       19

Создание лучшей хэш-функции

0 голосов
/ 21 марта 2011 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

class Item {
public:
    Item(const string & v): value(v), next(0) { }
    string value;
    Item * next;
};

int hash_function(const string & s)
{
    unsigned int hashval = 0;
    int i = s.length();
    while (i > 0)
{
        hashval += s[--i];
}       
return hashval%101;
}

main()
{
    string name;
    int index;
    Item * p;

    vector<Item *> bucket(101);

    for (index = 0; index < 101; index++)
        bucket[index] = 0;

    while (cin >> name) {
        p = new Item(name);
        index = hash_function(name);

        // push front
        if (bucket[index] != 0)
            p->next = bucket[index];
        bucket[index] = p;
    }

    for (index = 0; index < 101; index++)
        if (bucket[index] != 0) {
            cout << setw(3) << index << ": ";
            p = bucket[index];
            while (p != 0) {
                cout << p->value << " ";
                p = p->next;
            }
            cout << endl;
        }

    Item * temp;
    for (index = 0; index < 101; index++) {
        p = bucket[index];
        while (p != 0) {
            temp = p;
            p = p->next;
            delete temp;
        }
    }
}

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

Вот пример ввода / вывода: 

Alice
Amy  
Barry
Carrie
David
Garret 
Edward
Henry
Ingrid
Fred
 65: Amy Alice 
 66: Barry 
 67: Carrie 
 68: David 
 69: Edward 
 70: Fred 
 71: Garret 
 72: Henry 
 73: Ingrid

Что я могу добавить в свой алгоритм, который позволит Эмиа Алису положили в собственное ведро?

Ответы [ 4 ]

8 голосов
/ 21 марта 2011

Ваша функция hash_function на самом деле не возвращает значение.Вы должны обращать больше внимания на предупреждения вашего компилятора!

Очевидно, что это имеет эффект возврата первого символа в строке.Это чисто произвольно.На другой платформе он всегда может вернуть ноль или привести к взрыву вашего компьютера.(Вероятно, на самом деле не последний.)

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

1 голос
/ 21 марта 2011

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

Вот небольшая улучшенная версия: 

int hash_function(const string & s)
{
    double hashval = 0;
    int i = s.length();
    double weight = 1.0;
    while (i > 0)
    {
        hashval +=  weight * s[--i];
        weight *= 1.5;
    }       
    return (int) hashval;
}

Если предположить, что строка s не слишком длинная, в противном случае произойдет переполнение!

0 голосов
/ 21 марта 2011

Попробуйте по-разному взвешивать разные буквы. В вашей текущей реализации (при условии, что это работает, как упомянуто выше), имя ab будет иметь хэш того же значения, что и ba. Что-то вроде: 

for (int i = 0 to str.len())
    hash = hash + hash + str[i]

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

0 голосов
/ 21 марта 2011

Проверьте это (предложено Google sparsehash): Боб Дженкинс: http://burtleburtle.net/bob/hash/ или Пол Се: http://www.azillionmonkeys.com/qed/hash.html

...