-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;

そして、まだ結果0d47307150c412cfと一致しない結果fa365282a44c0ba7を取得します

これを修正する方法についての提案

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

現在の結果は、公式の参照 ソース コード (C) と手動計算fa365282a44c0ba7によると正しいです... これにより、テスト サイトが間違っています。

参照ソース ファイルはここにリンクされています: C ファイルとH ファイル
のインクルード を削除し、longlong.h代わりに次の 2 つのコード部分を追加しました。 

/*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.
イデオネもそう言ってる

于 2015-09-19T00:25:08.187 に答える