Re: stop searching
Bruce Guenter <[email protected]> Mon, 26 Aug 2002 17:41:55 -0600
| Newsgroups | gmane.comp.djb.cdb |
|---|---|
| Message-ID | <[email protected]> |
On Sat, Aug 24, 2002 at 05:16:48PM -0300, Gustavo Vieira Gonçalves Coelho Rios wrote: > Jeff King wrote: > > 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. > > 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. The standard cdbmake code ensures that the tables have twice as many slots in them as there are keys. This ensures there are many free slots so searches terminate quickly. -- Bruce Guenter <[email protected]> http://em.ca/~bruceg/ http://untroubled.org/ OpenPGP key: 699980E8 / D0B7 C8DD 365D A395 29DA 2E2A E96F B2DC 6999 80E8
signature.asc
(application/pgp-signature, 232 B)
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE9arzD6W+y3GmZgOgRAp7VAJ4nJ6mvYEONHBGQmPVdAcbWUzZ+tgCfcHGV 35InRdzm620JcxqF47pMFFs= =qOLP -----END PGP SIGNATURE-----