Re: stop searching

Jeff King wrote:
> 
> On Sat, 24 Aug 2002, Gustavo Vieira Gonçalves Coelho Rios wrote:
> 
> > In a linear probing scheme, how may i determine is time to stop
> > searching for a key?
> > That's to say: a table with k slots size and all them fullfilled!
> 
> If you've searched all 'k' slots and not found the key, then it's not
> there. :)
> 
> If you're referring specifically to cdb, http://cr.yp.to/cdb/cdb.txt
> says:
> 
>   Probe that slot, the next higher slot, and so on, until
>   you find the record or run into an empty slot.
> 
> So if there is a gap in the table, you know to stop searching. I don't
> know if Dan also adds a sentinel slot at the end of the table that is
> empty (since you already know the table size and can avoid exceeding
> it). I'd have to look at the code to be sure.
> 
> -Peff

But if you think that in a linear probe scheme, a table with k slots
will be completely full by k register, so, there will not be any empty
solt, right? And if you allows a cyclic search, you will only be able to
known you have seek the whole table when starting from k mod n you
increment k until k mod n is k (original) again.

This may work if you have fill hundred of register, but if have in the
order of 10 ^ 8 register, this may be slow. isn't it?