javascript - JS骗我吗？想要在 C 中实现与 Javascript 中相同的哈希值

Question

我在 Javascript 中有一个函数，可以从字符串生成哈希值，在 PHP 中有相同的函数并生成相同的值，但在 C 中却没有。我猜这与类型有关，但不知道如何解决这个问题。我花了几个小时在这上面。

<小时/>

javascript函数很简单，(我认为是从Java复制的):

function getHashCode(s)
{
 var hash=0,c=(typeof s === 'string')?s.length:0,i=0;

 while(i<c) 
  { hash = ((hash<<5)-hash)+s.charCodeAt(i++); }

 return ( hash < 0 )?((hash*-1)+0xFFFFFFFF):hash; /* convert to unsigned int */
}

C 版本(已经混淆了某些类型，但无法正确处理):

uint64_t getHashCode( const char* s )
{
 int16_t  iLen  = strlen( s );
 int16_t  i     = 0;
 int32_t  hash  = 0;

 while( i < iLen ) 
  { 
     // hash<<5 = multiply by 32
    hash = ((hash<<5)-hash)+(uint8_t)s[i++]; 
  }

 return (( hash < 0 )?((hash*-1)+0xFFFFFFFF):hash); //convert to unsigned 
}

我使用的示例字符串:

"M:/Mijn Muziek/Various Artists/Revs & ElBee - Tell It To My Heart.mp3"

在应用新的哈希值后(在 while 循环中)添加一些调试输出后，我得到了这个表:

C/C++               JS
---------------         -----------------
77                  77
2445                2445
75842               75842
2351179             2351179
72886654            72886654
-2035480916         -2035480916
1324601154          1324601154
-1887037154         -1887037154
1631390447          1631390447
-966503578          -966503578
103160276           103160276
-1096998635         -1096998635
352780784           352780784
-1948697477         -1948697477
-280079596          4014887700      <- DIFFERENT!
-92532798           -4387500094     | (and all after this)
1426450655          5721417951      |
1270297459          -7319637133     |
724515670            9314450262     \/
985149401           -7604785191
474860476            9064795068
1835772983          -11049128905
1074387657           9664322249
-1053720936         -9643655528
1694389466           10284324058
986466010           -11898435878
515675343            13400577231
-1193933436          -14078835324
1642769264           14527671152
-613760253          -13498662141
-1846698612          15333170572
-1413082042          -14297983930
-855870241           16323998943
-762173577           -17942042761
2142423004           19322292188
1990603716          -19484232764
1579173090           18759042274
1709725566          -19765110914
1461885063           18641754247
-1926203195         -19106072379
417243165            17597112349
49636328        -17130232856
1538726269      18718595453
455874115       -16723995069
1247195722      18427064906
8361750             -17171507434
259214334       17439083518
-554290137      -17734159321
-3124955        17176744229
-96873497       -17276742681
1291888921      18471758105
1393850960      -20080985520
259706916       21734543396
-539020164      -22013856644
470244184       21945080664
1692667927      -24077135849
933098217       22407934697
-1138726268     -22613562748
-940775819      20534060661
900720715       -20574115765
-2142428835     19332407645
-1990784344     -19170653528
-1584772423     19890064057
-1883304743     -19063173927
1747095227      18926964411
-1674622765     -18854491949
-373698054      16806171130
1300262326      -15879606858
1653426493      14538328381

<小时/>

我该怎么做才能在 C 语言中得到正确的结果？尝试“增加”类型但给出了截然不同的结果。 JS 是否有根据值或其他内容更改其类型的技巧？任何人都可以解释发生了什么以及为什么在某个点上如此不同(请参阅上面结果表中的 DIFFERENT! 标记)？

有人知道如何解决这个问题吗？

Answer 1

您在 JS 和 PHP 中得到了一个奇怪的结果，因为您正在使用 IEEE float ，而不是整数。 >> 运算符将其操作数视为有符号 32 位整数，但减法和加法则不然。这意味着，当任何迭代中的值介于 2^31 和 2^32 - 1 之间时，您会得到不同的输出，因为 JavaScript 将其解释为无符号数字而不是签名号码。

您可以修复 JavaScript 并使其输出与 C/C++ 相同的结果，通过 using a rightshift of 0再次将结果视为有符号 32 位整数:

const str = "M:/Mijn Muziek/Various Artists/Revs & ElBee - Tell It To My Heart.mp3"
const hashCode = getHashCode( str );
console.log( hashCode );

function getHashCode(s)
{
     var hash=0,c=(typeof s === 'string')?s.length:0,i=0;
    
     while(i<c) 
      { hash = (((hash<<5)-hash)+s.charCodeAt(i++)>>>0); } // Added >>> 0
    
     return ( hash < 0 )?((hash*-1)+0xFFFFFFFF):hash; /* convert to unsigned int */
}

要让 C 按照 Javascript 和 PHP 的方式运行，您需要使用更大的哈希数据类型 (int64_t) ，但请确保将其视为仅用于左移操作的 int32_t :

uint64_t getHashCode( const char* s )
{
 int16_t  iLen  = strlen( s );
 int16_t  i     = 0;
 int64_t  hash  = 0;

 while( i < iLen ) 
  { 
     // hash<<5 = multiply by 32
    hash = (((int32_t)hash<<5)-hash)+(uint8_t)s[i++]; 
  }

 return (( hash < 0 )?((hash*-1)+0xFFFFFFFF):hash); //convert to unsigned 
}