1
$\begingroup$

Below, I define two expressions X and Y (which arose in the wild!) such that not only

Hash[X] == Hash[Y]

but

Hash[{1}~Join~X] == Hash[{1}~Join~Y]

(and similarly for prepending and appending other lists), but X =!= Y (hint: look at the rule for p_137). This behaviour is observed on 10.0.1.0, OS X.

Is this a serious flaw in Mathematica's default hashing routine?

(It certainly wasted a lot of time for me, identifying this as the source of my problem.)

As a workaround, explicitly specifying a reliable hash algorithm, e.g. Hash[X, "SHA256"], works well.

X = {Subscript[p, 
    104] -> -(25489980146521924426446713/96977406606180352), 
   Subscript[p, 105] -> -(430682887014938439483527/1515271978221568), 
   Subscript[p, 106] -> 5149370439855884069715214191767921/
    1248460754793368970592256, 
   Subscript[p, 107] -> 26033322239045777466933937/
    1551638505698885632, Subscript[p, 108] -> -(466943/1792), 
   Subscript[p, 109] -> (
    25852260858512757 + 14006616064 Subscript[p, 110])/56026464256, 
   Subscript[p, 111] -> (
    105975798642828581977 - 112052928512 Subscript[p, 110])/
    7171387424768, 
   Subscript[p, 112] -> -(10402310382872191152683/15239198277632), 
   Subscript[p, 113] -> 623439045409311380656040905/14507716760305664,
    Subscript[p, 
    114] -> -(5259278076338981703182988881/360634730816733184), 
   Subscript[p, 
    115] -> -(5259278076338981703182988881/360634730816733184), 
   Subscript[p, 
    116] -> -(5259278076338981703182988881/360634730816733184), 
   Subscript[p, 
    117] -> -(5259278076338981703182988881/360634730816733184), 
   Subscript[p, 118] -> 476202049521095965/72123154432, 
   Subscript[p, 119] -> -(476202049521095965/1126924288), 
   Subscript[p, 
    120] -> -(27415335183976424824508760199138283/
     2205203303913668739072), Subscript[p, 121] -> 466943/114688, 
   Subscript[p, 122] -> 466943/28, Subscript[p, 123] -> 466943/28, 
   Subscript[p, 124] -> 466943/114688, 
   Subscript[p, 125] -> 23731276456463/517888, 
   Subscript[p, 126] -> 23731276456463/2121269248, 
   Subscript[p, 127] -> 3328836647/243712, 
   Subscript[p, 128] -> 3328836647/243712, 
   Subscript[p, 129] -> 23731276456463/2121269248, 
   Subscript[p, 130] -> 23731276456463/517888, 
   Subscript[p, 131] -> -(23731276456463/33144832), 
   Subscript[p, 132] -> -(23731276456463/33144832), 
   Subscript[p, 133] -> 15129551325791316375/1024483917824, 
   Subscript[p, 134] -> 0, Subscript[p, 135] -> 0, 
   Subscript[p, 136] -> -(15129551325791316375/16007561216), 
   Subscript[p, 137] -> 
    221094924364364149683780539852104201735038495241303244508425419897\
10850623213289708172866577/
     64942786580395380028213662293782159004668276294157920673487428733\
30745344, tt[1] -> -4096, tt[2] -> -(1/4096), tt[3] -> -1, 
   tt[4] -> 13240796148367/205979648, tt[5] -> 7129/136, 
   tt[6] -> 1/64, tt[7] -> 64, tt[8] -> -1, tt[9] -> -1, tt[10] -> -1,
    tt[11] -> -(31814976375/29425664), tt[12] -> 31814976375/459776, 
   tt[13] -> 7129/136, tt[14] -> 7129/136, tt[25] -> 896, 
   tt[26] -> 7/2, tt[27] -> 56, tt[28] -> 16, tt[29] -> -4, 
   tt[40] -> -(7/128), tt[41] -> -14, tt[42] -> -(7/8), 
   tt[43] -> 1/16, tt[44] -> -(1/4), tt[69] -> 368/153, 
   tt[70] -> 28/3, tt[71] -> -(111072583/291312), 
   tt[72] -> 1354453/2448, tt[73] -> 180241/2856, 
   tt[74] -> 12980343285/201601, tt[75] -> -(16411441/51609856), 
   tt[76] -> -(1195573365/6451232), tt[77] -> -(480081105/25804928)};
Y = {Subscript[p, 
   104] -> -(25489980146521924426446713/96977406606180352), 
  Subscript[p, 105] -> -(430682887014938439483527/1515271978221568), 
  Subscript[p, 106] -> 5149370439855884069715214191767921/
   1248460754793368970592256, 
  Subscript[p, 107] -> 26033322239045777466933937/1551638505698885632,
   Subscript[p, 108] -> -(466943/1792), 
  Subscript[p, 109] -> (
   25852260858512757 + 14006616064 Subscript[p, 110])/56026464256, 
  Subscript[p, 111] -> (
   105975798642828581977 - 112052928512 Subscript[p, 110])/
   7171387424768, 
  Subscript[p, 112] -> -(10402310382872191152683/15239198277632), 
  Subscript[p, 113] -> 623439045409311380656040905/14507716760305664, 
  Subscript[p, 
   114] -> -(5259278076338981703182988881/360634730816733184), 
  Subscript[p, 
   115] -> -(5259278076338981703182988881/360634730816733184), 
  Subscript[p, 
   116] -> -(5259278076338981703182988881/360634730816733184), 
  Subscript[p, 
   117] -> -(5259278076338981703182988881/360634730816733184), 
  Subscript[p, 118] -> 476202049521095965/72123154432, 
  Subscript[p, 119] -> -(476202049521095965/1126924288), 
  Subscript[p, 
   120] -> -(27415335183976424824508760199138283/
    2205203303913668739072), Subscript[p, 121] -> 466943/114688, 
  Subscript[p, 122] -> 466943/28, Subscript[p, 123] -> 466943/28, 
  Subscript[p, 124] -> 466943/114688, 
  Subscript[p, 125] -> 23731276456463/517888, 
  Subscript[p, 126] -> 23731276456463/2121269248, 
  Subscript[p, 127] -> 3328836647/243712, 
  Subscript[p, 128] -> 3328836647/243712, 
  Subscript[p, 129] -> 23731276456463/2121269248, 
  Subscript[p, 130] -> 23731276456463/517888, 
  Subscript[p, 131] -> -(23731276456463/33144832), 
  Subscript[p, 132] -> -(23731276456463/33144832), 
  Subscript[p, 133] -> 15129551325791316375/1024483917824, 
  Subscript[p, 134] -> 0, Subscript[p, 135] -> 0, 
  Subscript[p, 136] -> -(15129551325791316375/16007561216), 
  Subscript[p, 137] -> 
   375050576652584929340491548385592669353140526061699/
   110082038399271563699906716631040, tt[1] -> -4096, 
  tt[2] -> -(1/4096), tt[3] -> -1, tt[4] -> 13240796148367/205979648, 
  tt[5] -> 7129/136, tt[6] -> 1/64, tt[7] -> 64, tt[8] -> -1, 
  tt[9] -> -1, tt[10] -> -1, tt[11] -> -(31814976375/29425664), 
  tt[12] -> 31814976375/459776, tt[13] -> 7129/136, 
  tt[14] -> 7129/136, tt[25] -> 896, tt[26] -> 7/2, tt[27] -> 56, 
  tt[28] -> 16, tt[29] -> -4, tt[40] -> -(7/128), tt[41] -> -14, 
  tt[42] -> -(7/8), tt[43] -> 1/16, tt[44] -> -(1/4), 
  tt[69] -> 368/153, tt[70] -> 28/3, tt[71] -> -(111072583/291312), 
  tt[72] -> 1354453/2448, tt[73] -> 180241/2856, 
  tt[74] -> 12980343285/201601, tt[75] -> -(16411441/51609856), 
  tt[76] -> -(1195573365/6451232), tt[77] -> -(480081105/25804928)}
$\endgroup$
  • 1
    $\begingroup$ I get False for Hash[X]==Hash[Y], on Mathematica version 10.3.1 for Mac OS X. Likewise for the prepended versions. $\endgroup$ – Jens Apr 7 '16 at 5:51
  • 1
    $\begingroup$ All hash functions have collisions. For some, they might be easier to find than others. Although I can't provide a proof, I can say with quite a confidence that pairs of the form you describe exist even for "SHA256", they're just much harder to find. $\endgroup$ – kirma Apr 7 '16 at 5:52
  • $\begingroup$ From the documentation "Distinct inputs can give the same hash codes." I get False on 10, True on 9 for default Hash - something under the cover changed I'd venture, but just try a different hash type... $\endgroup$ – ciao Apr 7 '16 at 5:59
  • $\begingroup$ 10.4 on Xubuntu Trusty also gives different hashes for X and Y. I believe it was mentioned somewhere (but I cannot find the reference at the moment) that the default hash's algorithm is not guaranteed to be consistent across different versions, so your observed collision might be for that particular version only. $\endgroup$ – J. M.'s technical difficulties Apr 7 '16 at 6:37
  • 1
    $\begingroup$ @J.M. Default behaviour of Hash[expr] and hashing in different versions of Mathematica $\endgroup$ – Kuba Apr 7 '16 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.