This directory contains several hash-map implementations, similar inAPI to SGI's hash_map class, but with different performancecharacteristics.  sparse_hash_map uses very little space overhead, 1-2bits per entry.  dense_hash_map is very fast, particulary on lookup.(sparse_hash_set and dense_hash_set are the set versions of theseroutines.)  On the other hand, these classes have requirements thatmay not make them appropriate for all applications.All these implementation use a hashtable with internal quadraticprobing.  This method is space-efficient -- there is no pointeroverhead -- and time-efficient for good hash functions.COMPILING---------To compile test applications with these classes, run ./configurefollowed by make.  To install these header files on your system, run'make install'.  (On Windows, the instructions are different; seeREADME_windows.txt.)  See INSTALL for more details.This code should work on any modern C++ system.  It has been tested onLinux (Ubuntu, Fedora, RedHat, Debian), Solaris 10 x86, FreeBSD 6.0,OS X 10.3 and 10.4, and Windows under both VC++7 and VC++8.USING-----See the html files in the doc directory for small example programsthat use these classes.  It's enough to just include the header file:   #include <sparsehash/sparse_hash_map> // or sparse_hash_set, dense_hash_map, ...   google::sparse_hash_set<int, int> number_mapper;and use the class the way you would other hash-map implementations.(Though see "API" below for caveats.)By default (you can change it via a flag to ./configure), these hashimplementations are defined in the google namespace.API---The API for sparse_hash_map, dense_hash_map, sparse_hash_set, anddense_hash_set, are a superset of the API of SGI's hash_map class.See doc/sparse_hash_map.html, et al., for more information about theAPI.The usage of these classes differ from SGI's hash_map, and otherhashtable implementations, in the following major ways:1) dense_hash_map requires you to set aside one key value as the   'empty bucket' value, set via the set_empty_key() method.  This   *MUST* be called before you can use the dense_hash_map.  It is   illegal to insert any elements into a dense_hash_map whose key is   equal to the empty-key.2) For both dense_hash_map and sparse_hash_map, if you wish to delete   elements from the hashtable, you must set aside a key value as the   'deleted bucket' value, set via the set_deleted_key() method.  If   your hash-map is insert-only, there is no need to call this   method.  If you call set_deleted_key(), it is illegal to insert any   elements into a dense_hash_map or sparse_hash_map whose key is   equal to the deleted-key.3) These hash-map implementation support I/O.  See below.There are also some smaller differences:1) The constructor takes an optional argument that specifies the   number of elements you expect to insert into the hashtable.  This   differs from SGI's hash_map implementation, which takes an optional   number of buckets.2) erase() does not immediately reclaim memory.  As a consequence,   erase() does not invalidate any iterators, making loops like this   correct:      for (it = ht.begin(); it != ht.end(); ++it)        if (...) ht.erase(it);   As another consequence, a series of erase() calls can leave your   hashtable using more memory than it needs to.  The hashtable will   automatically compact at the next call to insert(), but to   manually compact a hashtable, you can call      ht.resize(0)I/O---In addition to the normal hash-map operations, sparse_hash_map canread and write hashtables to disk.  (dense_hash_map also has the API,but it has not yet been implemented, and writes will always fail.)In the simplest case, writing a hashtable is as easy as calling twomethods on the hashtable:   ht.write_metadata(fp);   ht.write_nopointer_data(fp);Reading in this data is equally simple:   google::sparse_hash_map<...> ht;   ht.read_metadata(fp);   ht.read_nopointer_data(fp);The above is sufficient if the key and value do not contain anypointers: they are basic C types or agglomorations of basic C types.If the key and/or value do contain pointers, you can still store thehashtable by replacing write_nopointer_data() with a custom writingroutine.  See sparse_hash_map.html et al. for more information.SPARSETABLE-----------In addition to the hash-map and hash-set classes, this package alsoprovides sparsetable.h, an array implementation that uses spaceproportional to the number of elements in the array, rather than themaximum element index.  It uses very little space overhead: 2 to 5bits per entry.  See doc/sparsetable.html for the API.RESOURCE USAGE--------------* sparse_hash_map has memory overhead of about 4 to 10 bits per   hash-map entry, assuming a typical average occupancy of 50%.* dense_hash_map has a factor of 2-3 memory overhead: if your  hashtable data takes X bytes, dense_hash_map will use 3X-4X memory  total.Hashtables tend to double in size when resizing, creating anadditional 50% space overhead.  dense_hash_map does in fact have asignificant "high water mark" memory use requirement, which is 6 timesthe size of hash entries in the table when resizing (when reaching 50% occupancy, the table resizes to double the previous size, and the old table (2x) is copied to the new table (4x)).sparse_hash_map, however, is written to need very little spaceoverhead when resizing: only a few bits per hashtable entry.PERFORMANCE-----------You can compile and run the included file time_hash_map.cc to examinethe performance of sparse_hash_map, dense_hash_map, and your nativehash_map implementation on your system.  One test against theSGI hash_map implementation gave the following timing information fora simple find() call:   SGI hash_map:     22 ns   dense_hash_map:   13 ns   sparse_hash_map: 117 ns   SGI map:         113 nsSee doc/performance.html for more detailed charts on resource usageand performance data.---16 March 2005(Last updated: 12 September 2010)