|
Notes |
|
|
|
Non-version hash tables, i.e. in library/hash_table.m, exhibit the same behaviour.
I'll add a test case for them too. |
|
|
|
|
The bug can be reproduced with just the following keys:
"abandoned",
"abase",
"abases" |
|
|
|
(0000120)
|
|
wangp
|
|
2008-08-07 16:38
|
|
I think the problem is this:
find_slot(HT, K) looks up key K in hash table HT and
returns the index for the entry K in H. This is either the
first free slot identified (K is not in the table, but here
is where it would go) or the slot for K (K is in the table
and this is its slot).
Whether or not K is actually in the table can be decided
by checking to see whether its bit in the bitmap is set
or clear.
That's fine if keys never get deleted. But say two keys K1, K2 both
want to go into slot S1. K1 gets there first, so K2 must reprobe and
go into slot S2. Delete K1 so slot S1 becomes free. If you try to
search for K2, it won't be found since S1 is free so it won't bother
to look in S2. |
|
|
|
|
That's what I had concluded as well - I was just waiting for a workspace with deep tracing
in the library directory to compile in order to confirm it. For this sort of hash table the
deletion algorithm needs to traverse the entire array until it finds the key it is deleting
or until it get backs to where it starts. |
|
|
|
|
Actually, supporting deletion at all would mean that you could insert duplicate keys
into the table without it being detected - maybe we should just not support deletion?
|
|
|
|
(0000123)
|
|
wangp
|
|
2008-08-07 16:58
|
|
|
Let's just switch to separate chaining. Deleting is important. |
|
|
|
|
|
vht_delete.m (1,341) 2008-07-14 10:44