当table插入新值而没有空位的时候,会触发rehash

static TValue *newkey(gafq_State *L, Table *t, const TValue *key)
{
    Node *mp = mainposition(t, key); // 获取主要位置
    if (!ttisnil(gval(mp)) || mp == dummynode)
    {
        Node *othern;
        Node *n = getfreepos(t); // 获取一个空位置
        if (n == NULL)
        {                               
            rehash(L, t, key);          // 没有找到空位置就重新算hash
            return gafqH_set(L, t, key);
        }
}
static void rehash(gafq_State *L, Table *t, const TValue *ek)
{
    int nasize, na;
    int nums[MAXBITS + 1]; /* nums[i] = number of keys between 2^(i-1) and 2^i */
    int i;
    int totaluse;
    for (i = 0; i <= MAXBITS; i++)
        nums[i] = 0;                          // 重置数组数量?
    nasize = numusearray(t, nums);            // 计算数组部分的key的数量
    totaluse = nasize;                        // 所有整数的key的数量
    totaluse += numusehash(t, nums, &nasize); // 哈希表部分的key数量
    nasize += countint(ek, nums); // 新加的key 会不会加到整数部分
    totaluse++;
    na = computesizes(nums, &nasize); // 重新计算数组部分
    /* resize the table to new computed sizes */
    resize(L, t, nasize, totaluse - na);
}

1. 在rehash中首先计算数组部分使用的数量

// 统计array部分数量
static int numusearray(const Table *t, int *nums)
{
    int lg;
    int cur_max_lg;     /* 2^lg */
    int all_use_count = 0; // 计算使用的数字类型的key数量
    int check_array_index = 1;    // 遍历所有数字key
    for (lg = 0, cur_max_lg = 1; lg <= MAXBITS; lg++, cur_max_lg *= 2)
    {               /* for each slice */
        int lc = 0; // 每一小部分的使用的数字的数量
        int cur_limit = cur_max_lg;
        if (cur_limit > t->sizearray)
        {
            cur_limit = t->sizearray; // 最多直到当前数组的大小
            if (check_array_index > cur_limit)//检查超过了
                break;
        }
        /* count elements in range (2^(lg-1), 2^lg] */
        for (; check_array_index <= cur_limit; check_array_index++)
        {
            if (!ttisnil(&t->array[check_array_index - 1]))
                lc++;
        }
        nums[lg] += lc;
        all_use_count += lc;
    }
    return all_use_count;
}

1. 接着计算hash部分使用的数量

// 统计哈希部分的数量
static int numusehash(const Table *t, int *nums, int *pnasize)
{
    int totaluse = 0; // 哈希部分使用的总量
    int all_use_count = 0;     // 使用的数量
    int i = sizenode(t);
    while (i--)
    {
        Node *n = &t->node[i];
        if (!ttisnil(gval(n)))
        {
            all_use_count += countint(key2tval(n), nums);
            totaluse++;
        }
    }
    *pnasize += all_use_count;
    return totaluse;
}

1. 计算数组部分的大小

static int computesizes(int nums[], int *narray)
{
    int i;
    int twotoi; /* 2^i */
    int a = 0;  /* number of elements smaller than 2^i */
    int na = 0; /* number of elements to go to array part */
    int n = 0;  /* optimal size for array part */
    for (i = 0, twotoi = 1; twotoi / 2 < *narray; i++, twotoi *= 2)
    {
        if (nums[i] > 0)
        {
            a += nums[i];
            if (a > twotoi / 2)
            {               /* more than half elements present? */
                n = twotoi; /* optimal size (till now) */
                na = a;     /* all elements smaller than n will go to array part */
            }
        }
        if (a == *narray)
            break; /* all elements already counted */
    }
    *narray = n;
    gafq_assert(*narray / 2 <= na && na <= *narray);
    return na;
}

1. 重新计算resize

// 重新计算 根据 当前数组使用数量nasize 和 hash使用数量nhsize
static void resize(gafq_State *L, Table *t, int nasize, int nhsize)
{
    int i;
    int oldasize = t->sizearray;
    int oldhsize = t->lsizenode;
    Node *nold = t->node;  // 旧的hash数量
    if (nasize > oldasize) // 需要增加数组部分
        setarrayvector(L, t, nasize);
    setnodevector(L, t, nhsize); // 创建哈希位置
    if (nasize < oldasize) // 数组部分变少了
    {
        t->sizearray = nasize;
        for (i = nasize; i < oldasize; i++)
        {
            if (!ttisnil(&t->array[i]))
                setobjt2t(L, gafqH_setnum(L, t, i + 1), &t->array[i]);
        }
        // 减少array
        gafqM_reallocvector(L, t->array, oldasize, nasize, TValue);
    }

   // 重新插入哈希部分
    for (i = twoto(oldhsize) - 1; i >= 0; i--)
    {
        Node *old = nold + i;
        if (!ttisnil(gval(old)))
            setobjt2t(L, gafqH_set(L, t, key2tval(old)), gval(old));
    }
    if (nold != dummynode)
        gafqM_freearray(L, nold, twoto(oldhsize), Node); /* free old array */
}