Solved

hash_set : need the location /index where stored .

Posted on 2004-04-26
5
535 Views
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 :)

/abhijit/





0
Comment
Question by:avizit
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 30

Expert Comment

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

There's no real question in your post.

Specifically what is your question?
0
 
LVL 22

Accepted Solution

by:
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.

0
 
LVL 22

Expert Comment

by:NovaDenizen
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.
0
 
LVL 11

Author Comment

by:avizit
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 )

/abhijit/

0
 
LVL 11

Author Comment

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

/abhijit/
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

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

Suggested Solutions

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
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.

734 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