Может кто-нибудь проверить, правильно ли я делаю это хэширование
Я пытаюсь сделать реализацию Хеш-функция Фаулера – Нолла – Во
Псевдокод выглядит так
hash = FNV_offset_basis
for each byte_of_data to be hashed
hash = hash × FNV_prime
hash = hash XOR byte_of_data
return hash
Это мой код для этого
uint8_t byte_of_data;
uint16_t hash;
uint16_t FNV_offset_basis;
uint16_t FNV_prime;
void computeHash(std::string p)
{
FNV_offset_basis = 0xcbf29ce484222325;
FNV_prime = 0x100000001b3;
hash = FNV_offset_basis;
//Iterate through the string
for(int i=0 ; i<p.size();i++)
{
hash = hash * FNV_prime;
hash = hash ^ p.at(i);
}
std::cout << hash; //output 2983
std::cout << std::hex << hash ; //ba7
}
Теперь я использую это как это
int main()
{
computeHash("Hello");
}
Я проверяю свой результат Вот и я получаю результат как 0d47307150c412cf
Обновить:
Я исправил свои типы в
uint8_t byte_of_data;
uint64_t hash;
uint64_t FNV_offset_basis;
uint64_t FNV_prime;
и я получаю результат fa365282a44c0ba7, который все еще не соответствует результату
0d47307150c412cf
Любые предложения о том, как я могу это исправить
Решение
Ваш текущий результат fa365282a44c0ba7 правильно в соответствии с официальной ссылкой
Исходный код (в C) и ручной расчет тоже … это делает тестовый сайт неправильным.
Ссылочные исходные файлы связаны между собой Вот: C файл а также H файл
Я удалил включает в себя longlong.h и добавил следующие две части кода:
/*before the reference code*/
#include <stdint.h>
#define HAVE_64BIT_LONG_LONG
typedef uint64_t u_int64_t;
typedef uint32_t u_int32_t;
/*after it*/
#include<stdio.h>
int main()
{
printf("%llx\n", fnv_64_str("Hello", FNV1_64_INIT));
}
чтобы сделать его компиляцией с gcc -std=c11 source.c
(gcc (i686-posix-sjlj-rev0, Built by MinGW-W64 project) 4.9.1)
Выход: fa365282a44c0ba7,
И Ideone тоже так говорит
Другие решения
Это проблема:
uint16_t FNV_offset_basis;
uint16_t FNV_prime;
void computeHash(std::string p)
{
FNV_offset_basis = 0xcbf29ce484222325;
FNV_prime = 0x100000001b3;
FNV_prime а также FNV_offset_basis оба являются 16-битными целыми числами в вашем коде, но необъяснимо, что вы присваиваете им длинные 64-битные целые числа, ваш компилятор C ++ должен предупреждать вас о неправильном литеральном присваивании.
Что произойдет, если вы измените типы на uint64_t?