Lua源码中字符串类型的实现

410 /* 
411 ** Header for string value; string bytes follow the end of this structure 
412 */ 
413 typedef union TString { 
414  L_Umaxalign dummy; /* ensures maximum alignment for strings */ 
415  struct { 
416   CommonHeader; 
417   lu_byte extra; /* reserved words for short strings; "has hash" for longs */ 
418   unsigned int hash; 
419   size_t len; /* number of characters in string */ 
420  } tsv; 
421 } TString; 

48 /* type to ensure maximum alignment */ 
49 #if !defined(LUAI_USER_ALIGNMENT_T) 
50 #define LUAI_USER_ALIGNMENT_T  union { double u; void *s; long l; } 
51 #endif 
52    
53 typedef LUAI_USER_ALIGNMENT_T L_Umaxalign; 

74 /* 
75 ** Common Header for all collectable objects (in macro form, to be 
76 ** included in other objects) 
77 */ 
78 #define CommonHeader  GCObject *next; lu_byte tt; lu_byte marked 

81 /* 
82 ** Common header in struct form 
83 */ 
84 typedef struct GCheader { 
85  CommonHeader; 
86 } GCheader; 

 95 /* 
 96 ** creates a new string object 
 97 */                                                  
 98 static TString *createstrobj (lua_State *L, const char *str, size_t l,                
 99                int tag, unsigned int h, GCObject **list) {              
100  TString *ts;                                            
101  size_t totalsize; /* total size of TString object */                       
102  totalsize = sizeof(TString) + ((l + 1) * sizeof(char));                      
103  ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts; 
104  ts->tsv.len = l; 
105  ts->tsv.hash = h; 
106  ts->tsv.extra = 0;                                         
107  memcpy(ts+1, str, l*sizeof(char)); 
108  ((char *)(ts+1))[l] = '\0'; /* ending 0 */                            
109  return ts; 
110 }  

130 /* 
131 ** checks whether short string exists and reuses it or creates a new one 
132 */ 
133 static TString *internshrstr (lua_State *L, const char *str, size_t l) { 
134  GCObject *o; 
135  global_State *g = G(L); 
136  unsigned int h = luaS_hash(str, l, g->seed); 
137  for (o = g->strt.hash[lmod(h, g->strt.size)]; 
138    o != NULL; 
139    o = gch(o)->next) { 
140   TString *ts = rawgco2ts(o); 
141   if (h == ts->tsv.hash && 
142     ts->tsv.len == l && 
143     (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { 
144    if (isdead(G(L), o)) /* string is dead (but was not collected yet)"htmlcode">

119  stringtable strt; /* hash table for strings */ 


而类型stringtable是一个结构体，其定义如下（lstate.h）：


59 typedef struct stringtable {                                     
60  GCObject **hash; 
61  lu_int32 nuse; /* number of elements */ 
62  int size; 
63 } stringtable; 



其中成员GCObject **hash是一个指针数组，数组中每个成员实质指向TString（注意TString中包括宏CommonHeader，该宏中的next成员可以构造出Hash表中开散的链表）；nuse是数组hash中已经被使用的元素个数；size是当前数组hash的大小。
在函数newshrstr插入新的字符串前，都会判断nuse值是否大于size，若大于，表明Hash表大小不够需要扩充，则把Hash表的大小扩充到原来的2倍，对应的代码如下（lstring.c）:


121  if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)                 
122   luaS_resize(L, tb->size*2); /* too crowded */  



在gc的时候，会判断nuse是否比size/2还小（在Lua 5.1中是把nuse与size/4比较），如果是的话就重新resize这个stringtable的大小为原来的一半。对应的代码如下（lgc.c）：


783   int hs = g->strt.size / 2; /* half the size of the string table */               
784   if (g->strt.nuse < cast(lu_int32, hs)) /* using less than that half"htmlcode">

51 unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {               
52  unsigned int h = seed ^ l;                                     
53  size_t l1;                                             
54  size_t step = (l  LUAI_HASHLIMIT) + 1;                              
55  for (l1 = l; l1 >= step; l1 -= step)                                
56   h = h ^ ((h<<5) + (h2) + cast_byte(str[l1 - 1]));                       
57  return h;                                             
58 }  
21 /*                                                 
22 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to                 
23 ** compute its hash                                         
24 */                                                  
25 #if !defined(LUAI_HASHLIMIT)                                     
26 #define LUAI_HASHLIMIT   5                                    
27 #endif 



 （4）当有多个字符串连接时，不应该直接用字符串连接运算符”..”，而是用table.concat操作或者是string.format来加快字符串连接的操作。
 （5）Lua中字符串Hash算法用的是JSHash，关于字符串的各种Hash函数，网络有篇文章对它进行了总结：https://www.byvoid.com/blog/string-hash-compare
以上所述谁就是本文的全部内容了，希望能对大家学习lua有所帮助。