Hashtables

[Complete]

I have heard a lot of talk about hashtables from time to time. They are supposed to be very cool ways of storing data where the index you use to look up the data is somehow the data itself.

But hashtables are not part of the C++ standard template library... I think. So does anyone have any tips on how to write a hashtable?

[laserlight]

But hashtables are not part of the C++ standard template library... I think.
True, but if you are using a new compiler that comes with a TR1 implementation (e.g., g++ 4.1+ or MSVC9), or otherwise can use a TR1 implementation (e.g., from Dinkumware), then you can use std::tr1::unordered_set, std::tr1::unordered_map, std::tr1::unordered_multiset, and std::tr1::unordered_multimap. If you do not have access to a TR1 implementation, then you can give the libraries from Boost (http://www.boost.org) a try.

So does anyone have any tips on how to write a hashtable?
First, try searching the Web on "hash table".

[Peter_APIIT]

I agree laserlight's opinion but if this is for learning purpose then i will write my own but for production purposes then i will use those library.

[Complete]

Well I did some looking around and a textbook I found had this to say about hashtables. The SGI STL (free available at Standard Template Library Programmer's Guide --
http://www.sgi.com/Technology/STL )

is one of the most robust implementations of the STL, and can be
used to replace your compiler's STL if that is found wanting. In
addition they've added a menber of extensions including hash_set,
hash_multiset, hash_map, hash_multimap, slist (a singly-linked lest)
and rope (a variant of string optimized for verylarge strings and
fast concatenation and substring operations).

The hasp_map header is not part of the standard C++ STL. It is an
extension that is only available as part of the SGI STL.

I downloaded these header files and I copied them into the directory:
C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\include>

I wrote a little test program (more about this later) and I tried to compile.
I got a C2061 error because when I copied the SGL STL header files
I should have merged the code instead.

1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\stdlib.h(360) : error C2061: syntax error : identifier '_CountofType'

So, where is '_CountofType' defined?

I need some help.

Can someone tell me where I can get the original header files?

Here is the list of SGI STL header files:


algo.h
algobase.h
algorithm
alloc.h
bitset
bvector.h
char_traits.h
concept_checks.h
container_concepts.h
defalloc.h
deque
deque.h
function.h
functional
hashtable.h
hash_map
hash_map.h
hash_set
hash_set.h
heap.h
iterator
iterator.h
limits
list
list.h
map
map.h
memory
multimap.h
multiset.h
numeric
pair.h
pthread_alloc
pthread_alloc.h
queue
rope
rope.h
ropeimpl.h
sequence_concepts.h
set
set.h
slist
slist.h
stack
stack.h
stdexcept
stl_algo.h
stl_algobase.h
stl_alloc.h
stl_bvector.h
stl_config.h
stl_construct.h
stl_ctraits_fns.h
stl_deque.h
stl_exception.h
stl_function.h
stl_hashtable.h
stl_hash_fun.h
stl_hash_map.h
stl_hash_set.h
stl_heap.h
stl_iterator.h
stl_iterator_base.h
stl_list.h
stl_map.h
stl_multimap.h
stl_multiset.h
stl_numeric.h
stl_pair.h
stl_queue.h
stl_range_errors.h
stl_raw_storage_iter.h
stl_relops.h
stl_rope.h
stl_set.h
stl_slist.h
stl_stack.h
stl_string_fwd.h
stl_tempbuf.h
stl_threads.h
stl_tree.h
stl_uninitialized.h
stl_vector.h
string
tempbuf.h
tree.h
type_traits.h
utility
valarray
vector
vector.h


Are you saying that with my version of VC++, I did not have to download anything to begin with?

[ltcmelo]

Hi.

Visual studio, like most C++ compilers, already comes with an implementation of the STL. Therefore, it won't just work if you copy those header files to the include directory. You have to do some configurations so you'll be able to use an alternative version of the STL. You need to look for some documentation on how to achieve that.

You can find an independent implementation of the STL at STLport website (http://www.stlport.org/). This is "kind" of a more up to date version of the original SGI implementation.

Regarding hash tables specifically, the others have already given suggestions. Still, you can find a standalone implementation with STL like interface here (http://www.codeproject.com/KB/cpp/stllikeopenhash.aspx).

[Lindley]

The basic idea of a hash table is very simple: Define a hash function which, given an object, will come up with some wildly unpredictable number. The number can be anywhere in the range of valid ints, signed or unsigned; doesn't matter. The only important thing is that exactly the same object will always produce exactly the same number, and the probability of two different objects producing the same number should be low.

For example, in a binary image (one in which only black and white pixels exist), you might define a hash function that treats each pixel as a 1 or 0 in an enormous, width*height-digit binary number. Odds are this number will be larger than MAX_INT, but we don't really care if it wraps around, so that's okay.

Once you've got a hash function, just use it to generate a hash value, then modulus the value with the size of your hash table to get an index. Then just place the object at the index. If multiple objects end up at the same index we can handle that by hanging a linked list off that index; but this should be unlikely.

[GCDEF]

I don't think it's based on a hash table, but an STL map serves the same purpose.

[Lindley]

std::map is slightly slower (by a logarithmic factor), and requires a weak ordering. On the plus side it gives you sorting for free.

[souldog]

also, if you want to use STLport you need to follow the instructions for compiling and installing it. Read the documentation provided.

[ltcmelo]

I don't think it's based on a hash table, but an STL map serves the same purpose.

You're right, they're not based on hash tables, but on trees. Usually, the implementations of std::map are actually red-black trees (http://en.wikipedia.org/wiki/Red-black_tree).

Regarding the purpose of them, there're a couple of differences. As Lindley has already said, most of them come from the fact that trees provide you an ordering mechanism while hash tables don't. On the other hand, good implementations of hash tables provide you amortized constant time for accessing elements (assuming an efficient key and a balanced table).