Re: ltable.c table deletion

[Josh Haberman <jhaberman@...>]

On Jan 31, 2012 at 2:06 PM, Doug Currie wrote:
> On Jan 31, 2012, at 3:01 PM, Josh Haberman wrote:
> > […]  it occurred to me that Brent's
> > variation (evicting a colliding element that is not in its main
> > position) prevents chain coalescing
>-
> No, it doesn't. Imagine a full hash table with all keys in their main
> position (perfectly hashed). All chains are coalesced.

Like Lua, I am using chained scatter (what you call "explicit
chaining" below), so in the scenario you describe every entry's "next"
pointer will be NULL and no chains will be coalesced.

> > […] I was surprised that Lua didn't
> > implement it.
>
> Note that Lua uses explicit chaining (with next fields in the TKey),
> so chains never coalesce at the expense of one link pointer per hash
> bucket.

Chains don't coalesce in Lua *only because* Lua uses Brent's variation.
With naive chained scatter they can coalesce, as described in my
original link, or to use an even simpler example, insert 1 into this
table (assume the identity hash for integers):

      val next
     +---+----+
  0  | 0 |  1 |--+
     +---+----+  |
  1  | 4 |    |<-+
     +---+----+
  2  |   |    |
     +---+----+
  3  |   |    |
     +---+----+

With naive chained scatter, you will see that 1's main position is
full and append to that chain, causing bucket 0's chain (containing 0
and 4, which both hash to 0) to coalesce with bucket 1's chain.  This
gives you a single chain of length 3.

      val next
     +---+----+
  0  | 0 |  1 |--+
     +---+----+  |
  1  | 4 |  2 |<-'
     +---+----+`-,
  2  | 1 |    |<-+
     +---+----+
  3  |   |    |
     +---+----+

With Brent's variation, to insert 1 into the original table above you
will see that 1's main position is full, but that its current occupant
(4) is not in its main position (0), so you'll evict it which prevents
the chains from coalescing.  This gives you two shorter chains instead
of one long one, which makes lookup faster.

      val next
     +---+----+
  0  | 0 |  1 |--+
     +---+----+  |
  1  | 1 |    |  |
     +---+----+  |
  2  | 4 |    |<-+
     +---+----+
  3  |   |    |
     +---+----+

And since the chains didn't coalesce, removal only requires you to
remove the target item from its own chain; no other chains are
affected.  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.

Josh