Re: cdb format: hash table slots

--M9NhX3UHpAaciwkO
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Fri, Apr 11, 2008 at 06:18:42PM +0100, David Farrar wrote:
> In this particular case, (hash / 256) % 4 =3D (2417049413 / 256) % 4 =3D =
3,=20
> meaning that I skip past the value I'm looking for (jumping straight to=
=20
> 'thomas.mangin') and falsely report that the key does not exist.

What is missing from the above paragraph is that the slots are
essentially a circular buffer.  So, after probing slot 3, you should
then probe the next slot, which is slot *0*.  There you find your hash
key, and the referenced data is what you want.  This is normally how
linearly probed hash tables work.

--=20
Bruce Guenter <[email protected]>                http://untroubled.org/

--M9NhX3UHpAaciwkO
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)

iD8DBQFICtkU6W+y3GmZgOgRAmy2AJwPELCd5/FAT6oHPYJp1wB9sc3mCwCdHyzq
Z/pPpfJj3uMkNmVU3Q5GGS8=
=DZpO
-----END PGP SIGNATURE-----

--M9NhX3UHpAaciwkO--