上一节对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.c
unsigned 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(
- A，B，
- 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
