JS哈希算法

问题背景

  公司旗下的自有产品桔梗导航,日均20万IP(数据来源CNZZ,截止20170801)。其下方信息流部分,本来走的是东方头条的资讯接口,东方头条按链接的GET带参统计来源,进行计费。为提高变现能力,现在要接入第三方广告。经业务人员业务洽谈,拉来了360的信息流插流广告。拉完讨论组之后,对接人员发来了对接文档

  大体的方式还是取JSON数据,在信息流渲染时,插流推广。与之前的东方头条不同的有两点:JSONP跨域以及哈希算法

JSONP跨域

  第一点,东方头条的接口,直接在服务端HTTP的Header中带参,为我们放开了跨域限制,可以直接跨域GET到数据。而360的数据接口,若要在浏览器端跨域访问,必须走标准JSONP请求。

  这并不是问题,按JSONP格式,使用JS生成一个script标签,将src属性指定为接口URL,URL中GET带参,传入回调参数名称(例如jsonpCallback),之后将script元素append到head元素中。script一旦载入,就会执行以下格式代码,从而将数据传给回调函数。(这部分的代码jQuery已经封装好了,之后我有空再把原生写法单独开文章贴进来)

1
2
3
4
5
6
7
8
// 包装一个立即执行的函数
(function(){
// 声明局部变量,将数据放在名为ads的JSON数组中
//...表示具体数据,这里为了代码整洁,不展示
var json={"ads":[{...},{...},{...},...]};
// 将局部变量中的数据,作为参数传给回调函数
window['jsonpCallback'](json);
})();

  为了优化性能,减少占用,避免冲突,一般情况下,JSONP的回调函数不能重名(可在发起请求时,在回调名内加上unix时间戳,jQuery的JSONP就是这么干的),而且应该“阅后即焚”(取到数据后,销毁回调函数),这里就不展开说了。

哈希算法

  第二点,东方头条的接口中,因为top50.json是一个定时生成的静态文件,并没有什么去重需求。而360给出的是有伸缩性的真正的RESTful接口,有去重需求。

文档内对UID的定义:

  用户一个session以内生成的唯一uid,用于多次广告请求的创意去重,uid的生成示例见后续;每次打开或刷新页面生成新的uid;

文档末尾UID的伪代码:

1
2
uid = Hash(cookie + domain)
//Hash 函数自定义。

  cookie和domain很好理解,就是document对象的cookie和domain属性,在浏览器控制台中console.dir(document),就能在document对象树中找到这两个家伙,数据类型都是字符串。那么我们的代码就应该是:

1
var uid=Hash(document.cookie+document.domain);

  接下来是Hash(散列)部分,根据以上需求,接收一个字符串,返回一串唯一哈希数字作为特征码。

两点要求

  1. 由于哈希算法是空间映射的压缩算法,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。我们这里是希望数据尽量一一映射,将得到的hash值直接作为特征码使用,所以对碰撞率有要求。
  2. 另外,JS本身是解释性语言,浏览器运行环境迥异,这个算法的性能要尽量高,减少性能消耗。

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
这部分是UMD(Universal Module Define)模块定义部分,
是为了兼容AMD模块加载机制和CommonJS模块加载机制,
从而实现模块在客户端(浏览器JS引擎)和服务端(Node)的复用,
如果看不懂,可以不管
*/

(function(root, factory) {
if (typeof define === 'function' && define.amd) {
define([], factory);
} else if (typeof exports === 'object') {
module.exports = factory();
} else {
root.hash = factory();
}
}(this, function() {

/**
一个字符哈希函数,基于Daniel J. Bernstein提出的,十分流行的'times 33'(乘以33)哈希算法
@param {string} text - 待hash字符串
@return {number} hash结果
*/

// 关键代码开始
function hash(text) {
'use strict';

var hash = 5381,
index = text.length;

while (index) {
hash = (hash * 33) ^ text.charCodeAt(--index);
}

return hash >>> 0;
}
// 关键代码结束
return hash;
}));

​ 这个方案碰撞率较低,而且使用了位运算符,性能较高。满足前面的两点要求。

综上所述,我们最终的代码snippet如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function Hash(text) {
// 启用严格模式,防止JS解释器异常
'use strict';

if(typeof text === 'number'){
// 假如输入是数字,转换为字符串
text = String(text);
}else if(typeof text !== 'string'){
// 假如输入不是数字也不是字符串,
// 由于没有使用try-catch语句,
// throw抛出的异常会终止运算,并在控制台显示Uncaught Error
throw new Error('数据类型错误,请传入数字或字符串');
}

var hash = 5381,// 给出哈希种子
index = text.length;// 字符串长度作为索引

while (index) {
//按索引倒序取Unicode,与种子的33倍进行按位异或比较,
//比较结果当做下一次的种子
hash = (hash * 33) ^ text.charCodeAt(--index);
}
// 无符号右移0位,保证结果为非负整数
return hash >>> 0;
}

var uid=Hash(document.cookie+document.domain);

附录

有关无符号右移,在StackOverflow上看到如下回答:

x >>> 0 performs a logical (unsigned) right-shift of 0 bits, which is equivalent to a no-op. However, before the right shift, it must convert the x to an unsigned 32-bit integer. Therefore, the overall effect of x >>> 0 is convert x into a 32-bit unsigned integer.

This ensures x is a nonnegative number.

翻译过来就是:

x >>> 0进行了一次逻辑上的 (无符号的) 0位右移, 这相当于什么也没干。但是,在进行右移之前,必须将x转化为一个无符号32位整数. 因此, x >>> 0 的最终效果是将x 转化为 32位无符号整数。

这保证了 x 是一个非负数

对于位运算,JS仅支持32位整数,其中1位符号位,31位数字位。这意味着,

  • 32bit最大正整数:Math.pow(2, 31) - 1 = 2147483647
  • 32bit最小负整数:Math.pow(2, 31) = -2147483648
  • 32bit最大无符号整数:Math.pow(2, 32) - 1= 4294967295

以上哈希算法的结果就是把任意长度的任意字符串映射到了0到4294967295这一段区间内。