Re: hash two keys to one index
Mark wrote On 11/21/06 16:57,:
Mark wrote:
I've run into a bit of a snag.
When I insert an object into the hash table, I pass in (a reference to)
the object, and a hash code, which can either be based on the last name
or the student number. To deal with collisions, I use a quadratic
probing technique...
If you're trying to learn how to implement a hash table,
fine: go ahead and fiddle around to your curiosity's limits.
But if you're just trying to use a hash table in the solution
of some other problem, I recommend java.util.HashMap to your
attention. The wheel has already been invented, and is not
too badly out of round ...
void insert(Object obj, int hash) throws HashTableFull
{
if( count == table.length ) throw new HashTableFull("Cannot insert:
hash table is full");
int key = probe(hash);
table[key] = obj;
++count;
}
int sign(int i)
{
if( i < 0 ) return -1;
return 1;
}
int probe(int hash)
{
int probe = 0;
while(true)
{
int key = (hash + probe*probe*sign(probe)) % table.length;
if( table[key] == null )
return key;
if( probe <= 0 )
probe = -probe+1;
else
probe = -probe;
}
}
Which, in theory, should work nicely.
I haven't studied it closely, but at a quick glance it
doesn't look noticeably better than linear probing. Every
hash value that starts by probing a particular bucket [k]
then follows the same path: [k+1], [k-1], [k+4], [k-4], ...
Also, I haven't convinced myself that this probe sequence
will eventually visit every table location instead of just
cycling back on itself.
Also, the % operator doesn't do quite what you want.
For example, -7 % 4 yields -3, not 1.
However... when retrieving the
object, how do I know when I've found the right one?
[...]
Rereading what you wrote, you indicate that a reference to the key
should also be stored. I didn't really understand why a reference to
the key should be stored, if the key could easily be derived from
hashing the object. However... I suppose it could be useful when
trying to find an object...
The "key" is the actual Student name or number, not the
hash code derived from it nor the location of some bucket in
the table. You hash the key, do some numerical hocus-pocus,
and derive a bucket number. In that bucket, if it's not empty,
you find a (key,value) pair. You compare the bucket's key to
the search key to find out whether this is the desired pair or
whether you need to probe further.
Note: Since you stop searching as soon as you've found a
bucket whose key equals the search key, it follows that the
keys (not necessarily their hash codes) must be unique. If
you've got two different Students both named "John Smith"
there'll be trouble. You could, if you wanted, have a Map
that associated a name with a collection of all the Students
sharing that same name; many collections would contain just
one Student apiece, but some might contain several.
Recommended reading: D.E. Knuth, "The Art of Computer
Programming, Volume III: Sorting and Searching." Some people
are intimidated by Knuth's rigor (I confess that some sections
are beyond my own mathematical skills), but he always ends the
deeper derivations with a straightforward statement of the
conclusions -- very helpful for those of us unlikely to win
a Fields Medal any time soon.
--
Eric.Sosman@sun.com