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