« April 2020 | Main

May 26, 2020

lua hash 函数的一点讨论

最近一段时间,lua 的邮件列表中有好几个主题讨论 hash 表的设计。我读下来受益匪浅。比如 前两周的这个主题 中,有同学主张去掉 lua hash table 中的链表指针,而改成固定步长的冲突链表。具体这里就不展开了,有兴趣的同学可以自己看。

这两天的讨论是围绕 lua 的 hash 函数的,暂时还没有固定链接,我把我的理解和思考记录下来,不一定正确,如有行家发现错误,请不吝赐教。

unsigned int
luaS_hash (const char *str, size_t l, unsigned int seed, size_t step) {
  unsigned int h = seed ^ cast_uint(l);
  for (; l >= step; l -= step)
    h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
  return h;
}

来看这样一个 hash 函数:

(h<<5) + (h>>2) 本质上相当于 ((h<<7) + h) >> 2 ,不同的是,前者可以多保留 2 个高位,不至于移出去。

(h<<7) + h 即 h * 129 ,所以这个算法本质上就是 Knuth 在《计算机编程艺术》第 3 卷 第 2 版的 6.4 节谈论的 hash 算法。

不过这个乘数选的不好,因为它不是素数。为什么素数更好呢?我的理解是,hash 函数和伪随机数列发生器类似,都是想把源数据流变得随机。因为在 hash 表的实现中,桶的数量比较小,往表中放的时候需要按桶的数量再次取模。数据是随机时,取模后碰撞的几率更小。

当采用 LCG 算法时,乘数的选择会影响随机数列的周期,为了获得更大的周期,就需要取更大的素数做乘数。非素数因为可以被分解为更小的素数的积,所以不如差不多大的素数。

这里采用移位和加法是建立在乘法运算的开销明显大于移位和加法的前提上的,但本质上,乘法就是若干次的移位和加法的组合。太多次的移位的开销未必还能比单次乘法要低,所以我们在优化常数乘法的时候,要谨慎选择常数。

这里有同学建议把这里的算法改成 (h<<4)-(h>>3) ,它等价于 (h*127)>>>3 同时保护了高 3 位。和原版的区别在于 127 是一个梅森素数。 乘数是梅森数 (2^n-1) 可以保证能分解成一次移位和一次减法。

这里把移位从 2 改成 3 的道理在于,hash 函数是迭代处理数据流的,而数据流是按计算机字长逐个输入。通常字长都是 2 的倍数,所以移位的数量不宜是 2 ,3 会更好一些。

如果设备的乘法足够快的话,其实直接用乘法而不是用移位可能更好。因为我们可以选择更好的乘数。

Thomas Wang 有一篇关于 Integer Hash Function 的文章分析了怎样构造 hash 函数。

构造一个整数 hash 函数应该保证运算步骤是可逆的。因为只要存在可逆函数,就能保证源和结果 1:1 对应,避免了冲突。

加减法、左移、取反、异或操作都是可逆操作,乘法可以看作是移位和加法的组合,也是可逆的。

为了达到随机的效果(即 2 进制表达时,每个 bit 是 0 或 1 的可能性都是 50% ),我们迭代计算 hash 的过程,每 1bit 输入都尽量多个 bits 的变化。

上面的可逆操作中,移位、取反、异或要么是调整了 bits 的位置,要么是做了整体反转。真正引起变化的是加减法。比如 0111 + 1 = 1000 ,它让若干个连续 bits (但不是整体)反转了。只要结合这些运算,就能达到 hash 和稀(泥) 的效果。

乘法相当于多次的移位和加法,其实从实用价值上看,性价比是很高的。加法的次数等价于乘数中连续 1 的区段的个数。从这个角度看,0101010101 这样交错形式的乘数性价比最高。

对于 32bit 的 word ,我们应该选一个 16bit 的乘数。可惜 0b0101010101010101 = 0x5555 是 5 的倍数不是素数,如果稍微调整一下, 0b1010101010101011 = 0xAAAB = 43691 这个素数更好一些。

如果我们把上面的算法改写成:

h ^= ((h + cast_byte(ptr[l])) * 0xAAAB)>>3

或许是一个更好的 hash 函数。

我还猜想, 11011011 这样两个 1 一个 0 的模式会不会更好,因为 0b1011011011011011 = 0xB6Db = 46811 是一个更大的素数。


btw, Knuth 针对 64bit word 提出的乘数建议是 2654435761 ,它是 2^32 的黄金分割点附近的素数。


5 月 27 日补充:

我写了个程序来测试这一系列 hash 函数的避免碰撞的性能。使用了 3 万多个英语单词随机分组,模拟插入 hash 表。这里是测试代码和结果

针对这组测试数据,结论是 (h<<4) - (h>>3) + x 最好,原版的 (h<<5) + (h>>2) + x 最差。但是最好和最差之间也没有特别明显的区别。

影响碰撞的因素中,把每次迭代的位移从 2 改为 3 可能更重要,而乘数的选择则不那么重要。

May 19, 2020

记一次生不如死的经历

前几天晚上 21 点洗澡的时候感觉左腹部疼痛。因为前一天有过一次腹泻,便以为是吹空调着凉还没有好。继续蹲在马桶上又拉了一次肚子,但和之前不同,并没有减少痛苦的感觉,反而加重了。

我转而怀疑是吃错了什么东西引起的肠胃问题,但是努力回忆也想不出什么来。只觉得如果能把腹中的东西排空应该就好了。想了一下就抠了一下喉咙,趴在马桶上将肚子里没消化完的食物吐了出来。可是依然不见好转。

这个时候已经是坐立不安了,找不到一个姿势可以让自己好受一点。

我自觉还是对疼痛忍耐指数挺高的,攀岩的时候手指肚上拉下一块皮也不觉得有什么,可以继续爬;有次拔智齿的时候甚至没打麻药,牙科医生都赞我是看过的病人里最能忍痛的。可这次真的有点受不了。

零点的时候家人劝我去医院看看。我不是个讳疾忌医的人,也知道身体的信号不能马虎。但实在是太难受,感觉在家里条件会比医院好一些,至少想躺就能躺下,想坐在马桶上就能坐。就让家人出门帮忙买了点止疼药,“布洛芬缓释胶囊”。

服了药后,并没有像预计的那样很快好转。大约过了一个小时,稍微好了一点。我觉得我能自由活动了,便去医院挂了个急诊号。

大约等了一个多小时,等来了住院部的值班医生给我做 B 超检查。检查了大约 40 分钟,判断是左肾结石,尿道有扩张。验血验尿的结果是有感染,应该是结石划伤了尿道导致的。急诊医生给我开了三天的消炎药,静脉注射。叮嘱说若不用药,很可能接下来几天可能发烧。而这些日子发烧可不是件小事。

我问了一下排石是否需要服药,医生说,服药的话只有一些中成药可供选择,但我们这里是西医院不开任何中药,如果你需要,可以去药房自己买,就挑最便宜的那种就够了。我说,我不信那个,估计吃了也不会有安慰剂效应。医生问我需不需要开点止疼药,我问我吃的那个布洛芬还能继续用吗?他说也行,那就不开了。反正若还有下次的话,估计啥止疼药都不管用,忍着就好。

我前几年体检的时候 B 超就查出来肾里有结晶,一直担心发展成结石,所以每年体检都特定叮嘱 B 超医生仔细检查。最近一次体检是在去年 12 月,当时医生明确说没有肾结石。现在想起来,要么结石是最近在家关了小半年长出来的,要么就是体检不太靠谱了。当然,体检 B 超久那么几分钟,想想也不能太过信任。

第二天上网研究了一下,挂了个珠江医院的泌尿外科专家号。重新做了检查。教授判断说,那天晚上导致腹痛的结石已经排出来了。不过肾里还有一颗 2x3mm 的泥沙状结石。这个多喝水,多运动,比如每天跳跳绳就好。

这次唯一的收获是:有了个正当理由推掉了一次当天晚上的阿里管理者会议。参加这些会议对我来说或许是件更痛苦的事。

May 08, 2020

《程序员修炼之道》中的一段废稿

我在翻译《程序员修练之道》第二版时,一开始拿到的版本并不是现在出版的这个。所以在中途更换过一个版本,即最后英文版的最终版。前后两个版本都不是原始 markdown ,而是 pdf 格式的。试过几个 diff 软件都无法很好的比对,只好花了不少时间人肉校对了一遍。

虽然两个版本先后只差了几个月,但是增加,调整的段落非常之多,可见作者维护的非常频繁。我当时特别想一观他们的内部写作仓库。记忆比较深刻的是有一大段谈团队的文字被删掉了。不知道原因。但我觉得挺可惜的,这是我很喜欢的一个段落。为了忠于原著,我也从中译版里删除。

下面记录一下这段废稿:

项目团队

你是否注意到,一些项目团队非常高效,每个人都知道该做什么,并做出了充分的贡献;而其他一些团队的成员却总是争吵不休,似乎无法相互谦让?

通常这就是一个正交性问题。当团队组织重复到架屋迭床时,成员会对职责感到困惑。每修改一个东西都需要整个团队开会,因为修改会影响每个人。

如何将团队组织成职责明确、重叠最少的不同小组?没有简单的答案。这一定程度上取决于具体项目,以及你对可能发生变化区域的分析;同时还取决于你能调用的人手。我们的首选做法是,先将基础设施从应用程序中分离出来,让每个主要的基础设施组件(数据库、通信接口、中间件层等)都有自己的子团队,让应用程序中特别明显的不同功能都能简单地分开。然后再查看我们拥有(或计划拥有)的人员,并相应地调整分组。

有一个通俗的方法,可以用来评估项目团队结构的正交性——只需简单看看,在讨论每个修改时,有多少人需要参与进来。人数越多,组织的正交性越差。显然,一个正交的团队更有效率。(话虽如此,我们还是鼓励子团队间保持相互沟通。)