hash_set : need the location /index where stored .

Posted on 2004-04-26
Last Modified: 2008-03-17
I am using hash_set which is available from gcc ( and which i presume is not part of the C++ standard yet )

okay , In hash tables the key is used by a hash function to calculate a  index and the object is stored under that key.
I would like to have the index value. I want to iterate over all the objects stored in the hash_set and get all the objects and their index. )  
The aim is to display the hash_set  graphically, so that we can visually see how the objects are stored and are they distributed evenly or there is high collision and we arent getting much benifit out of using hash_set as compared to using a list.

Also for classes created by us , we have to define our own hash functions and in that case we can calculate it from the object itself. BUt what if we just have a pointer to the hash_set object and have no idea what the hash function is ?

second problem is when we define a hash_set
hash_set(size_type n)              Creates an empty hash_set with at least n buckets.

this creates a hash_set with _at least_ n buckets . Is there any way we can make sure that exactly n buckets are created. cos if our custom hash function returns a value from 0 to n-1 i dont see any use of creating a hash_set with more than n buckets.

Phew I hope i was clear enough :)


Question by:avizit
  • 2
  • 2
LVL 30

Expert Comment

ID: 10922928
>>Phew I hope i was clear enough :)

There's no real question in your post.

Specifically what is your question?
LVL 22

Accepted Solution

NovaDenizen earned 300 total points
ID: 10922937
The GNU hash_set class, defined in stl_hash_set.h, has a hashtable member variable called _M_ht.  The hash_set basically treats its hashtable as a black box, so to get the information you want you have to dive down into _M_ht and class hashtable.
The GNU hashtable class has a member variable called _M_buckets, of type vector<_Node *, _Alloc> where _Node and _Alloc are template classes derived from the template information. You would have to examine your_hash_set._M_ht._M_buckets to see the view of the table you want.
However, all of the member variables are private, and you don't have access to them.  You would have to somehow worm your way into their private members.  The easiest way to do this would probably be to edit the header files (stl_hash_set.h and stl_hashtable.h) so that the hash_set and hashtable classes declared your nosy class as a friend class.  

This would be horrifically unportable, and a bad idea to use it for anything important, but it ought to work.  Replace your header files after you have done whatever it is you are doing.  Don't use the modified header files for any serious work.

LVL 22

Expert Comment

ID: 10923012
second question:  the hashtable implementation uses a static array of integers called __stl_prime_list to define the hashtable sizes.  It starts {53, 97, 193} and keeps going, roughly doubling each time until it gets to 4294967291.  hashtable uses numbers from this list to define its sizes and size increments.  I don't think that the hashtable will size itself to something other than one of the prime values in this table.

Also, this hashtable expects hash functions to return a value from 0 to (2^32)-1, and the hashtable performs a % n to map the 32-bit value to the hashtable size.  So your hash function should return a good 32-bit value.  The hashtable will not tell you when it needs to grow.  Your hash function should always return the same value for the same node, and shouldn't return a hash value based on the table size.

Another thing:  The gnu hashtable is implemented as a vector of linked lists.  Each cell in the hash table is a linked list of elements that hashed to that cell.  I don't think this implementation does gravestoning or incrementing to handle collisions, so maybe you need to rethink how you will represent the state of the hash table.
LVL 11

Author Comment

ID: 10924712
Thanks NovaDenizen ,

I guess I will have to live with it.  I am not proficient enough to go and try to mess with the header files.

The reason I wanted get those indexes was to see if the custom hash function supplied was good enough for the kind of data I am storing and should I make my own hash function. And presenting the hash table graphically would have given me a good indication of that.

Anyway thanks for your reply ( i have increased the points to 300 )


LVL 11

Author Comment

ID: 10924719
I shall also be posting at the c++ newsgroup to see what they have go to say.


Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
ADO Memory leak with DELPHI 2007 37 171 build a IF/Then Walkthrough Guide 1 192
IdTCPClient1->Disconnect(); not working 3 62
computer science syllabus 3 70
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

863 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

25 Experts available now in Live!

Get 1:1 Help Now