Stay Hungry.Stay Foolish.
lua数据结构之hashtable

typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of 'node' array */
  unsigned int alimit;  /* "limit" of 'array' array */
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  struct Table *metatable;
  GCObject *gclist;
} Table;
  • lua内核的hash表分两部分,一部分是数组存放,一部分是真正的键值对hash表;
  • lua内核的hashtable实现和别的有点不一样,使用的是连续数组方式,hashtable的node指针指向连续内存地址的hashnode的首地址;
typedef struct TValue {
  Value value_; 
   lu_byte tt_;
} TValue;

typedef union Node {
  struct NodeKey {
   Value value_; 
    lu_byte tt_;
    lu_byte key_tt;  /* key type */
    int next;  /* for chaining */
    Value key_val;  /* key value */
  } u;
  TValue i_val;  /* direct access to node's value as a proper 'TValue' */
} Node;
  • Node 结构体其实就保存了两个值,一个key,一个value,使用联合体的目的注释有说明为了方便可以直接访问value,估计是为了遍历值?
  • 使用了闭散列法解决hash冲突,next域保存了碰撞元素的偏移位置(即,所有的值都存在于表中。如果hash 发生碰撞,额外的数据记在空闲槽位里,而不额外分配空间存放。当整个个表放满后,hash 段会扩大,所有段内的数据将被重新 hash ,重新 hash 后,冲突将大大减少。)

typedef union Value {
  struct GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  int b;           /* booleans */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;
  • 关于 value结构体,是个非常复杂的联合体,承载着存储lua所有的数据类型
自由转载-非商用-非衍生-保持署名(创意共享3.0许可证
评论

暂无评论~~