lua-users home
lua-l archive

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

On Wed, Feb 1, 2012 at 2:19 AM, Mike Pall <> wrote:
Josh Haberman wrote:
> Is there a reason for this?

1. To allow deletion of values during a table traversal.

  If the key was removed, too, the traversal would lose its
  anchor. This is because traversals in Lua are incremental,
  based on the previous key, and don't need extra context
  (e.g. a hash table position).

  [LuaJIT tries to use a hidden context to speed up traversals.]

2. To preserve the key slot in the table.

  Fields that toggle from non-nil to nil and back do not need to
  create a new key in the table every time. Creating a new key is
  substantially more expensive than re-using an existing key slot.

These make sense.
3. To save work.

  Removing individual keys is expensive, because you'll need to
  traverse the whole chain for each key.

Just wanted to clarify that by "each" key you mean "the chain
of the key you are removing."  You *don't* have to traverse all
chains in the hash table to perform a single deletion if you avoid
coalescing (that's the result I discovered but couldn't find published).

Also I wanted to point out that the average length of each chain
for a good hash function is very short (even at 100% load), so
deletions would be O(1) on average but O(n) worst-case (ie.
just like insertions).

But clearly the other two reasons outweigh any potential benefits
of performing actual table deletions.