-2

我正在尝试实现Fowler–Noll–Vo 哈希函数

伪代码看起来像这样

  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

关于如何解决此问题的任何建议

4

2 回答 2

0

这就是问题：

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？

于 2015-09-18T22:58:26.533 回答
0

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也这么说

于 2015-09-19T00:25:08.187 回答