Re: [boost] Container suggestions (was: Re: BOOST_NO_HASH)

From: Beman Dawes (beman_at_[hidden])
Date: 2001-01-09 21:02:21

At 09:21 AM 1/8/2001 -0800, Matthew Austern wrote:

 >Yes, this is called "open addressing".  It's described in Knuth.
 >
 >I thought a lot about using open addressing for an STL-style hashtable
 >implementation, and I never figured out a reasonable way to do it.
 >Here are the problems that I saw:
 >
 > - Erasing is hard when you use open addressing.  The problem is that
 >   an element with a given hash code might be in one of several
 >   places.  If it's in slot B, you can only find it if you know that
 >   there's something already there in slot A.  So what happens if
 >   you had something in slot A, and you've now erased it?  The usual
 >   way around this is to set a bit in slot A saying that there was
 >   something there and now it's gone.
 > - It doesn't interact very well with general C++ types, where you
 >   have to worry about invoking constructors and destructors.
 > - It doesn't interact very well with automatic resizing.  All of
 >   the discussions of open addressing that I've seen assume fixed
 >   sized tables.
 >
 >In principle, the advantage of open addressing is that you can get
 >some space saving.  I don't know if that's a big enough advantage to
 >be worth the pain.

FWIW, I've implemented open addressing several times, and always been 
dissatisfied.  Too sensitive to distribution of hashing function, choice of 
loading factor, etc.  Quite a bit more fragile than any of several chaining 
schemes.

--Beman