hello, i'm very new to hash tables, but here is what i need: i want to store the an integer into a table and want to index it with two other integers. how would a hash function look like that retrieves this integer based on two others? (i need this to store the index of a new vertex that lies between two other vertices. and to not create this new vertex again from another face i want to look it up in a hashtable if it already exists)

Quote:Original post by Andrew Russell
That is MSVC-code, you may have to convert it to your own version of the STL (the traits, mostly). It will also Warning-4996 unless you disable that warning or resolve it (I believe by changing std to std_ext).

As of VC++ 7.1 > * hash_map under name space std has been deprecated, on VC++ 7.1 > * all library extensions are in name space stdext (of course doesn't reflect all compilers or the standard), you should use that version because i think std version is older and not been maintained.

For GCC * < GCC 4.* its in header ext/hash_map in namespace __gnu_cxx and reflects SGI's interface which has a slightly different template type parameter list & types than VC++'s hash_map.

For GCC 4.* > * should be in namespace std::tr1 under the name of unordered_map this of course reflects the standard library technical report (TR1) which appears to follow SGI's interface.

Quote:Original post by Andrew Russell
Is this what you're after?

*** Source Snippet Removed ***

That is MSVC-code, you may have to convert it to your own version of the STL (the traits, mostly). It will also Warning-4996 unless you disable that warning or resolve it (I believe by changing std to std_ext).

It's coded off the top of my head as an example, so you may want to fix it a little. Also, see the documentation for hash_map for more detials.

From my (admittedly very limited) experience with msVC hash (multi)map, for custom objects with their own hash_compare() in order to have it fully work the object also needs its custom 'operator <' which works by comparing hash values for two involved objects ... otherwise --with different comparison method-- all sorts of funny things might happen. >.<;

Also, this particular table could probably be done with simple

hash_map<int, int> vertex_map;

and then the key for insertion/lookup could be generated with explicit call to separate hash function?

int hash( const vertex& Vertex1, const vertex& Vertex2 ) {    return ((Vertex1.x + Vertex2.x) * 5) - ((Vertex1.y + Vertex2.y) * 3); // or whatever}

given the original poster wants a sort based on being between certain two vertices rather than related to just one ^^;;

Quote:Original post by snk_kid

Quote:Original post by tolaris
From my (admittedly very limited) experience with msVC hash (multi)map, for custom objects with their own hash_compare() in order to have it fully work the object also needs its custom 'operator <' which works by comparing hash values for two involved objects

Not quite thats just the default, VC++ hash_map's third template type parameter is the hash traits type which defaults to using stdext::hash_compare which is also a template class for which it's second template type parameter takes a Comparator type that defaults to using std::less, std::less assumes the type has relational less than operator supported.

That does not mean you must overload the relational less than operator, its just the default, you can either use a custom comparator type for hash_compare or if you write your own hash traits type it must support 2 function calls (achieved by overloading the function call operator), one for hashing and another for comparison of keys which Andrew already did in his example.

Quote:Original post by Couvillion
Since hash_map isn't standard STL, you you may want to build your hash-table out of std::maps:

I just can't see the logic in this (other than the fact that hash_map isn't in the standard but is currently being reviewed under the name unordered_map).

Considering that std::map is an ordered associative container where significant operations are logarithmic in time complexity.

Where as hash_map/std::tr1::unordered_map is an unordered associative container where signficant operations are amortized constant in time complexity.

Quote:Original post by snk_kid
Not quite thats just the default, VC++ hash_map's third template type parameter is the hash traits type which defaults to using stdext::hash_compare which is also a template class for which it's second template type parameter takes a Comparator type that defaults to using std::less, std::less assumes the type has relational less than operator supported.

That does not mean you must overload the relational less than operator, its just the default, if you write your own hash traits type it must support 2 function calls (achieved by overloading the function call operator), one for hashing and another for comparison of keys which Andrew already did in his example.

I wasn't very clear in my reply, am sorry ^^;

I can see the provided example has its own comparison function. What i meant was, what i found out while playing with the hash map, apparently if the comparison function you use for the objects *might* order the objects in manner different than comparison of object's hash values would, it can sometimes lead to some nasty problems with the hash map. Specifically, call to equal_range( foo ) would occasionally (but in consistent manner, always for the same objects in a map) return _empty set_ even though at least one object with key foo _was_ most definitely placed in the map. Changing the original comparison function to something to effect of 'Left.hash() < Right.hash' removed this behaviour.

Quote:Original post by tolaris
I wasn't very clear in my reply, am sorry ^^;

no worries [wink]

Quote:Original post by tolaris
I can see the provided example has its own comparison function. What i meant was, what i found out while playing with the hash map, apparently if the comparison function you use for the objects *might* order the objects in manner different than comparison of object's hash values would, it can sometimes lead to some nasty problems with the hash map. Specifically, call to equal_range( foo ) would occasionally (but in consistent manner, always for the same objects in a map) return _empty set_ even though at least one object with key foo _was_ most definitely placed in the map. Changing the original comparison function to something to effect of 'Left.hash() < Right.hash' removed this behaviour.

VC++ version of hash_map seems to be an odd ball to say the least, from what i understand from the docs it says the comparator must impose strict weak ordering of elements (typical stuff for an ordered container but hash_map shouldn't need to be ordered) but then goes on to say comparison of equality is valid too:

Quote:from MSDN DOCs
.... In general, the elements need be merely less than comparable to establish this order: so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements. On a more technical note, the comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y and a return value of true or false. An ordering imposed on a hash_map is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y) and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, then the ordering becomes total (in the sense that all the elements are ordered with respect to each other) and the keys matched will be indiscernible from each other.

The actual order of elements in the controlled sequence depends on the hash function, the ordering function, and the current size of the hash table stored in the container object. You cannot determine the current size of the hash table, so you cannot in general predict the order of elements in the controlled sequence. Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that had specifically pointed at the removed elements.....

Hopefully all should go as planned and std::tr1::unordered_map will be accepted and becomes part of the C++ standard, then VC++ will have no choice but to implement that version instead.

ok thank you first of all!

as i said, i'm new to hashtables, so i'm not sure if i can follow you all.

if possible, i would like to avoid the stl in this case. here is what i have so far:




then for every new vertex i create. i store it in a hashtable like this:

hashtable[h].keyA = neighbourA;
hashtable[h].keyB = neighbourB;
hashtable[h].value = index;
h++;

now instead of the above hashfunction looping through all the entries, i would need one that finds value faster.


also, please tell me if what i did so far is completely wrong. ;-)))

thanks!

[/source]