[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6,"_7":8},"actionData","errors","root",{"_11":-5},"routes/user.$name.collections",{"_9":10,"_11":12,"_13":14,"_15":16,"_17":18,"_19":16},"topics",[35],"user",{"_20":21,"_13":14,"_22":23,"_24":14,"_25":26,"_27":28,"_29":30,"_31":32,"_33":34},"loginname","x770158999","page",1,"limit",20,"total","id","23117","avatar_url","https://avatars.githubusercontent.com/u/16560532?v=4","githubUsername","create_at","2016-06-13 09:11:43.493","score",40,"topic_count",0,"reply_count",8,"is_star",false,{"_20":36,"_37":38,"_39":40,"_41":42,"_43":44,"_45":46,"_47":48,"_49":34,"_31":18,"_50":51,"_25":52,"_53":54},"14990","author_id","4922","tab","share","content","库的地址在这里：https://github.com/node-modules/node-murmurhash\r\n\r\n介绍一下 murmurhash。murmurhash 是 Austin Appleby 于2008年创立的一种非加密 hash 算法，适用于基于 hash 进行查找的场景。\r\n\r\n相比其他的 hash 算法，对于规律性较强的 key，MurmurHash 的随机分布特性表现更良好。而且很快。\r\n\r\n好了就摘抄到这了。。。\r\n\r\n至于为什么用到了它，是因为前公司那里，有个分布式缓存服务用了它来做分片。@fengmk2(https://github.com/fengmk2) 和 @dead-horse(https://github.com/dead-horse) 实现了这个缓存服务的 Node 客户端，在这一过程中，也同时需要实现 murmurhash 算法。\r\n\r\n我们只要保证跟 Java 那边同样的输入，能得到同样的输出就好了。我不是很懂 murmurhash 这个技术选型的目的。\r\n\r\n目前我们实现的这个是 murmurhash v2 的版本。\r\n\r\n大家知道，加密算法普遍使用了各种【与】【或】【溢出】等手段来生成最终 hash 值。而 js 对于二进制的操作，有时候是要绕着来做，而且一些 C 语言中不同类型的表现，也需要特殊处理。\r\n\r\n## C++版本\r\n\r\n这是最初的版本。\r\n\r\n源码： https://github.com/node-modules/node-murmurhash/blob/4136c63dd87cc1541268e19f54149585d3ebe93b/src/murmurhash.cc\r\n\r\n```\r\n#include \"nan.h\"\r\n#include \"murmurhash.h\"\r\n\r\n#define MURMURHASH_M 0x5bd1e995\r\n\r\nNAN_METHOD(MurmurHash2) {\r\n NanScope();\r\n\r\n if (args.Length() < 2) {\r\n NanThrowTypeError(\"Wrong number of arguments\");\r\n NanReturnUndefined();\r\n }\r\n\r\n char *key = node::Buffer::Data(args[0]->ToObject());\r\n int len = node::Buffer::Length(args[0]->ToObject());\r\n uint32_t seed = args[1]->NumberValue();\r\n uint32_t h = seed ^ len;\r\n int index = 0;\r\n\r\n while (len >= 4) {\r\n uint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)\r\n | ((key[index + 2] << 16) & 0xff0000)\r\n | (key[index + 3] << 24);\r\n\r\n k *= MURMURHASH_M;\r\n k ^= (k >> 24);\r\n k *= MURMURHASH_M;\r\n h *= MURMURHASH_M;\r\n h ^= k;\r\n index += 4;\r\n len -= 4;\r\n }\r\n\r\n switch (len) {\r\n case 3:\r\n h ^= (key[index + 2] << 16);\r\n\r\n case 2:\r\n h ^= (key[index + 1] << 8);\r\n\r\n case 1:\r\n h ^= key[index];\r\n h *= MURMURHASH_M;\r\n }\r\n\r\n h ^= (h >> 13);\r\n h *= MURMURHASH_M;\r\n h ^= (h >> 15);\r\n NanReturnValue(NanNew(h));\r\n}\r\n```\r\n\r\n因为涉及二级制操作嘛，很自然地，一开始的版本是个 C++ 的 addon。找个开源的库，把 v8.h 相关的操作替换进去，再 node-gyp 包一下，就能工作了。\r\n\r\n其实这么用着，也倒相安无事。速度很快，代码反正写好就是固定的，也不用改。\r\n\r\n但无论对于 Mac 还是 Windows 的用户来说，用上这个库的前提都是需要安装一个编译环境。Mac 下面有 Xcode 的工具可以安装，Windows 下面，不懂怎么弄，好像是弄个 vs 的工具套装。那这么说，对于一些没有环境的新用户，本地开发第一次安装时，始终是不太方便的。\r\n\r\n先来说说上述代码里面的几个关键点。\r\n\r\n一、【与】【或】【非】的操作，js 都支持，而且结果跟 C++ 里几乎一样。\r\n\r\n上述代码中`seed ^ len` 这样的操作是 js 原生支持的。\r\n\r\n在 js 里面，Number 类型在内存中的结构跟 C++ 语言里面 double 是一样的。都是双精度浮点数，也可以叫 64 位浮点数，IEEE 754 标准。在进行二进制操作的时候（比如 `100 << 2`），js 会把 Number 当做 32 位的有符号整形进行操作，\r\n\r\n小数部分直接舍去，比如：\r\n\r\n```js\r\n> 2.9 << 1\r\n4\r\n```\r\n\r\n\r\n超过 32 位的部分舍去。比如：\r\n\r\n```js\r\n> Math.pow(2, 32).toString(2)\r\n'100000000000000000000000000000000'\r\n> Math.pow(2, 33).toString(2)\r\n'1000000000000000000000000000000000'\r\n> (Math.pow(2, 32) + 1).toString(2)\r\n'100000000000000000000000000000001'\r\n> (Math.pow(2, 32) + 1) << 1\r\n2\r\n> ((Math.pow(2, 32) + 1) << 1).toString(2)\r\n'10'\r\n```\r\n\r\n参考： https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators\r\n\r\n二、\r\n\r\n`#define MURMURHASH_M 0x5bd1e995` 这个宏怎么办？\r\n\r\n但其中多处使用的 `uint32_t` 怎么在 js 中表示？\r\n\r\n```js\r\nuint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)\r\n | ((key[index + 2] << 16) & 0xff0000)\r\n | (key[index + 3] << 24);\r\n```\r\n\r\n这句是在做什么？其中 `key[index]` 都是 char 类型的。\r\n\r\nswitch 那个地方，`key[index + 2] << 16` 这句乍看之下没问题，但大家注意，`key[index]` 都是 char 类型的。一个 char 类型在 c 语言中进行二进制操作的时候，会发生哪些不为人知的事情？\r\n\r\n`k *= MURMURHASH_M` 这一句，k 作为一个 `uint32_t`，乘以另一个 32 位正整数，分分钟要溢出，溢出的表现是如何的？\r\n\r\n这些事情又怎么在 js 中模拟。下面让我们走近科学...\r\n\r\n## 分解\r\n\r\n我们一个个地说\r\n\r\n### 宏\r\n\r\n`#define MURMURHASH_M 0x5bd1e995`\r\n\r\n这段宏倒是好处理，虽然这是个宏，但我们 js 中使用赋值，结果也是一样的。之所以使用宏，一是因为 c 语言中，常量习惯使用宏；二是因为，宏是在编译阶段展开的，展开后它嵌到各个使用语句中，运行时不必再去变量中取值。不过既然 js 不支持宏，我们也只能赋值了。效率当然低一点啦，但我们是有心理准备的，而且我们相信 V8。\r\n\r\n所以这句，直接 `var MURMURHASH_M = 0x5bd1e995`。\r\n\r\n对了，这个数的意义是什么呢？就当它是个 magic number 吧。。。我赌一块钱，这是个质数。\r\n\r\n### uint32_t\r\n\r\n```\r\nuint32_t k = (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)\r\n | ((key[index + 2] << 16) & 0xff0000)\r\n | (key[index + 3] << 24);\r\n```\r\n\r\n说到这个地方，要先说说它的右边 `key[index] & 0xff` 发生了什么。`key[index]` 是个 char 类型，它的范围是 –128 to 127。\r\n\r\n如果一个字符的 ascii 码大于等于0，小于等于127的时候。那么 char 类型会如实记录它的值。\r\n\r\n如果大于 127，比如 128，那么在赋值给 char 的时候，C 语言会认为 char 的值是 -128\r\n\r\n这个我们可以在 node 里面试试：\r\n\r\n```\r\n> var b = new Buffer(1)\r\nundefined\r\n> b\r\n\r\n> b.writeInt8(128, 0, true)\r\n1\r\n> b\r\n\r\n> b.readInt8(0)\r\n-128\r\n```\r\n\r\n在 char 转换成 signed int，对应也有两种情况。当值大于等于0，小于等于127的时候，直接转成对应的 int。大于 127 的时候，会变成一个极大的负数。```0x79 === 127```。\r\n\r\n`0x79` 转成 int 的时候，C 语言里面变成 `0x000000079`。`0x80` 转成 int 的时候，C 语言里面会变成 `0xffffff80`，这段内存被 int 一解读，就成了极大负数。\r\n\r\n```\r\n(key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00)\r\n | ((key[index + 2] << 16) & 0xff0000)\r\n | (key[index + 3] << 24);\r\n```\r\n\r\n这句整体的意思就是，用户传进来的连续4个char（每个8位），用 `& 0xff00` 的操作，过滤所有跟符号位有关的影响，把本该属于它们的实际两位取出来，然后把它们拼成一个 32 位的值。\r\n\r\n假设 `key = [0x01, 0x02, 0x80, 0x813]`，那么这个地方拼出来的值就是 `0x13800201`。我们可以试一试。\r\n\r\n```\r\n> var key = [0x01, 0x02, 0x80, 0x13]\r\nundefined\r\n> var index = 0\r\nundefined\r\n> (key[index] & 0xff) | ((key[index + 1] << 8) & 0xff00) | ((key[index + 2] << 16) & 0xff0000) | (key[index + 3] << 24)\r\n327156225\r\n> 327156225..toString(16)\r\n'13800201'\r\n\r\n\r\n// 高级写法，不过比上述要慢。可能V8本来就很快，而 Buffer 操作又涉及与 C++ 层的通信。\r\n// 这里的 key 在 js 中是 Buffer，所以我们可以调用 Buffer 的 read 方法。\r\n// 示例代码\r\n> var key = new Buffer([0x01, 0x02, 0x80, 0x13])\r\nundefined\r\n> key.readInt32LE(0)\r\n327156225\r\n```\r\n\r\n然后这个值被赋给 `k` 记录下来。无论 k 是 int32_t 还是 uint32_t，都会如实记录下这个值。\r\n\r\n不同的是，使用的时候，k 到底被解释负数还是正数。\r\n\r\n下面我们马上就要使用 k 了。\r\n\r\n先说说 js 对于这个问题的解法：\r\n\r\n```\r\nk = (key[i] |\r\n (key[i + 1] << 8) |\r\n (key[i + 2] << 16) |\r\n (key[i + 3] << 24))\r\n```\r\n\r\n在我们这里，key 是个 Buffer 的实例，里面的每个值，都是大于等于0小于等于255的数字。\r\n\r\n由于 js 会把每个索引的部分当成 Number 来看待，所以我们这里没有 char 溢出的问题。不必进行 `& 0xff00` 等操作。直接移位就能如实拿到它的内存表示。\r\n\r\n### char to int32\r\n\r\n`h ^= (key[index + 2] << 16);`\r\n\r\n这一句，没有只截取需要的 char 部分，而是如实把符号位相关的也使用了。在上一段中，其实 char to int32 的问题我们并没有解，只是刚好没发生。\r\n\r\n但到了这一步，就需要解了。\r\n\r\n解法也简单：\r\n\r\n```js\r\nfunction negative(num) {\r\n if (num < 127) {\r\n return num;\r\n }\r\n return num | 0xffffff00\r\n}\r\n```\r\n\r\n就可以了。\r\n\r\n在这个函数出来之前，我们的解法是，用一张映射表，把 256 种情况列进来，然后通过查表来决定 char 应该转成什么。这个表的生成其实也简单的，而且效率也很高，哪有比查表更快的嘛。\r\n\r\n但我改成这个函数之后，我发现效率没有下降，而且这样更简单，就改成这样了。或许我这样改还拖慢了速度，不过差别不大，根据我们使用的 benchmark，可能会每秒少100w次吧（逃....但我就喜欢这么写。\r\n\r\n### imul\r\n\r\nc语言中，`0x5bd1e995` 这东西叫做 decimal literal。它并不区分类型，只是严格地记住自己的二进制形式。当赋值或者运算的时候，才根据对方需要的类型，来解读自身。\r\n\r\n`k *= MURMURHASH_M` 这一句发生的时候，它被解释成了 int。由于它的首位不是0，所以它是个正数。\r\n\r\n而 k 由于按照无符号数解释，也是个正数。\r\n\r\n这时候蛋疼的事情就来了。因为溢出了。\r\n\r\n```\r\n> var k = 3\r\nundefined\r\n> var MURMURHASH_M = 0x5bd1e995\r\nundefined\r\n> k * MURMURHASH_M\r\n4621450431\r\n> 4621450431..toString(16)\r\n'11375bcbf'\r\n> 4621450431..toString(2).length\r\n33\r\n> 4621450431..toString(2)\r\n'100010011011101011011110010111111'\r\n```\r\n\r\nk 作为一个 uint32_t，最多表示 32 位的数，而我们的结果有 33 位，这时候 c 语言只会保留 `0b00010011011101011011110010111111` 下来，去掉超过 32 位的部分。\r\n\r\n```js\r\n> 0b00010011011101011011110010111111\r\n326483135\r\n```\r\n\r\nok，这种情况我们怎么模拟？\r\n\r\n先说为什么需要模拟，上面不是好好地得出了与C语言一样的值吗？\r\n\r\n因为 js 中，按照 IEEE 754 的标准，能精确表示的最大整数是 2 ** 53 - 1。\r\n\r\n两个 32 位的正整数相乘，最大的结果可以达到64位（但无法到达65位）。\r\n\r\n如果我们的 `k *= MURMURHASH_M` 的结果大于 2 ** 53 - 1，在 js 中，就会变成一个非精确值。相信大家有所耳闻过这一点。\r\n\r\n```js\r\n> Math.pow(2, 53) + 1\r\n9007199254740992\r\n> Math.pow(2, 53) + 2\r\n9007199254740994\r\n```\r\n\r\n所以这里不敢让它们直接相乘。\r\n\r\n解法就是，拆拆拆！\r\n\r\n把 0x5bd1e995 拆成 0x5bd1 和 0xe995。都是16位的，与32位相乘之后，最多48位，js中可以精确表示。\r\n\r\n```\r\nvar MURMURHASH_M = 0x5bd1e995;\r\nvar L16MURMURHASH_M = MURMURHASH_M >>> 16; // 0x5bd1\r\nvar R16MURMURHASH_M = MURMURHASH_M & 0xffff; // 0xe995\r\n```\r\n\r\n`L16MURMURHASH_M * k` 之后，得到一个最多48位的数。这个数，我们能使用到的部分，是最右的 16 位。因为这个结果值由于某个入参被右移了16位。所以得到结果之后，需要把结果左移16位。而一共就那么32位，左移之后右边全是0。所以有效部分只有16位。\r\n\r\n将上述的结果，再加上 `R16MURMURHASH_M * k` 的值，这个值是最多48位的。与上述32位的结果相加，最多产生一个49位的数。可以精确表示。\r\n\r\n所以这个正整数相乘的溢出部分，我们的写法是：\r\n\r\n`k = (k * L16MURMURHASH_M << 16) + k * R16MURMURHASH_M`\r\n\r\n后来 es6 出来了一个一个 `Math.imul` 函数，原生支持我们要的结果。用 `Math.imul` 改写这个地方之后，速度是原来的 2.5 倍左右。\r\n\r\n### 总结\r\n\r\n现在的实现在这里：https://github.com/node-modules/node-murmurhash/blob/master/lib/murmur.js\r\n\r\n我就不贴出来了，大家可以对比着看。纯 js 版本。\r\n\r\n之前 c 语言版本的速度，对于这样一个 buffer：`new Buffer('haha, this is key')`。每秒是 800w 次这样。\r\n\r\n使用 Math.imul 之前，js 版本也是 800w 次左右，持平。使用了 Math.imul 之后，现在是 2000w 次。\r\n\r\nfaster than c!!! https://github.com/felixge/faster-than-c","title","解析 node-murmurhash 库：说说 Node.js 二进制操作","last_reply_at","2018-10-15 03:02:22.329","good",true,"top","visit_count",15004,"2015-11-16 18:05:25.042","author",{"_13":55,"_22":56},"alsotang","https://avatars.githubusercontent.com/u/1147375?v=4"]