[lua source code] luaS_hash

上一節(jié)對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內(nèi)部包含了下面這些重要部分：

  • 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指向了版本指針，通常我們發(fā)布程序版本號都是外置的，Lua把版本號內(nèi)置在全局狀態(tài)里，使得可以在運行時動態(tài)判斷自己的版本號。

而，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的代碼沒什么道理可言，其實一步步展開還是能理解的。首先，哈希函數(shù)有兩類：

  • 加密用的哈希函數(shù)，例如SHA-256, SHA-512, MD5, RIPEMD-160等
  • 非加密用的哈希函數(shù)

luaS_hash即屬于非加密用的哈希函數(shù)，在散列表里的主要作用是：

  • 把輸入字符串隨機映射到散列表的索引范圍[0, len-1]內(nèi)
  • 哈希應(yīng)該在[0,len-1]內(nèi)盡量符合均勻分布(Unifrom)，也就是合法的輸入被映射到[0,len-1]中任何一個地址的概率是相等的，這就使得輸入經(jīng)過哈希后可以得到一個“隨機的地址”，以減少碰撞。

可見，它本質(zhì)上是一種偽隨機數(shù)生成器，而我們知道偽隨機數(shù)生成器最古典的就是線性同余方法(wiki:Linear congruential generator(LCG))，它的算法如下：

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

LCG算出來的偽隨機數(shù)序列在模M之后就是一個周期整數(shù)序列，周期的大小決定了碰撞的概率。LCG的周期最大是M，但大部分情況都會少于M，如果要讓LCG達到最大周期，應(yīng)該要符合以下Hull–Dobell Theorem條件：

  1. B，M互質(zhì)
  2. M的所有質(zhì)因子都能整除A-1
  3. 若M是4的倍數(shù)，A-1也是。
  4. A，B，N_0都比M小
  5. A，B都是正整數(shù)

LCG本身只是偽隨機數(shù)生成器，需要滿足均勻分布以減少碰撞才能在散列表里面使用。因此一個非密碼學(xué)使用的哈希函數(shù)是否足夠好（good hash function)，就要看它是否足夠均勻分布。

先看一個常見的Hash函數(shù)的實現(xiàn)，叫做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循環(huán)里做的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)范圍內(nèi)的整數(shù)。
  • M=2^{32}（或者 2^{64}，取決于int的位數(shù)）

可以看到A，B，M滿足如下的幾個性質(zhì)：

  • 如果B是奇數(shù)，B和M互質(zhì)，至少一半的概率
  • M的所有質(zhì)因子是2，它可以整除A-1=32
  • M(2^{32} 或者 2^{64} )是4的倍數(shù)，A-1=32也是4的倍數(shù)
  • A，B，N_0都比M小
  • A，B是正整數(shù)（除0外）。

因此DJBX33A這個哈希函數(shù)具有很好的最大周期性，從而盡可能減少碰撞。但這只解釋了一半原因，另一半原因是：

  • A選擇33這個接近2^n的數(shù)字，可以充分利用計算機里面用shift-and-add的方式計算乘法，即：h^33 = h^32+h = (h<<5)+h
  • 假設(shè)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互質(zhì)，也有利于多次迭代中讓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里的這幾個魔數(shù)的來源做了另一番解釋：直接暴力計算對比，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哈希函數(shù)外，下面兩個著名的哈希函數(shù)也是類似的做法：

回到luaS_hash，與DJBX33A哈希函數(shù)是類似的，其中：

  • 通過隨機種子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);
}

這就是隨機種子初始化的地方，可以看到最后一句調(diào)用了luaS_hash來遞歸的生成種子本身，而buff,p,h就是初始值，其中h就是“生成隨機種子的種子”，分拆下：

  • 字符串buff包含了heap variable,local variable,address of lua_newstate三種信息
  • p就是buff的長度
  • 而種子h使用時間函數(shù)time來初始化，實際上用戶可以在 luaconf.h 中配置 luai_makeseed 定義自己的隨機方法。

待續(xù)

至此，我們分解清楚了global_State->seed的作用，以及l(fā)uaS_hash函數(shù)背后的原理。下一次，我們會繼續(xù)探索global_State-> l_registry。對技術(shù)背后原理的好奇，是前進的最大動力。

[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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪：刷leetcod...
    土汪閱讀 12,927評論 0贊 33
  • 賣西瓜的老人 “賣西瓜，薄皮沙瓤大西瓜，不甜不要錢?！?一陣蒼老的叫賣聲傳入正在睡午覺的我的耳膜，透過窗戶，看見一...
    5780933168ec閱讀 517評論 4贊 2
  • 今早下班回家，看到兒子沒去托輔。怎么還不去托輔？媽媽，我在家復(fù)習(xí)。一想，也是，要不在家復(fù)習(xí)吧。這幾天身體...
    翔兒媽媽閱讀 167評論 0贊 0
  • 前兩天，三年多沒聯(lián)系的朋友突然給我打電話，看到來電的那一瞬間有些意外，接起來也是打了聲招呼就不知道說些什么了。 電...
    粟說saying閱讀 1,035評論 0贊 0

友情鏈接更多精彩內(nèi)容