lua source code, when the key in table is of string type, the key value order is not unique

When the key is the key value of table, it will be mapped to the array according to the hash value of string.

The hash value of string will be copied to the hash when it is created

//lstring.c:167
static TString *internshrstr (lua_State *L, const char *str, size_t l) {
  TString *ts;
  global_State *g = G(L);
  unsigned int h = luaS_hash(str, l, g->seed);
...
  ts = createstrobj(L, l, LUA_TSHRSTR, h);
...
  return ts;
}

//lstring.c:133
static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
  TString *ts;
  GCObject *o;
  size_t totalsize;  /* total size of TString object */
  totalsize = sizelstring(l);
  o = luaC_newobj(L, tag, totalsize);
  ts = gco2ts(o);
  ts->hash = h;
  ts->extra = 0;
  getstr(ts)[l] = '\0';  /* ending 0 */
  return ts;
}

The hash seed, G - > seed, is used every time the hash is calculated. The hash seed is set to the current time every time it is started.

//lstate.c:295
LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
...
g->seed = makeseed(L);
...
}

//lstate.c:81
static unsigned int makeseed (lua_State *L) {
...
  unsigned int h = luai_makeseed();
...
}

//lstate.c:46
#define luai_makeseed()		cast(unsigned int, time(NULL))

 

 

The G - > seed of lua program will be different every time it starts, resulting in the same string and different hash value every time it starts. So every time we traverse the table, we will find that the order is different after the restart.

This is the mechanism added by lua5.3. There is no concept of hash seed in lua5.1. The following is the calculation of hsah value in lua5.1

//lua5.1 lstring.c:75
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  unsigned int h = cast(unsigned int, l);  /* seed */
  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
  size_t l1;
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    TString *ts = rawgco2ts(o);
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  return newlstr(L, str, l, h);  /* not found */
}

 

Posted on Fri, 01 Nov 2019 04:22:33 -0700 by rgermain