库的地址在这里：https://github.com/node-modules/node-murmurhash

介绍一下 murmurhash。murmurhash 是 Austin Appleby 于2008年创立的一种非加密 hash 算法，适用于基于 hash 进行查找的场景。

相比其他的 hash 算法，对于规律性较强的 key，MurmurHash 的随机分布特性表现更良好。而且很快。

好了就摘抄到这了。。。

至于为什么用到了它，是因为前公司那里，有个分布式缓存服务用了它来做分片。@fengmk2(https://github.com/fengmk2) 和 @dead-horse(https://github.com/dead-horse) 实现了这个缓存服务的 Node 客户端，在这一过程中，也同时需要实现 murmurhash 算法。

我们只要保证跟 Java 那边同样的输入，能得到同样的输出就好了。我不是很懂 murmurhash 这个技术选型的目的。

目前我们实现的这个是 murmurhash v2 的版本。

大家知道，加密算法普遍使用了各种【与】【或】【溢出】等手段来生成最终 hash 值。而 js 对于二进制的操作，有时候是要绕着来做，而且一些 C 语言中不同类型的表现，也需要特殊处理。

C++版本

这是最初的版本。

源码： https://github.com/node-modules/node-murmurhash/blob/4136c63dd87cc1541268e19f54149585d3ebe93b/src/murmurhash.cc

#include "nan.h"
#include "murmurhash.h"

#define MURMURHASH_M 0x5bd1e995

NAN_METHOD(MurmurHash2) {
  NanScope();

  if (args.Length() < 2) {
    NanThrowTypeError("Wrong number of arguments");
    NanReturnUndefined();
  }

  char *key = node::Buffer::Data(args[0]->ToObject());
  int len = node::Buffer::Length(args[0]->ToObject());
  uint32_t seed = args[1]->NumberValue();
  uint32_t h = seed ^ len;
  int index = 0;

  while (len >= 4) {
    uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
      | ((key[index + 2] << 16) & 0xff0000)
      | (key[index + 3] << 24);

    k *= MURMURHASH_M;
    k ^= (k >> 24);
    k *= MURMURHASH_M;
    h *= MURMURHASH_M;
    h ^= k;
    index += 4;
    len -= 4;
  }

  switch (len) {
    case 3:
      h ^= (key[index + 2] << 16);

    case 2:
      h ^= (key[index + 1] << 8);

    case 1:
      h ^= key[index];
      h *= MURMURHASH_M;
  }

  h ^= (h >> 13);
  h *= MURMURHASH_M;
  h ^= (h >> 15);
  NanReturnValue(NanNew<v8::Number>(h));
}

因为涉及二级制操作嘛，很自然地，一开始的版本是个 C++ 的 addon。找个开源的库，把 v8.h 相关的操作替换进去，再 node-gyp 包一下，就能工作了。

其实这么用着，也倒相安无事。速度很快，代码反正写好就是固定的，也不用改。

但无论对于 Mac 还是 Windows 的用户来说，用上这个库的前提都是需要安装一个编译环境。Mac 下面有 Xcode 的工具可以安装，Windows 下面，不懂怎么弄，好像是弄个 vs 的工具套装。那这么说，对于一些没有环境的新用户，本地开发第一次安装时，始终是不太方便的。

先来说说上述代码里面的几个关键点。

一、【与】【或】【非】的操作，js 都支持，而且结果跟 C++ 里几乎一样。

上述代码中seed ^ len 这样的操作是 js 原生支持的。

在 js 里面，Number 类型在内存中的结构跟 C++ 语言里面 double 是一样的。都是双精度浮点数，也可以叫 64 位浮点数，IEEE 754 标准。在进行二进制操作的时候（比如 100 << 2），js 会把 Number 当做 32 位的有符号整形进行操作，

小数部分直接舍去，比如：

> 2.9 << 1
4

超过 32 位的部分舍去。比如：

> Math.pow(2, 32).toString(2)
'100000000000000000000000000000000'
> Math.pow(2, 33).toString(2)
'1000000000000000000000000000000000'
> (Math.pow(2, 32) + 1).toString(2)
'100000000000000000000000000000001'
> (Math.pow(2, 32) + 1) << 1
2
> ((Math.pow(2, 32) + 1) << 1).toString(2)
'10'

参考： https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

二、

#define MURMURHASH_M 0x5bd1e995 这个宏怎么办？

但其中多处使用的 uint32_t 怎么在 js 中表示？

uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
  | ((key[index + 2] << 16) & 0xff0000)
  | (key[index + 3] << 24);

这句是在做什么？其中 key[index] 都是 char 类型的。

switch 那个地方，key[index + 2] << 16 这句乍看之下没问题，但大家注意，key[index] 都是 char 类型的。一个 char 类型在 c 语言中进行二进制操作的时候，会发生哪些不为人知的事情？

k *= MURMURHASH_M 这一句，k 作为一个 uint32_t，乘以另一个 32 位正整数，分分钟要溢出，溢出的表现是如何的？

这些事情又怎么在 js 中模拟。下面让我们走近科学…

分解

我们一个个地说

宏

#define MURMURHASH_M 0x5bd1e995

这段宏倒是好处理，虽然这是个宏，但我们 js 中使用赋值，结果也是一样的。之所以使用宏，一是因为 c 语言中，常量习惯使用宏；二是因为，宏是在编译阶段展开的，展开后它嵌到各个使用语句中，运行时不必再去变量中取值。不过既然 js 不支持宏，我们也只能赋值了。效率当然低一点啦，但我们是有心理准备的，而且我们相信 V8。

所以这句，直接 var MURMURHASH_M = 0x5bd1e995。

对了，这个数的意义是什么呢？就当它是个 magic number 吧。。。我赌一块钱，这是个质数。

uint32_t

uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
  | ((key[index + 2] << 16) & 0xff0000)
  | (key[index + 3] << 24);

说到这个地方，要先说说它的右边 key[index] & 0xff 发生了什么。key[index] 是个 char 类型，它的范围是 –128 to 127。

如果一个字符的 ascii 码大于等于0，小于等于127的时候。那么 char 类型会如实记录它的值。

如果大于 127，比如 128，那么在赋值给 char 的时候，C 语言会认为 char 的值是 -128

这个我们可以在 node 里面试试：

> var b = new Buffer(1)
undefined
> b
<Buffer 00>
> b.writeInt8(128, 0, true)
1
> b
<Buffer 80>
> b.readInt8(0)
-128

在 char 转换成 signed int，对应也有两种情况。当值大于等于0，小于等于127的时候，直接转成对应的 int。大于 127 的时候，会变成一个极大的负数。0x79 === 127。

0x79 转成 int 的时候，C 语言里面变成 0x000000079。0x80 转成 int 的时候，C 语言里面会变成 0xffffff80，这段内存被 int 一解读，就成了极大负数。

(key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)
  | ((key[index + 2] << 16) & 0xff0000)
  | (key[index + 3] << 24);

这句整体的意思就是，用户传进来的连续4个char（每个8位），用 & 0xff00 的操作，过滤所有跟符号位有关的影响，把本该属于它们的实际两位取出来，然后把它们拼成一个 32 位的值。

假设 key = [0x01, 0x02, 0x80, 0x813]，那么这个地方拼出来的值就是 0x13800201。我们可以试一试。

> var key = [0x01, 0x02, 0x80, 0x13]
undefined
> var index = 0
undefined
> (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00) | ((key[index + 2] << 16) & 0xff0000) | (key[index + 3] << 24)
327156225
> 327156225..toString(16)
'13800201'


// 高级写法，不过比上述要慢。可能V8本来就很快，而 Buffer 操作又涉及与 C++ 层的通信。
// 这里的 key 在 js 中是 Buffer，所以我们可以调用 Buffer 的 read 方法。
// 示例代码
> var key = new Buffer([0x01, 0x02, 0x80, 0x13])
undefined
> key.readInt32LE(0)
327156225

然后这个值被赋给 k 记录下来。无论 k 是 int32_t 还是 uint32_t，都会如实记录下这个值。

不同的是，使用的时候，k 到底被解释负数还是正数。

下面我们马上就要使用 k 了。

先说说 js 对于这个问题的解法：

k = (key[i] |
  (key[i + 1] << 8) |
  (key[i + 2] << 16) |
  (key[i + 3] << 24))

在我们这里，key 是个 Buffer 的实例，里面的每个值，都是大于等于0小于等于255的数字。

由于 js 会把每个索引的部分当成 Number 来看待，所以我们这里没有 char 溢出的问题。不必进行 & 0xff00 等操作。直接移位就能如实拿到它的内存表示。

char to int32

h ^= (key[index + 2] << 16);

这一句，没有只截取需要的 char 部分，而是如实把符号位相关的也使用了。在上一段中，其实 char to int32 的问题我们并没有解，只是刚好没发生。

但到了这一步，就需要解了。

解法也简单：

function negative(num) {
  if (num < 127) {
    return num;
  }
  return num | 0xffffff00
}

就可以了。

在这个函数出来之前，我们的解法是，用一张映射表，把 256 种情况列进来，然后通过查表来决定 char 应该转成什么。这个表的生成其实也简单的，而且效率也很高，哪有比查表更快的嘛。

但我改成这个函数之后，我发现效率没有下降，而且这样更简单，就改成这样了。或许我这样改还拖慢了速度，不过差别不大，根据我们使用的 benchmark，可能会每秒少100w次吧（逃…但我就喜欢这么写。

imul

c语言中，0x5bd1e995 这东西叫做 decimal literal。它并不区分类型，只是严格地记住自己的二进制形式。当赋值或者运算的时候，才根据对方需要的类型，来解读自身。

k *= MURMURHASH_M 这一句发生的时候，它被解释成了 int。由于它的首位不是0，所以它是个正数。

而 k 由于按照无符号数解释，也是个正数。

这时候蛋疼的事情就来了。因为溢出了。

> var k = 3
undefined
> var MURMURHASH_M = 0x5bd1e995
undefined
> k * MURMURHASH_M
4621450431
> 4621450431..toString(16)
'11375bcbf'
> 4621450431..toString(2).length
33
> 4621450431..toString(2)
'100010011011101011011110010111111'

k 作为一个 uint32_t，最多表示 32 位的数，而我们的结果有 33 位，这时候 c 语言只会保留 0b00010011011101011011110010111111 下来，去掉超过 32 位的部分。

> 0b00010011011101011011110010111111
326483135

ok，这种情况我们怎么模拟？

先说为什么需要模拟，上面不是好好地得出了与C语言一样的值吗？

因为 js 中，按照 IEEE 754 的标准，能精确表示的最大整数是 2 ** 53 - 1。

两个 32 位的正整数相乘，最大的结果可以达到64位（但无法到达65位）。

如果我们的 k *= MURMURHASH_M 的结果大于 2 ** 53 - 1，在 js 中，就会变成一个非精确值。相信大家有所耳闻过这一点。

> Math.pow(2, 53) + 1
9007199254740992
> Math.pow(2, 53) + 2
9007199254740994

所以这里不敢让它们直接相乘。

解法就是，拆拆拆！

把 0x5bd1e995 拆成 0x5bd1 和 0xe995。都是16位的，与32位相乘之后，最多48位，js中可以精确表示。

var MURMURHASH_M = 0x5bd1e995;
var L16MURMURHASH_M = MURMURHASH_M >>> 16; // 0x5bd1
var R16MURMURHASH_M = MURMURHASH_M & 0xffff; // 0xe995

L16MURMURHASH_M * k 之后，得到一个最多48位的数。这个数，我们能使用到的部分，是最右的 16 位。因为这个结果值由于某个入参被右移了16位。所以得到结果之后，需要把结果左移16位。而一共就那么32位，左移之后右边全是0。所以有效部分只有16位。

将上述的结果，再加上 R16MURMURHASH_M * k 的值，这个值是最多48位的。与上述32位的结果相加，最多产生一个49位的数。可以精确表示。

所以这个正整数相乘的溢出部分，我们的写法是：

k = (k * L16MURMURHASH_M << 16) + k * R16MURMURHASH_M

后来 es6 出来了一个一个 Math.imul 函数，原生支持我们要的结果。用 Math.imul 改写这个地方之后，速度是原来的 2.5 倍左右。

总结

现在的实现在这里：https://github.com/node-modules/node-murmurhash/blob/master/lib/murmur.js

我就不贴出来了，大家可以对比着看。纯 js 版本。

之前 c 语言版本的速度，对于这样一个 buffer：new Buffer('haha, this is key')。每秒是 800w 次这样。

使用 Math.imul 之前，js 版本也是 800w 次左右，持平。使用了 Math.imul 之后，现在是 2000w 次。

faster than c!!! https://github.com/felixge/faster-than-c