Как я могу хешировать строку к интервалу с помощью C++?
Я должен записать свою собственную хеш-функцию. Если я хотел просто сделать простую хеш-функцию, которая отображает каждую букву в строке к численному значению (т.е. a=1, b=2, c=3...), там способ, которым я могу выполнить этот хеш на строке, не имея необходимость сначала преобразовывать его в струну до для рассмотрения каждого отдельного символа? Существует ли более эффективный способ хешировать строки?
5 ответов
Повторите первый вопрос, например, например:
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 ++ в соответствии с приведенным выше фрагментом).
Вы можете изучить каждый отдельный символ из std :: string с использованием оператора [] . Тем не менее, вы можете посмотреть Boost :: Functional / Hash , чтобы узнать о лучшей схеме хеширования. Также имеется список хеш-функций в c, расположенный здесь .
Вы можете использовать функции-члены operator[] или at класса string или итераторы для доступа к отдельным символам строкового объекта без преобразования его в массив char в стиле c.
Для хэширования строкового объекта в целое число вам придется обращаться к каждому отдельному символу строкового объекта, что можно сделать так:
for (i=0; i < str.length(); i++) {
// use str[i] or str.at(i) to access ith element.
}
#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;
}