[lua source code] luaS_hash
上一节对global_State做了子板块划分,回顾一下global_State整理后的代码:
typedef struct global_State { // Version const lua_Number *version; /* pointer to version number */ // Hash unsigned int seed; /* randomized seed for hashes */ // Global Registry TValue l_registry; // Global String table stringtable strt; /* hash table for strings */ Mbuffer buff; /* temporary buffer for string concatenation */ // Global Meta table TString *tmname[TM_N]; /* array with tag-method names */ struct Table *mt[LUA_NUMTAGS]; /* metatables for basic types */ // Global Thread list struct lua_State *mainthread; struct lua_State *twups; /* list of threads with open upvalues */ // Memory Allocator lua_Alloc frealloc; /* function to reallocate memory */ void *ud; /* auxiliary data to 'frealloc' */ // GC Info GCInfo *gcinfo; // Error Recover lua_CFunction panic; /* to be called in unprotected errors */}加深一下印象,也就是说global_State内部包含了下面这些重要部分:
- Version:pointer to version number
- Hash:randomized seed for hashes
- Global Registry
- Global String table
- Global Meta table
- Global Thread list
- Memory Allocator
- GC Info
- Error Recover
其中,Version指向了版本指针,通常我们发布程序版本号都是外置的,Lua把版本号内置在全局状态里,使得可以在运行时动态判断自己的版本号。
而,Hash部分的seed则是用在散列表里面计算哈希时的种子,在Lua的代码里可以找到这段代码:
//lstring.cunsigned int luaS_hash (const char *str, size_t l, unsigned int seed) { unsigned int h = seed ^ cast_uint(l); size_t step = (l >> LUAI_HASHLIMIT) + 1; for (; l >= step; l -= step) h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1])); return h;}第1眼看上去luaS_hash的代码没什么道理可言,其实一步步开展还是能了解的。首先,哈希函数有两类:
- 加密用的哈希函数,例如SHA-256, SHA-512, MD5, RIPEMD-160等
- 非加密用的哈希函数
luaS_hash即属于非加密用的哈希函数,在散列表里的主要作用是:
- 把输入字符串随机映射到散列表的索引范围[0, len-1]内
- 哈希应该在[0,len-1]内尽量符合均匀分布(Unifrom),也就是合法的输入被映射到[0,len-1]中任何一个地址的概率是相等的,这就使得输入经过哈希后可以得到一个“随机的地址”,以减少碰撞。
可见,它本质上是一种伪随机数生成器,而我们知道伪随机数生成器最古典的就是线性同余方法(wiki:Linear congruential generator(LCG)),它的算法如下:
LCG算出来的伪随机数序列在模M之后就是一个周期整数序列,周期的大小决定了碰撞的概率。LCG的周期最大是M,但大部分情况都会少于M,假如要让LCG达到最大周期,应该要符合以下Hull–Dobell Theorem条件:
- B,M互质
- M的所有质因子都能整除A-1
- 若M是4的倍数,A-1也是。
- A,B,
都比M小
- A,B都是正整数
LCG本身只是伪随机数生成器,需要满足均匀分布以减少碰撞才能在散列表里面使用。因而一个非密码学使用的哈希函数能否足够好(good hash function),就要看它能否足够均匀分布。
先看一个常见的Hash函数的实现,叫做DJBX33A (Daniel J. Bernstein, Times 33 with Addition):
unsigned int DJBHash(char* str, unsigned int len){ unsigned int hash = 5381; unsigned int i = 0; for(i = 0; i < len; str++, i++) { hash = ((hash << 5) + hash) + (*str); } return hash;}在for循环里做的hash = ((hash << 5) + hash) + (*str);实际上就是hash = hash*33+str[i],就是LCG递归算法的一个中间步骤。比照一下公式,可以看到:
=左边的hash
=右边的hash
- A=33
- B=str[i],str是ASCII字符串,str[i]是8 bits,从而B是[0,256)范围内的整数。
- M=
(或者者
,取决于int的位数)
可以看到A,B,M满足如下的几个性质:
- 假如B是奇数,B和M互质,至少一半的概率
- M的所有质因子是2,它可以整除A-1=32
- M(
或者者
)是4的倍数,A-1=32也是4的倍数
- A,B,
都比M小
- A,B是正整数(除0外)。
因而DJBX33A这个哈希函数具备很好的最大周期性,从而尽可能减少碰撞。但这只解释了一半起因,另一半起因是:
- A选择33这个接近
的数字,可以充分利用计算机里面用shift-and-add的方式计算乘法,即:h^33 = h^32+h = (h<<5)+h
- 假设h是32位,则二进制表达式为A1A2…A32,其中Ai取0或者者1,那么h<<5的二进制表达式是A6A7…A3200000,那么(h<<5)+h实际上把h的bit做了一次位移后再逐位和h自己相加,得到的h^33的每一个bit就尽可能均匀地混合了原来h的每一个bit信息。
- 从这个角度来说,假如h<<n里面的n太大,则会每次只混合了比较少的h原来bit的信息;假如n太小,则h<<n的每个bit离h的每个bit很近,这会需要更多的迭代才能让h的32个bit混合均匀。而5和32互质,也有利于屡次迭代中让h的每个bit有更大概率与输出h的每个bit都有机会做混合。
- 考虑B=str[i],str是ASCII字符串,str[i]是8 bits。ASCII的前4个bit都含有0x3。则:
- 迭代一次:h1=h0<<n+h0+str[i]
- 迭代二次:h2=h1<<n+h1+str[i+1] = h1’+str[i+1]
- 可以看到假如n是8,h1’的低8位就是str[i],那么h1’和str[i+1]的[4,8]位之间就会有相同的值做混合,不利于添加信息。n取4和2也是一样的问题。而n取5则可以让str[i]的低4位有更多机会和str[i+1]的高4位做混合。
上面这段解释来自参考资料[2]的评论,而参考资料[3]的评论下则有一段对DJB里的这几个魔数的来源做了另一番解释:直接暴力计算比照,you can you up!
/** DJBX33A (Daniel J. Bernstein, Times 33 with Addition)** This is Daniel J. Bernstein's popular `times 33' hash function as* posted by him years ago on comp.lang.c. It basically uses a function* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best* known hash functions for strings. Because it is both computed very* fast and distributes very well.** The magic of number 33, i.e. why it works better than many other* constants, prime or not, has never been adequately explained by* anyone. So I try an explanation: if one experimentally tests all* multipliers between 1 and 256 (as RSE did now) one detects that even* numbers are not useable at all. The remaining 128 odd numbers* (except for the number 1) work more or less all equally well. They* all distribute in an acceptable way and this way fill a hash table* with an average percent of approx. 86%.** If one compares the Chi^2 values of the variants, the number 33 not* even has the best value. But the number 33 and a few other equally* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great* advantage to the remaining numbers in the large set of possible* multipliers: their multiply operation can be replaced by a faster* operation based on just one shift plus either a single addition* or subtraction operation. And because a hash function has to both* distribute good _and_ has to be very fast to compute, those few* numbers should be preferred and seems to be the reason why Daniel J.* Bernstein also preferred it.*** -- Ralf S. Engelschall <rse@engelschall.com>*/除了DJBX33A哈希函数外,下面两个著名的哈希函数也是相似的做法:
- wiki:Bob Jenkin’s hash function
- wiki:Fowler–Noll–Vo hash function
- 参考资料[4]上列出了一共16种不同的非加密用的哈希函数
回到luaS_hash,与DJBX33A哈希函数是相似的,其中:
- 通过随机种子
unsigned int h = seed ^ cast_uint(l);来防御哈希碰撞攻击 - 通过
LUAI_HASHLIMIT控制step,通过控制step可以控制哈希计算的速度 (h<<5)与(h>>2)做混合
可以看到seed正是使用global_State里的seed,下面的代码验证了这点:
static TString *internshrstr (lua_State *L, const char *str, size_t l) { TString *ts; global_State *g = G(L); stringtable *tb = &g->strt; unsigned int h = luaS_hash(str, l, g->seed); TString **list = &tb->hash[lmod(h, tb->size)]; ...}而global_State->seed的初始化如下:
LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) { ... g->seed = luai_makeseed(L); ...}进一步,我们看下luai_makeseed(L);的代码:
static unsigned int luai_makeseed (lua_State *L) { char buff[3 * sizeof(size_t)]; unsigned int h = cast_uint(time(NULL)); int p = 0; addbuff(buff, p, L); /* heap variable */ addbuff(buff, p, &h); /* local variable */ addbuff(buff, p, &lua_newstate); /* public function */ lua_assert(p == sizeof(buff)); return luaS_hash(buff, p, h);}这就是随机种子初始化的地方,可以看到最后一句调用了luaS_hash来递归的生成种子本身,而buff,p,h就是初始值,其中h就是“生成随机种子的种子”,分拆下:
- 字符串
buff包含了heap variable,local variable,address of lua_newstate三种信息 - p就是buff的长度
- 而种子h使用时间函数
time来初始化,实际上客户可以在 luaconf.h 中配置 luai_makeseed 定义自己的随机方法。
待续
至此,我们分解清楚了global_State->seed的作用,以及luaS_hash函数背后的原理。下一次,我们会继续探究global_State-> l_registry。对技术背后原理的好奇,是前进的最大动力。
[1] https://en.wikipedia.org/wiki/Linear_congruential_generator
[2] https://stackoverflow.com/questions/1579721/why-are-5381-and-33-so-important-in-the-djb2-algorithm
[3] https://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function/13809282#13809282
[4] https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » [lua source code] luaS_hash