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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

685 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