Re: Behavior of newkey(): intentional?

[roberto@... (Roberto Ierusalimschy)]

> I've been examining the rather neat hash algorithm+implementation in
> lua 5. I have been trying to figure out this line of code in newkey(),
> the one that checks whether the mainposition is used or not:
> 
>   if (!ttisnil(gval(mp))) {  /* main position is not free? */
> 
> In particular, I'm curious why it checks gval(mp) instead of gkey(mp).
> In the case that mp _was_ used In this case, the new key will get its
> mainposition, but it will re-use the old chain.
> 
> [...]
> 
> So, it seems like checking gkey(mp) would keep the chains separate, at
> the cost of increasing the amount of re-hashing (moving an item out of
> mainposition uses up a free node). Is this in fact the tradeoff that's
> being made?

Yes. As far as I remember, the difference between both implementations
is small. (Such "collisions" are rare.) The main reason for the use of
gval is that it is more consistent with the rest of the code, which
always assumes that gval=nil means an empty slot. (In particular, Lua
never accesses the gkey of an empty slot.)

-- Roberto