0x1. 结构定义

  1. typedef struct Table {
  2.     CommonHeader;
  3.     lu_byte flags;  /* 1<<p means tagmethod(p) is not present */ 
  4.     lu_byte lsizenode;  /* log2 of size of `node' array */
  5.     struct Table *metatable;
  6.     TValue *array;  /* array part */
  7.     Node *node;
  8.     Node *lastfree;  /* any free position is before this position */
  9.     GCObject *gclist;
  10.     int sizearray;  /* size of `array' array */
  11. } Table;

node字段即为hash桶，array字段是table的一个优化，如果key是数字并且比较小的话就保存到数组里面，以提高性能。

typedef union TKey {
  struct {
    TValuefields;
    struct Node *next;  /* for chaining */
  } nk;
  TValue tvk;/*这个和nk里面的TValuefields是一样的结构*/
} TKey;


typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

这里的TKey里面的tvk比较令人疑惑，这里解释下。这个其实和nk里面的TValuefields是一样的定义，而且这是个union类型，所以访问tvk和访问nk的TValuefields是一样的内容。这样子就可以将TKey转化为一个Tvalue的格式，因为有的接口参数是使用TValue的。这个手发在lua里面很常见。

0x2. hash表

想要实现一个hash表就要解决几个问题：

  • hash函数
  • hash冲突如何处理
  • 扩容

hash函数

由于table是支持各种不同类型的key，所以这里的hash函数会根据具体的类型用不同的hash函数。

hash冲突

lua中解决hash冲突不是常见的链式解决方案，有点像是线性探测和链式的合并。这里首先介绍一个概念main position。一个key对应的main position为该key的桶索引。
image.png

rehash

这个和常见的基本一样，也就是申请内存，重新插入。