This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/6966] New: hsearch almost always probes the same index when using the secondary hash
- From: "bugzilla at bsb dot me dot uk" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 19 Oct 2008 01:29:34 -0000
- Subject: [Bug libc/6966] New: hsearch almost always probes the same index when using the secondary hash
- Reply-to: sourceware-bugzilla at sourceware dot org
hsearch references Kunth vol. 3 6.4 on "open addressing" but the code does
implement the algorithm from Knuth. Instead of generating the second hash from
the first, the code generates the second hash from the first index. Because
this hash is then used to step the index, the result is that the first index
generated is (almost) always the same.
This partly defeats the purpose of using a secondary hash.
I say "almost" because it happens for all but 2 of the possible index values in
any given table. For example, in a table of size 11, all secondary probes will
start at index 10 unless the inital hash produced 9 or 10.
This was reported on news:comp.lang.c by James Dow Allen and I decided to check
on it. I have a simple patch but I am not sure of the procedure for posting
patches to glibc.
--
Summary: hsearch almost always probes the same index when using
the secondary hash
Product: glibc
Version: 2.8
Status: NEW
Severity: minor
Priority: P3
Component: libc
AssignedTo: drepper at redhat dot com
ReportedBy: bugzilla at bsb dot me dot uk
CC: glibc-bugs at sources dot redhat dot com
http://sourceware.org/bugzilla/show_bug.cgi?id=6966
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.