上篇提到了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域设置为空。
网友评论