Re: Suggestions for double-hashing scheme

websnarf@xxxxxxxxx writes:

> Clint Olsen wrote:
>> On 2005-05-26, websnarf@xxxxxxxxx <websnarf@xxxxxxxxx> wrote:
>> > Yeah, you have to be careful not to overdo it though. For example, you
>> > cannot just arbitrarily swap any found entry to the front, or with just
>> > any entry that isn't marked as deleted. Because entries along the probe
>> > sequence may be part of another probe sequence. This is one of the
>> > weaknesses of double-hashing style strategies. (With straight
>> > linear/constant hashing, you can do this, but this has far worse worst
>> > case scenarios.)
>>
>> As long as it's on it's probe sequence, it seems like you're safe to swap a
>> valid cell with a deleted cell. By definition, a probe sequence skips
>> through any occupied or deleted cell in the hopes of finding the object.
>> It's when you come to an empty slot you know it's not there. Minimizing
>> the time for this is important.
>
> Yeah, I'm just saying that the "move to front" heuristic works if you
> are swapping a found entry with an earlier "deleted" entry. But it
> does *not* work if you simply swap found entries with the first entry
> (for example) even though it would seem like a good idea to do this
> from a performance point of view.

I believe that you're discussing an algorithm for deleting from a
hash table with linear probing. I think that if you take this
discussion to its logical conclusion, you end up with Knuth's
Algorithm 6.4R (Deletion with linear probing).

Knuth also states that no similar algorithm is possible when
double hashing is used. This is one reason that one of my own
hash libraries doesn't use double hashing.
--
"Premature optimization is the root of all evil."
--D. E. Knuth, "Structured Programming with go to Statements"
.

Relevant Pages

  • Re: Suggestions for double-hashing scheme
    ... >> any entry that isn't marked as deleted. ... Because entries along the probe ... >> sequence may be part of another probe sequence. ... then they will both intersect an additional ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... > swapping a found entry with an earlier "deleted" entry. ... > *not* work if you simply swap found entries with the first entry (for ... > (If a previous probe sequence were to wrap around the edge of the lower ... we use the assumption that for a given initial hash index ...
    (comp.programming)
  • Re: Parameter query options...
    ... >Yeah, the field is open to any entry, which I know is a problem. ... >point it's going to be a major hassle to go back and clean that up so I was ... price at any software company in the world. ...
    (microsoft.public.access.queries)
  • Re: Display next to last results
    ... Yeah, that is a lot better than mine. ... > Microsoft Excel MVP ... >> If there are gaps in your data, ... >>> This formula works great to find the last entry in a col. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Switches to use C++ STL
    ... Yeah, thats it. ... I had to do one additional step though,but that was while linking just to ... get the CRT initialized I had to point the entry ...
    (microsoft.public.development.device.drivers)