[lua source code] luaS_hash

作者 : 开心源码 本文共5973个字,预计阅读时间需要15分钟 发布时间: 2022-05-12 共264人阅读

上一节对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)),它的算法如下:

N_{j+1}===(A*N_j+B)(mod M)

LCG算出来的伪随机数序列在模M之后就是一个周期整数序列,周期的大小决定了碰撞的概率。LCG的周期最大是M,但大部分情况都会少于M,假如要让LCG达到最大周期,应该要符合以下Hull–Dobell Theorem条件:

  1. B,M互质
  2. M的所有质因子都能整除A-1
  3. 若M是4的倍数,A-1也是。
  4. A,B,N_0都比M小
  5. 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递归算法的一个中间步骤。比照一下公式,可以看到:

  • N_{j+1}=左边的hash
  • N_j=右边的hash
  • A=33
  • B=str[i],str是ASCII字符串,str[i]是8 bits,从而B是[0,256)范围内的整数。
  • M=2^{32}(或者者 2^{64},取决于int的位数)

可以看到A,B,M满足如下的几个性质:

  • 假如B是奇数,B和M互质,至少一半的概率
  • M的所有质因子是2,它可以整除A-1=32
  • M(2^{32} 或者者 2^{64} )是4的倍数,A-1=32也是4的倍数
  • A,B,N_0都比M小
  • A,B是正整数(除0外)。

因而DJBX33A这个哈希函数具备很好的最大周期性,从而尽可能减少碰撞。但这只解释了一半起因,另一半起因是:

  • A选择33这个接近2^n的数字,可以充分利用计算机里面用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

发表回复