Lua Table的理解

• 在table 中的散列表去取元素

  const TValue *luaH_get (Table *t, const TValue *key) {
    switch (ttype(key)) {
          // 傳入的key為Nil。直接返回nil
      case LUA_TNIL: return luaO_nilobject;
          // 如果是string類型。  
      case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
      case LUA_TNUMBER: {
        int k;
        lua_Number n = nvalue(key);
        lua_number2int(k, n);
        if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
          return luaH_getnum(t, k);  /* use specialized version */
        /* else go through */
      }
      default: {
        Node *n = mainposition(t, key);
        do {  /* check whether `key' is somewhere in the chain */
          if (luaO_rawequalObj(key2tval(n), key))
            return gval(n);  /* that's it */
          else n = gnext(n);
        } while (n);
        return luaO_nilobject;
      }
    }
  }
  
  const TValue *luaH_getstr (Table *t, TString *key) {
      // t->node[i] 獲取對應(yīng)的散列桶的位置
    Node *n = hashstr(t, key);
    do {  /* check whether `key' is somewhere in the chain */
        // 鏈表對應(yīng)的元素為string value->gc->ts == key 則在node中取出value
      if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
        return gval(n);  /* that's it */
      else n = gnext(n);  //上面沒有獲取則在Node->TKey->nk->next 查找到鏈表上的下一個元素
    } while (n);
    return luaO_nilobject;
  }
  
  const TValue *luaH_getnum (Table *t, int key) {
      // 先在數(shù)組查找.
    /* (1 <= key && key <= t->sizearray) */
    if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
      return &t->array[key-1];
    else {
        // 不滿足則在散列表中查找，重復(fù)上面的過程。先找到散列桶，遍歷鏈表進行查找。
      lua_Number nk = cast_num(key);
      Node *n = hashnum(t, nk);
      do {  /* check whether `key' is somewhere in the chain */
        if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
          return gval(n);  /* that's it */
        else n = gnext(n);
      } while (n);
      return luaO_nilobject;
    }
  }
  

• 直接插入元素。插入元素之前會根據(jù)傳入的key判斷TValue是否存在。分別是luaH_set ,luaH_setnum,luaH_setstr,三個func會根據(jù)傳入的key判斷TValue是否存在，如果存在則返回，但是內(nèi)部并不會進行實際的修改或添加。返回TValue* 修改會放在外面。分別看一下這三個Api

 - TValue *luaH_setstr (lua_State *L, Table *t, TString *key)
       TValue *luaH_setstr (lua_State *L, Table *t, TString *key) {
         const TValue *p = luaH_getstr(t, key);
           // 不是nil，則返回Tvalue
         if (p != luaO_nilobject)
           return cast(TValue *, p);
         else {
             // 如果不存在則重新new一個新的Tvalue。對應(yīng)的是Node的value。返回給外界。
           TValue k;
           setsvalue(L, &k, key);
           return newkey(L, t, &k);
         }
       }
       
       const TValue *luaH_getstr (Table *t, TString *key) {
           // 獲取對應(yīng)的散列桶
         Node *n = hashstr(t, key);
           // 遍歷鏈表取出對應(yīng)的節(jié)點Node的value返回。
         do {  /* check whether `key' is somewhere in the chain */
           if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
             return gval(n);  /* that's it */
           else n = gnext(n);
         } while (n);
         return luaO_nilobject;
       }
       
   
 -  TValue *luaH_setnum (lua_State *L, Table *t, int key)  
     TValue *luaH_setnum (lua_State *L, Table *t, int key) {
         //  根據(jù)數(shù)字找到對應(yīng)的TValue * 元素
       const TValue *p = luaH_getnum(t, key);
         // 有則直接返回,沒有則去創(chuàng)建一個新的TValue并返回。
       if (p != luaO_nilobject)
         return cast(TValue *, p);
       else { 
         TValue k;
         setnvalue(&k, cast_num(key));
         return newkey(L, t, &k);
       }
     }
     
     const TValue *luaH_getnum (Table *t, int key) {
         // 先在數(shù)組中去查找，如果key在數(shù)組的范圍內(nèi)key>0 < sizearray。則直接在數(shù)組中返回
       /* (1 <= key && key <= t->sizearray) */
       if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
         return &t->array[key-1];
       else {  // 否則的話則找到對應(yīng)的散列桶，然后遍歷鏈表去尋找到對應(yīng)的元素，返回Node對應(yīng)的Value對象。
         lua_Number nk = cast_num(key);
         Node *n = hashnum(t, nk);
         do {  /* check whether `key' is somewhere in the chain */
           if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
             return gval(n);  /* that's it */
           else n = gnext(n);
         } while (n);
         return luaO_nilobject;
       }
     }
     
 - const TValue *luaH_get (Table *t, const TValue *key)  是一個大的口子,在里面會根據(jù)傳入的key的類型，調(diào)用上面提到的get_number和getstr的func。當(dāng)找不到的時候回調(diào)用newKey 創(chuàng)建一個新的Value并返回給外界。
 - 插入一個新的key流程如下
       static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
           // 獲取散列桶的位置
         Node *mp = mainposition(t, key);
           // 如果存在的話。串聯(lián)到其他的散列桶下
         if (!ttisnil(gval(mp)) || mp == dummynode) {
           Node *othern;
           Node *n = getfreepos(t);  /* get a free place */
           if (n == NULL) {  /* cannot find a free place? */
             rehash(L, t, key);  /* grow table */
             return luaH_set(L, t, key);  /* re-insert key into grown table */
           }
           lua_assert(n != dummynode);
           othern = mainposition(t, key2tval(mp));
             // 讓n串到mp的next節(jié)點。n替換掉mp之前的位置。
           if (othern != mp) {  /* is colliding node out of its main position? */
             /* yes; move colliding node into free position */
             while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
             gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
             *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
             gnext(mp) = NULL;  /* now `mp' is free */
             setnilvalue(gval(mp));
           }
           else {  /* colliding node is in its own main position */
             /* new node will go into free position */
             gnext(n) = gnext(mp);  /* chain new position */
             gnext(mp) = n;
             mp = n;
           }
         }
          // 如果對于的桶不存在。則直接進行Node的key的賦值，并把空的Value返回。
         gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
         luaC_barriert(L, t, key);
         lua_assert(ttisnil(gval(mp)));
         return gval(mp);
       }

  

• 上面代碼當(dāng)找不到對應(yīng)的freeSpace的時候會觸發(fā)重散列的過程。在開發(fā)中我們盡量避免過多的重散列，過多的重散列是非常消耗性能的。

  static void rehash (lua_State *L, Table *t, const TValue *ek) {
    int nasize, na;
    int nums[MAXBITS+1];  /* nums[i] = number of keys between 2^(i-1) and 2^i */
    int i;
    int totaluse;
      // 初始化nums
    for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */
    nasize = numusearray(t, nums);  /* count keys in array part */
    totaluse = nasize;  /* all those keys are integer keys */
    totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
    /* count extra key */
    nasize += countint(ek, nums);
    totaluse++;
    /* compute new size for array part */ // 對數(shù)組部門進行重新排列
    na = computesizes(nums, &nasize);
    /* resize the table to new computed sizes */  // 對散列表進行調(diào)整。
    resize(L, t, nasize, totaluse - na);
  }
  

  保存到array中的原則。所含元素的數(shù)量大于50%的最大索引。數(shù)組在每個2次方索引 容納元素的數(shù)量大于50%。
  

  key保存在數(shù)組中的位置為
  image.png

• 比如number[0] = 1; 滿足 key為1 滿足上面的條件。而且 數(shù)組數(shù)量1 >
  image.png
  
  

  同理可以繼續(xù)分析

• number[1] = 1; 滿足數(shù)量2>
  image.png

• number[5] = 1 4不滿足
  image.png
  
  

  。因此key為5分到散列表
  具體的重排列算法如下

      static int computesizes (int nums[], int *narray) {
        int i;
        int twotoi;  /* 2^i */
        int a = 0;  /* number of elements smaller than 2^i */
        int na = 0;  /* number of elements to go to array part */
        int n = 0;  /* optimal size for array part */
        for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
          if (nums[i] > 0) {
            a += nums[i];
            if (a > twotoi/2) {  /* more than half elements present? */
              n = twotoi;  /* optimal size (till now) */
              na = a;  /* all elements smaller than n will go to array part */
            }
          }
          if (a == *narray) break;  /* all elements already counted */
        }
        *narray = n;
        lua_assert(*narray/2 <= na && na <= *narray);
        return na;
      }

排列完數(shù)組后會對散列表部分進行resize。代碼如下

static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
  int i;
    // 數(shù)組的size 
  int oldasize = t->sizearray;
    // 散列表大小的
  int oldhsize = t->lsizenode;
  Node *nold = t->node;  /* save old hash ... */
    // size 變大。則 重新分配數(shù)組和散列表
  if (nasize > oldasize)  /* array part must grow? */
    setarrayvector(L, t, nasize);
  /* create new hash part with appropriate size */
  setnodevector(L, t, nhsize);  
    // 數(shù)組變下，則分配數(shù)組元素到散列表上
  if (nasize < oldasize) {  /* array part must shrink? */
    t->sizearray = nasize;
    /* re-insert elements from vanishing slice */
      // nasize大小開始到新的大小，
    for (i=nasize; i<oldasize; i++) {
      if (!ttisnil(&t->array[i]))
          //對應(yīng)值設(shè)置到散列表上
        setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
    }
    /* shrink array */  /* 重新分配數(shù)組空間，去掉后面溢出部分*/
    luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
  }
  /* re-insert elements from hash part */  將舊的散列表上的Node從后到前設(shè)置到新的散列表上
  for (i = twoto(oldhsize) - 1; i >= 0; i--) {
    Node *old = nold+i;
    if (!ttisnil(gval(old)))
      setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
  }
    // 釋放老的hash表空間
  if (nold != dummynode)
    luaM_freearray(L, nold, twoto(oldhsize), Node);  /* free old array */
}