 |
lua-l archive |
|
|
||
|
Sorry, I try to describe it in detail via a MWE.
`
local a = { --size = 8
[16] = nil,
[17] = nil,
[18] = nil,
[19] = nil,
[20] = nil,
}
-- now the hash part size of `a` is 8 and the a.lastfree(the structure in c language) = &a.node[8];
a[0] = 1
a[8] = 2
a[16] = 3
--[[ the hash part has a chain
the chain: a.node[0].next -> a.node[6].next -> a.node[7]
| | |
the node key,val: key=0,val=1 key=16,val=3 key=8,val=2
]]
a[16] = nil
--[[ the hash part chain is as follow
the chain: a.node[0].next -> a.node[6].next -> a.node[7]
| | |
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[0].next -> a.node[6].next -> a.node[7]
| | |
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[0].next -> a.node[6].next -> a.node[5].next -> a.node[7]
| | | |
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
> 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.
>
> Please help me to point it out, if I have some mistakes. Thank you very
> much.
I am afraid I have not understood what you want to know.
-- Roberto