一般hash函数为 h(x) = x mod TableSize。这个不可避免的会出现冲突的问题。多个值会出现在一个槽位上。很多hash表解决hash冲突的方法都是用一个链表或者红黑树来解决冲突，冲突后的数组的slot为一个链表的表头。这个就是所谓的“拉链法”。
还有一种解决冲突的办法是冲突后 在找下一个槽位，这个就是开放定址法。lua中table就是用的这种办法。
拉链法每次冲突后会new一个node，并把这个node挂入链表中，这个会导致插入速度会比开放定址法慢。
针对lua的table 计算hash值以及hash冲突的做法，来做个简单的分析。
static Node *mainposition (const Table *t, const TValue *key) {
switch (ttype(key)) {
case LUA_TNUMBER:
return hashnum(t, nvalue(key));
case LUA_TSTRING:
return hashstr(t, rawtsvalue(key));
case LUA_TBOOLEAN:
return hashboolean(t, bvalue(key));
case LUA_TLIGHTUSERDATA:
return hashpointer(t, pvalue(key));
default:
return hashpointer(t, gcvalue(key));
}
}
如果为TNUMBER类型的时候，调用hashnum.lua_Number默认是double类型
static Node *hashnum (const Table *t, lua_Number n) {
unsigned int a[numints];
int i;
//这里之所以要和0进行比较，是因为double类型+0.0 和-0.0的位级表示是不同的。
//否则+0和-0会产生不同的hash值。
if (luai_numeq(n, 0)) /* avoid problems with -0 */
return gnode(t, 0);
//这里直接把调用内存拷贝函数把double类型的位级数据拷贝到数组中。
memcpy(a, &n, sizeof(a));
//这样求取hash的输入就当一个偷懒的随机化吧
//一般算法处理中，尽量不要让特定的输入影响算法的性能，所以很多算法都会对输入进行随机化，防止给一个特定输入会导致很差的性能，比如随机化快排。
for (i = 1; i < numints; i++)
a[0] += a[i];
return hashmod(t, a[0]);
}
这个计算double类型的hash值的方法，在lua5.2中进行了优化
#define luai_hashnum(i,n) \
{ volatile union luai_Cast u; u.l_d = (n) + 1.0; /* avoid -0 */ \
(i) = u.l_p[0]; (i) += u.l_p[1]; } /* add double bits for his hash */
可以看到没有了内存拷贝使用联合体来优化这个加法，去掉比较运算，使用+1.0来避免-0.0。
在看看hashmod 这个宏定义
/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t,n) (gnode(t, ((n) % ((sizenode(t)-1)|1))))
这个等于把hash表大小-1了，想了半天想了2个理由
1.按照注释说法，输入有比较大概率为2的幂次方，所以要-1避免冲突
2.就是这个减1的做法，降低填充因子，为了hash冲突的时候可以用上。暂且这么理解了。
接着来谈谈 字符串在table的处理
//lua自己封装了字符串，字符串结构自带一个hash值，不同的hash值字符串肯定不同。
#define hashstr(t,str) hashpow2(t, (str)->tsv.hash)
这个对比前面求取lua_Number的模sizenode(t)，因为字符串已经处理了，所以hash值也会大不一样，所以不需要-1。
#define hashpow2(t,n) (gnode(t, lmod((n), sizenode(t))))
因为size肯定2的幂次方，所以用“&”操作来替代除法操作，加快速度。这里说个题外话，除法指令占用的时钟周期是“&”操作的几十倍。
#define lmod(s,size) (check_exp((size&(size-1))==0, (cast(int, (s) & ((size)-1)))))
在来谈谈字符串hash值是如何生成的
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
unsigned int h = cast(unsigned int, l); /* seed */
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
o != NULL;
o = o->gch.next) {
TString *ts = rawgco2ts(o);
if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
/* string may be dead */
if (isdead(G(L), o)) changewhite(o);
return ts;
}
}
return newlstr(L, str, l, h); /* not found */
}
查看代码这个其实js-hash的算法，加入step的目的，不至于一个超长的字符串计算hash值比较慢，
但是也出现了另外一个弊端，就是如果恶意输入大量的一些step中间不同，但是step位置上刚好相同的字符串。
会导致大量的hash冲突，拖累整个hash表的性能。这就是所谓的hash攻击了
lua5.3的代码里解决了这个问题，加入了一个随机数种子，每次启动都不同，来计算字符串的hash值。
网友评论