Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

hash_set : need the location /index where stored .

Posted on 2004-04-26
5
Medium Priority
?
538 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 1200 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: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering 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

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

705 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