奇怪的哈希 | Hellflame

由于偶然的需求，需要在前端网页上计算链接的散列值，但是貌似并没有原生支持的比如md5，sha-x类的散列函数，也不可能引入一个 js-md5 这么一个庞大的库，所以不得不
自己实现一个小型的散列函数。一开始的时候一切看上去都运行的不错，但是仔细检查一下之后，发现了炒鸡奇怪的问题。

先看一下自己用 javascript 实现的哈希函数好了：

function hash(str){
    var result = 0,
        tab = [0x1234, 0x2345, 0x3456, 0x4567, 0x5678, 0x789a, 0x89ab, 0x9abc, 0xabcd, 0xbcde, 0xcdef];
    for(var i=0;i<str.length;i++){
      result = 33 * result + str.charCodeAt(i) ^ (i > 0 ? str.charCodeAt(i-1): 66) + tab[i % tab.length];
    }
    return Math.abs(result).toString(16)
  }

以上代码来自这个项目 , 具体的代码片段。

运行一下这个函数可以得到看上去效果很好的散列值：

hash('hellflame') 			// 1ecad345
hash('hellflame is fine')	// 6ebdc41a
hash('whatever')			// 1cb8a14b
hash('linux')				// 5a7bb254
hash('1')					// 1247
hash('2')					// 1244
hash('12')					// 2782f

运行起来的效果简直不只是好，甚至出人意料，嗯，的确从来没有想到散列值最长只有 8个字符，也就是不多不少 32 位 (我一开始并没有注意这个问题)。

关键的一行很明显是这个(然而也是坑最多的一行!)：

1	result = 33 * result + str.charCodeAt(i) ^ (i > 0 ? str.charCodeAt(i-1): 66) + tab[i % tab.length];

为了让每一个字符都作用到最终的散列值，把每一个位置的字符的ASCII码值再加上一个循环的查表结果作为 Horner 多项式的系数，杂糅结束之后取16进制结果作为最终哈希结果。为了使算法足够杂糅，这里掉进了第一个坑=。=

为了使算法足够杂糅，我计划着让当前位字符的ASCII码值跟前一位字符的ASCII码值做异或运算(第一位就跟66做异或操作)，然后再加上一个循环的 tab 列表得出的与位置相关的数(这个数只要每个地方不一样就好了)。但是，那关键的一行并没有实现计划！如果要看的更清楚的话，应该加上括号。

预想中的运算时这样的：

result = (33 * result)
  		 + (
  			str.charCodeAt(i) ^ (i > 0 ? str.charCodeAt(i-1): 66)
  		   )
  	     + tab[i % tab.length]);

嗯，在 Python 中也是很少做位运算的路过，以下是 python中的运算符号优先级，很明显跟记忆中是不一样好吧，位运算的符号虽然看上去很高端，但是优先级却出乎意料的低=。=(谁叫我只看加减乘除=。=)

运算符	描述
lambda	Lambda表达式
or	布尔“或”
and	布尔“与”
not x	布尔“非”
in，not in	成员测试
is，is not	同一性测试
<，<=，>，>=，!=，==	比较
\	按位或
^	按位异或
&	按位与
<<，>>	移位
+，-	加法与减法
*，/，%	乘法、除法与取余
+x，-x	正负号
~x	按位翻转
**	指数

由于运算优先级出现问题，所以实际上这行代码的优先级是这样的：

1
2
3

result = (33 * result + str.charCodeAt(i))
		 ^ 
  		 ((i > 0 ? str.charCodeAt(i-1): 66) + tab[i % tab.length]);

当然，就结果而言，这样的杂糅依然达到了想要的目的。异或的结果基本上是由最长的那个数来决定的，或者说一由于两个数长短不一样，长位数超出短位数的部分不会受到异或的影响，在运算后期，主要由 (i > 0 ? str.charCodeAt(i-1): 66) + tab[i % tab.length] 在改变着result的后几位数，result一直在以后几位字符ASCII值作为系数，幂级数增长，当前位字符的前一位字符影响越来越小(想到这里，这个hash函数其实并不好)，可以想象，如果字符特别长，异或运算的第二个操作数在整个杂糅中对最终值的扰动微乎其微。至于这个运算优先级的问题是怎么发现的话，就牵扯到了第二个坑。

在发现这个hash函数竟然能够无视字符串长度，无论多长，都能得到刚刚好的32位整数，我一样要在 python 上测试一下这个算法运算的效率怎么样，让这个函数跟语言自带的hashlib中的md5对比一下。于是按照js中的代码，实现了python中的同一套算法：

def hash(s):
    result = 0
    tab = [0x1234, 0x2345, 0x3456, 0x4567, 0x5678, 0x789a, 0x89ab, 0x9abc, 0xabcd, 0xbcde, 0xcdef]
    for index, i in enumerate(s):
        result = 33 * result + ord(i) ^ (ord(s[index - 1]) if index > 0 else 66) + tab[index % len(tab)]
    return hex(result if result > 0 else -result)

嗯，优先级错了，于是同样的值计算出来跟js不一样，于是发现了第一个问题。然而事实并没有那么简单。由于优先级都记错了，python能算对才怪！也就是，通过一个错误的python，得出js什么地方有问题，这个想法本身其实就已经错的一发不可收拾了。不过由此发现了原来自己的运算优先级竟然记错了！然后静静地一想，更不对了！既然两种语言的优先级是一样的，那为什么结果会不一样，而且还有一个很明显的差距，那就是python版本中的hash结果很显然没有保持32位的长度！

然而，这样不断增加的长度才应该是预想中的状态！js一定出了什么问题，也就是这里的第二个坑的真正现身。看看python使用hash函数的结果好了：

hash('hellflame') 			# 0x185be51ecad345
hash('hellflame is fine')	# 0x1f2877256aadc8f56ebdc41aL
hash('whatever')			# 0xbc331cb8a14b
hash('linux')				# 0x15a7bb254
hash('1')					# 0x1247
hash('2')					# 0x1244
hash('12')					# 0x2782f

出了最后3个能够和js中计算的结果匹配外，其他的值很显然都包含js的计算结果，或者说

1 2	python.hash(str)[-32:] == javascript.hash(str) # 字符串的长度的话，应该是[-8:]

很显然，js最终只保留了32位截断值。对于js的位运算，发现有很多文章在说这个截断问题。为什么不要在 JavaScript 中使用位操作符？，本质上是js中的位运算会将整数转换为有符号32位整数，那么超过32位的部分就直接被砍掉了，这也就是为什么在js的hash结果中最多只有32位整数的原因了，也是在函数末尾需要使用 abs来调整符号的原因。

在关键的地方log出变量的值会看的更清楚，去掉不重要的地方，看看结果：

function hash(str){
    var result = 0
    for(var i=0;i<str.length;i++){
      console.log(33 * result + str.charCodeAt(i), 
                  (i > 0 ? str.charCodeAt(i-1): 66))
      result = 33 * result + str.charCodeAt(i) ^ (i > 0 ? str.charCodeAt(i-1): 66)
      
      console.log(result)
      console.log("======")
    }
	console.log(Math.abs(result).toString(16))
}
hash('hellflame')

执行之后得到输出：

104 66
42
======
1487 104
1447
======
47859 101
47766
======
1576386 108
1576366
======
52020180 108
52020152
======
1716665124 102
1716665154
======
56649950179 108
815375247
======
26907383260 97
1137579453
======
37540122050 109
-1114583633
======
426f3251

在倒数第三行，很明显的出现了类似有符号整型溢出的现象，37540122050 ^ 109 = -1114583633，正确的结果应该是 37540122031。37540122050 算一下的话，已经超过了 2 ** 31 = 2147483648，37540122050.0 / 2 ** 32 = 8.740490779746324，8.7 超过了8.5，也就是最终结果大于2 ** 31，最终得到补码 37540122050 - Math.ceil(37540122050.0 / 2 ** 32) * 2 ** 32 = -1114583614 ，也就是实际参与运算的是 -1114583614，-1114583614 ^ 109 = -1114583633。

另一行不容易察觉到溢出的一行在这里 56649950179 ^ 108 = 815375247，56649950179 / 2 ** 32 = 13.189844363136217，13.1 未超过 13.5，也就是32位有符号整型中剩下的31位不会溢出，最终截断之后的值为 56649950179 - Math.floor(56649950179 / 2 ** 32) * 2 ** 32 = 815375331，进行异或操作之后得到 815375331 ^ 108 = 815375247，虽然得到的结果不是负数，但结果依然是被截断了。

最终，hash结果只剩下32位，就实际的混淆结果而言，看上去也还好，只是暂时没有测试碰撞概率以及和常见的hash函数相比的效率。应该在接下来的一段时间会稍微想想的吧。