HashTable

[carl]

I have found various hash_table implementation in c++ on the net. But I have
not found any that returns the chain of objects associated with a hased
index.

When more that one object hash to the same index it gets added to a chain of
elements. Are there any implmentations that returns the whole chain based on
a hashed index?

Its pretty much the functionality of a std::map that for each key contains a
list (or std::vector) of the stored objects. But I would like the constant
time lookup of the hash-table instead of the lg n time of a map.

 

[Chris M. Thomasson]

I have found various hash_table implementation in c++ on the net. But I
have not found any that returns the chain of objects associated with a
hased index.

When more that one object hash to the same index it gets added to a chain
of elements.
Sometimes.




Are there any implmentations that returns the whole chain based on a
hashed index?

Perhaps. It would be trivial to create one yourself. Just create a static
hash table with a container per-bucket. Add a lookup function which returns
a reference to the hashed container.

 

[Pavel]

I have found various hash_table implementation in c++ on the net. But I
have not found any that returns the chain of objects associated with a
hased index.

When more that one object hash to the same index it gets added to a
chain of elements. Are there any implmentations that returns the whole
chain based on a hashed index?

Its pretty much the functionality of a std::map that for each key
contains a list (or std::vector) of the stored objects. But I would like
the constant time lookup of the hash-table instead of the lg n time of a
map.

The functionality in std::map is actually slightly different and it *is*
available in hash maps:

You can iterate a sequence of objects with keys "Equal" or more
precisely, equivalent, to your given key using equal_range() methods of
both std::[multi]map and unordered_[multi]map (available in many current
C++ implementations in std::tr1 namespace or you can use
boost::unordered_map that provides the identical functionality).
(unordered_map is a hash table).

Additionaly to equal_range(), the following hash table-specific
functionality is available in unordered_map: you can retrieve a bucket
with bucket(key) call and iterate through the bucket but, if my reading
of C++0x specs is correct, you may encounter more than one hashcode in
the bucket (although it is guaranteed that you you will receive all
objects with the hash value equal to the one of your key in one bucket
and that the *average* length of the bucket is not greater than a
reasonably low constant).

If neither of the above alternatives is right for you, you may have to
implement your own hash table (or use the existing one and somehow
support the list or vector of elements with the equal hash codes on your
own). I am not aware of an implementation that does exactly what you
described (this certainly does not mean it is not available).

Hope this will help
-Pavel

 

[Stefan Ram]

When more that one object hash to the same index it gets added to a chain of
elements. Are there any implmentations that returns the whole chain based on
a hashed index?

Welcome to the world of "object-oriented programming" (or,
should I say just: "good practices of software engineering"?
or "abstract data types"?), here: "encapsulation" and
"information hiding"!

A "map" is defined as an object with an interface that
specifically does /not/ reveal this information. (For example,
so that it might change. In fact, a hash map might rehash its
entries sometimes so that also this chain will change.)