Как я могу хэшировать строку в int, используя c ++?

Question

Я должен написать свою собственную хэш-функцию. Если бы я хотел просто создать простую хэш-функцию, которая отображает каждую букву в строке на числовое значение (то есть a = 1, b = 2, c = 3, ...), есть ли способ выполнить этот хэш на строка без необходимости сначала преобразовывать ее в c-строку, чтобы посмотреть на каждый отдельный символ? Есть ли более эффективный способ хеширования строк?

Answer 1

Из личного опыта я знаю, что это работает и производит хорошие дистрибутивы. (Плагиат от http://www.cse.yorku.ca/~oz/hash.html):

djb2

этот алгоритм (k = 33) был впервые описан Даном Бернштейном много лет назад в comp.lang.c. другая версия этого алгоритма (теперь одобренная Бернштейном) использует xor: hash (i) = hash (i - 1) * 33 ^ str [i]; магия числа 33 (почему она работает лучше, чем многие другие константы, простые или нет) никогда должным образом не объяснялась.

unsigned long hash(unsigned char *str) {
    unsigned long hash = 5381;
    int c;

    while (c = *str++) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }

    return hash;
}

Answer 2

По первому вопросу, например, что-то вроде:

int hash = 0;
int offset = 'a' - 1;
for(string::const_iterator it=s.begin(); it!=s.end(); ++it) {
  hash = hash << 1 | (*it - offset);
}

Что касается второго, есть много лучших способов хеширования строк. Например, см. здесь для нескольких примеров C (легко переводимых на C ++ по приведенным выше фрагментам).

Answer 3

Вот хеш-функция C (++), которую я нашел в книге Страуструпа:

int hash(const char *str)
{
    int h = 0;
    while (*str)
       h = h << 1 ^ *str++;
    return h;
}

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

    return (h > 0 ? h : -h) % N_BUCKETS;

для последней строки.

Answer 4

Вы можете проверить каждый отдельный символ из std :: string с помощью оператора []. Тем не менее, вы можете посмотреть на Boost :: Functional / Hash для получения рекомендаций по лучшей схеме хеширования. Существует также список хэширующих функций в c, расположенных здесь .

Answer 5

C ++ 11 поставляется со стандартной функцией хеширования для строк.

https://en.cppreference.com/w/cpp/string/basic_string/hash

#include <string>
#include<functional> // hash
int main(){
    std::string s = "Hello";
    std::size_t hash = std::hash<std::string>{}(s);
}

Answer 6

Еще один способ для небольших струн:

int hash(const char* str) {
    int hash = 0;
    int c = 0;

    while (c < std::strlen(str)) {
        hash += (int)str[c] << (int)str[c+1];
        c++;
    }
    return hash;
}

Answer 7

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// a variation on dan bernstein's algorithm
// [http://www.cse.yorku.ca/~oz/hash.html]
template<typename Int>
struct hash {
    hash() : acc(5381) { }
    template<typename Ch>
    void operator()(Ch ch) { acc = ((acc << 5) + acc) ^ ch; }
    operator Int() const { return acc; }
    Int acc;
};

int main(int argc, char* argv[])
{
    string s("Hellp, world");
    cout << hex << showbase
        << for_each(s.begin(), s.end(), hash<unsigned long long>()) << '\n';
    return 0;
}

Answer 8

xor символов вместе, четыре за один раз.

Answer 9

Вы можете использовать функции-члены operator [] или в строкового класса или итераторов для доступа к индивидуальному char строкового объекта без преобразования его в char в стиле c массив.

Для хеширования строкового объекта в целое число вам необходимо получить доступ к каждому отдельному символу строкового объекта, который вы можете сделать так:

for (i=0; i < str.length(); i++) {
    // use str[i] or str.at(i) to access ith element.
}