Re: 【lua table】Different hashes are chained together，is it bug？

[Javier Guerra Giraldez <javier@...>]

On Fri, 17 Apr 2020 at 21:15, 彭健 <bzijiang@gmail.com> wrote:
>      Thanks for the answer. I think it is a bit different from usual. In my understanding, keys with different hash_value will be chained to different buckets.

there are many schemes to solve collisions in a hash table.  what you
describe is sometimes called "separate chaining".  and sometimes is
the first one described in textbooks, since it's simple to visualize
and it doesn't create new collisions.

The method  used in Lua tables is sometimes called open addressing or
(confusingly) closed hashing.  It stores all the entries in the same
table, therefore it creates new collisions and can easily join
separate chains, as you've observed.  At first it seems like a bad
strategy, but it results in a significantly better performance
because of much better cache locality and far less memory allocations
and fragmentation.



-- 
Javier