Topic: Hash table for C++ STL


Author: fraley@hpl.hp.com (Bob Fraley)
Date: Sat, 18 Feb 1995 02:32:58 GMT
Raw View
An implementation of hash table conforming to STL design is available
through anonymous ftp from butler.hpl.hp.com (192.6.19.31 or
butler.hpl.external.hp.com if butler.hpl.hp.com does not work) in file
/stl/bfhash.Z (and /stl/bfhash.zip for PC users).

Should you have any problem about this implementation, please send mail
to fraley@hpl.hp.com.

Enclosed in the distribution is the proposal which has been sent to
the C++ library standards committee.  This is a joint proposal with
Dave Musser and Javier Barreirro of Rensselaer Polytechnic Institute.

Let me clarify that the proposal makes absolutely no change to the
current STL library.  The first part of the proposal divides the
current table of requirements for associative containers into 2 parts.
This allows the hash table requirements to be derived from a common
base as the ordered associative container requirements.  But no change
for associative containers has been made, so all existing
implementations will remain valid.

Initial performance results show that the hash_set<string> is 5 times
faster than set<string> for a set of 10,000 strings, and
hash_set<unsigned> is 2 times faster than set<unsigned> for 12,000
random integers.  Some additional information on performance is
included in the implementation document included with the package.

Bob Fraley
Hewlett-Packard Laboratories

fraley@hpl.hp.com