Home > Archive > Java Help > April 2004 > Hash table bucket states
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Hash table bucket states
|
|
|
| Hi all,
I'm  about Closed Hash Tables (i.e. where each bucket is
occupied by up to one entry). I've read that each bucket in these
tables has three possible states;
never-occupied (if it has never been occupied)
occupied (if it is currently occupied)
formerly-occupied (if it previously contained an entry which has
previously
contained an entry but has not yet been replaced)
Why is it necessary to make the distinction between the first and the
last? It seems that when an object is inserted into the hashtable, it
doesn't matter whether its key points to a "never-occupied" bucket or
a "formerly-occupied" bucket - as long as it doesn't point to an
occupied bucket.
Cheers,
Andy
| |
| Eric Sosman 2004-04-21, 4:42 pm |
| Andy wrote:
>
> Hi all,
>
> I'm about Closed Hash Tables (i.e. where each bucket is
> occupied by up to one entry). I've read that each bucket in these
> tables has three possible states;
>
> never-occupied (if it has never been occupied)
> occupied (if it is currently occupied)
> formerly-occupied (if it previously contained an entry which has
> previously
> contained an entry but has not yet been replaced)
>
> Why is it necessary to make the distinction between the first and the
> last? It seems that when an object is inserted into the hashtable, it
> doesn't matter whether its key points to a "never-occupied" bucket or
> a "formerly-occupied" bucket - as long as it doesn't point to an
> occupied bucket.
(This isn't really a Java question -- it's about data
structures that aren't at all Java-specific. Still ...)
Insert object A in an empty hash table; it lands in its
"natural" bucket. Now insert object B that happens to have
the same "natural" bucket. B can't go there because that
bucket is already occupied by A, so B goes to some other,
second-choice bucket.
Now delete object A, and then search for object B. You
start by probing B's "natural" bucket, where A used to be.
B isn't there[*] because it went to its second-choice spot,
so you don't find B on the first probe. Now: Do you stop,
or do you continue probing? If you can't tell "never used"
from "used but vacated," you don't know what to do.
[*] This isn't necessarily true of all hash tables. Some
implementations do extra work when deleting objects,
moving the colliders "closer" to their "natural"
positions. But in implementations where objects aren't
shuffled around after being inserted, the first probe
for B will find the emptied spot left by A.
Any decent book on hashing will explain this; one oft-cited
(and much-feared, for reasons I've never understood) is "The Art
of Computer Programming, Volume III: Sorting and Searching" by
D.E. Knuth.
--
Eric.Sosman@sun.com
| |
|
| Thanks! That explanation helped a lot
> (This isn't really a Java question -- it's about data
> structures that aren't at all Java-specific. Still ...)
Sorry about off-topic question. I couldn't find a more appropriate
group and since I'm implementing these data structures in java I
thought I'd post here. If you recommend, I'll post a reference to the
code when I'm finished (since as far as I'm aware, Closed Hash Sets
don't come within the core java libs)
Andy
|
|
|
|
|