Может ли кто-нибудь сказать, что делает 4-я строка в этой функции!

Вопрос:

 size_t hash(const std::string data) {
    size_t h(0);
    for (int i=0; i<data.length(); i  ){
        h = (h << (31-i) ^ (h >> i) ^ data[i]);
    }
    h = h%hashsize;
    return h;
}

1. Ну, я бы сказал, что в ней есть ошибка. То, что «31» и size_t используются вместе, означает, что, вероятно, смешивание происходит не так, как предполагалось.

2. Это потребует много работы с карандашом и бумагой. Каков контекст вызова функции?

3. я нашел это где-то в сети и не понимаю этого h = (h << (31-i) ^ (h >> i) ^ data[i]);

4. @ohmantics: Да. Вероятно, это должно что-то сделать с sizeof (size_t) и CHAR_BIT.

5. @zombie : Если конкретно эта часть вас смущает, то заголовок вашего вопроса сформулирован крайне неудачно.

Ответ №1:

Это хэш-функция для std::string , якобы подходящая для TR1 и C 11 std::unordered_map<> , std::unordered_set<> и т.д. Т.Е. она пытается создать как можно более уникальное size_t значение для данного std::string для использования в хэш-таблицах.

При этом это плохая хэш-функция. Любая реализация стандартной библиотеки, которая поставляется с unordered_map<> , unordered_set<> и т.д. будет поставляться со встроенными хэш-функциями для стандартных библиотечных строк, которые имеют лучшие реализации, чем эта.

РЕДАКТИРОВАТЬ: (В ответ на комментарий) << — побитовый сдвиг влево, >> — побитовый сдвиг вправо и ^ — побитовый XOR, все из которых кратко обсуждаются в этой статье Википедии: Побитовая операция.

1. итак .. вы хотите сказать, что это создаст уникальное целое число без знака для этой строки! я прав?

2. @zombie : Не уникальный, но максимально уникальный — существует слишком много возможных строковых значений, чтобы получить действительно уникальное целое число для каждого из них, учитывая только 32/64 бита памяти (на большинстве платформ). Но да, это идея.