Lua中的字符串--读《Lua设计与实现》笔记

概述

表示字符串的最主要的两个数据：

    1.字符串的长度

    2.指向存放字符串内存数据的指针

Lua中的字符串

1.在Lua虚拟机中存在一个全局的数据区，用来存放当前系统中的所有字符串

2.同一个字符串数据，在Lua虚拟机中只可能有一份副本，一个字符串一旦创建，将是不可变更的

3.变量存放的仅是字符串的引用，而不是其实际的内容

lua字符串的有点在于：

1、空间优化，多份相同的字符串在整个系统中只存在一份

2、在进行字符串查找时，性能会提升不少。传统的字符串比较算法是根据字符串的长度逐位进行进行比较，这个时间复杂度与字符串的长度线性相关；而优化后通过散列值的进行一次整数的比较即可。

Lua将字符串存在global_state的strt成员

（lstate.h）
typedef struct stringtable {
  TString **hash;
  int nuse;  /* number of elements */
  int size;
} stringtable;

当新创建一个字符串TString时，首先根据散列算法算出散列值，这就是strt数组的索引值。如果这里已经有元素，则用链表串接起来，（与Java中的Hashtable实现原理类似）

 

当数据量很大的时候，分配到每个桶上数据也会非常多，这样一次查询也退化为线性查询，lua采用重新散列，增加桶的数目来解决该问题。

（lstring.c）
/*
** resizes the string table
*/
void luaS_resize (lua_State *L, int newsize) {
  int i;
  stringtable *tb = &G(L)->strt;
  if (newsize > tb->size) {  /* grow table if needed */
    luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *);
    for (i = tb->size; i < newsize; i++)
      tb->hash[i] = NULL;
  }
  for (i = 0; i < tb->size; i++) {  /* rehash */
    TString *p = tb->hash[i];
    tb->hash[i] = NULL;
    while (p) {  /* for each node in the list */
      TString *hnext = p->u.hnext;  /* save next */
      unsigned int h = lmod(p->hash, newsize);  /* new position */
      p->u.hnext = tb->hash[h];  /* chain it */
      tb->hash[h] = p;
      p = hnext;
    }
  }
  if (newsize < tb->size) {  /* shrink table if needed */
    /* vanishing slice should be empty */
    lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL);
    luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *);
  }
  tb->size = newsize;
}

在Lua中应该尽量减少使用字符串连接，因为每一次都会生成一个新的字符串。（可以使用table来模拟字符串缓冲区，避免大量使用连接操作符）