  lua-l archive

• Subject: Re: Question about luaH_newkey
• From: 重归混沌 <findstrx@...>
• Date: Tue, 25 Aug 2020 09:43:15 +0800

Sorry, I try to describe it in detail via a MWE.

`

local a = { --size = 8
 = nil,
 = nil,
 = nil,
 = nil,
 = nil,
}

-- now the hash part size of `a` is 8 and the a.lastfree(the structure in c language) = &a.node;

a = 1
a = 2
a = 3

--[[ the hash part has a chain

the chain:               a.node.next -> a.node.next -> a.node

|                |                |

the node key,val:        key=0,val=1      key=16,val=3     key=8,val=2

]]

a = nil

--[[ the hash part chain is as follow

the chain:               a.node.next -> a.node.next -> a.node

|                |                |

the node key,val:        key=0,val=1      key=16,val=nil     key=8,val=2

]]

a[8+6] = 4

--[[ the hash part chain is as follow

the chain:               a.node.next -> a.node.next -> a.node

|                |                |

the node key,val:        key=0,val=1      key=14,val=4     key=8,val=2

]]

a[8*2+6] = 5

--[[ the hash part chain is as follow

the chain:               a.node.next -> a.node.next -> a.node.next -> a.node

|                |                |                 |

the node key,val:        key=0,val=1      key=14,val=4       key=22,val=5      key=8,val=2

]]

So, In some extreme cases, the table operation sequence like: assign(main position), assign(conflict), assign(conflict), setnil(the last conflict key), assign(main position, which used by conflict key previous), and so on.

Is it possible that even if the hash conflict is not serious, the max chain size may be N/2-1(N is the hash part size).

Due to my poor English, it seems that it is difficult for me to clarify my question. If I have not made it clear, please let me know. Thank you very much

Roberto Ierusalimschy <roberto@inf.puc-rio.br> 于2020年8月24日周一 下午11:11写道：
> When I read the `luaH_newkey` function.
>
> I am a bit confused about the processing of mainposition(
> https://github.com/lua/lua/blob/master/ltable.c#L637) 。
>
> Even if the gval(mp) is empty, it still may be in some chain。of course, the
> result is still correct.
>
> Is it possible that in some extreme cases, all slots are in one chain.
>