Границы настроек по алгоритму хэша

Достаточно ли добавить % tableSize; в конец хеш-функции, чтобы гарантировать, что вы используете всю доступную память, но не превышаете ее?Границы настроек по алгоритму хэша

EG:

Я использую следующую функцию из библиотеки GeneralHashFunctions

unsigned int DJBHash(const std::string& str) 
{ 
    unsigned int hash = 5381; 

    for(std::size_t i = 0; i < str.length(); i++) 
    { 
     hash = ((hash << 5) + hash) + str[i]; 
    } 

    return hash; 
}

Это, как представляется, в моей программе:

unsigned int Hash::hash(string key) 
{ 
    unsigned int hash = 5381; 

    for(size_t i = 0; i < key.length(); i++) { 
     hash = (((hash << 5) + hash) + key[i]); 
    } 

    return hash % tableSize; 
}

Будет ли это делать то, что мне нужно это делать, или есть другие изменения, которые мне нужно сделать?

источник

2014-11-25 user3776749

Операция modulo должна выполняться после вычисления хэша, а не во время. Функция фактически не возвращает хэш данной строки, а имя вашей функции лежит. – BlamKiwi

Исправлено, спасибо. Я не знаю, почему я этого не видел. Наверное, я только что занимался этим так долго, что начал читать то, что знаю, код «должен» делать, а не то, что он делает. Время, чтобы выйти из доски и начать отслеживать вещи. Еще раз спасибо. – user3776749

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

Худшее, что может случиться, это то, что ваша функция хэша возвращает значение не намного больше, чем tableSize. Например, если максимальное значение равно tableSize+1, то первое ведро будет в два раза более вероятным. Если максимальное значение равно tableSize*2 - 1, последнее ведро пополам. Это только проблема с производительностью. Кроме того, вряд ли это повредит этот конкретный случай - на системах, где unsigned int - 16 бит, у вас всегда будут проблемы с производительностью с 32000 + строками в вашей хеш-таблице.

источник

2014-11-26 09:14:41 MSalters

Границы настроек по алгоритму хэша

ответ

Смежные вопросы