lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Jan 31, 2012, at 7:05 PM, Josh Haberman wrote:

> This is the key result that I realized but couldn't find
> published anywhere, which made me wonder whether this was previously
> known.  All algorithms I could find published used the (much) more
> complicated and expensive removal algorithm.

… which saves a next pointer at every bucket. I.e., the cost of the simpler deletion algorithm is a next pointer at every bucket, a cost that many implementations go to great pains to avoid (because cutting the size of the hash table fits more of it in cache). [Lua's hash table is a great piece on engineering, and I'm not knocking it, just trying to point out why many other implementations make different choices.]

-- e