哈希表与lua table(2)

上篇提到了lua的table采用闭散列的方式。下面来详细分析下table插入一个键值时的处理。

static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
  Node *mp = mainposition(t, key);
  if (!ttisnil(gval(mp)) || mp == dummynode) {
    Node *othern;
    Node *n = getfreepos(t);  /* get a free place */
    if (n == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /* grow table */
      return luaH_set(L, t, key);  /* re-insert key into grown table */
    }
    lua_assert(n != dummynode);
    othern = mainposition(t, key2tval(mp));
    if (othern != mp) {  /* is colliding node out of its main position? */
      /* yes; move colliding node into free position */
      while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
      gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
      *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
      gnext(mp) = NULL;  /* now `mp' is free */
      setnilvalue(gval(mp));
    }
    else {  /* colliding node is in its own main position */
      /* new node will go into free position */
      gnext(n) = gnext(mp);  /* chain new position */
      gnext(mp) = n;
      mp = n;
    }
  }
  gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
  luaC_barriert(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

情况1：用mainpostion计算key在这个数组的槽位，如果该槽位为空，那么直接使用这个槽位存储key
情况2：当mp不为空且othern == mp时，mp位置存储的值计算hash值也应该在这个槽位上，这个就是hash冲突了。

    else {  /* colliding node is in its own main position */
      /* new node will go into free position */
      gnext(n) = gnext(mp);  /* chain new position */
      gnext(mp) = n;
      mp = n;
    }

参考这段代码。我们可以得出冲突后用一个link到一个链表上，link到mp之后的一个节点。（特别注意的是这个往往会造成一个误解，这个并没有真的指针，只是存储了数据下标，所以他不是开散列，而是闭散列，存储数组下标作为next域）
情况3：当mp不为空，即有hash冲突，且本身mp槽位存储的值，本来不应该在这个槽位里。即表示这个值本身由于hash冲突，所以放到这个位置的。这里解决这个问题的办法是，讲原来存储在mp位置的上的值，重新挪到一个新的freepostion的槽位上去。

    if (othern != mp) {  /* is colliding node out of its main position? */
      /* yes; move colliding node into free position */
      while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
      gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
      *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
      gnext(mp) = NULL;  /* now `mp' is free */
      setnilvalue(gval(mp));
    }

othern这个位置是本该属于这个目前存储在mp槽位上值的槽位。所以从other这个往后找 一定可以找到mp，后面这个othern就是mp的前驱节点，然后修改othern的前驱节点只想n，然后把mp的内容拷贝到n上去。在把mp原来的next域设置为空。