RE: [Algorithms] Hashing arbitary data/pointers

[Andrew V. <av...@in...>]

Alternatively, you can write a templated hash-table using a traits class.
Off the top of my head something like this:

struct SampleTraits
{
	typedef <arbitrary_type>	Type;

	static bool Equals( const Type &a, const Type &b );
	static int  Hash( const Type &a );
}

template < Traits >
class HashTable
{
public:
	typedef Traits::Type	Type;

	void Insert( const Type &item )
	{
		int hash( Traits::Hash( item ) % mNumBins );
		mBins[ hash ].Insert( item );
	}
}

Or similar (obviously implementations could well vary).

This avoids using virtual function calls but will obviously generate more
code if you use it for lots of different types - might not matter for you
though.

It's also type safe if you do it properly - Note that the version above
*isn't* (it won't work if "Type" is a reference type) and if you want to
write one in this manner, I'd strongly recommend looking at the Loki library
(google for it) but probably only the TypeTraits stuff as that's all you
really need - not sure about the rest of it in general :).

Andrew.

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...] On
> Behalf Of Jon Watte
> Sent: 20 August 2004 17:31
> To: gda...@li...
> Subject: RE: [Algorithms] Hashing arbitary data/pointers
>
>
> The problem with using a void* as key is that two
> values that may compare equal, may get different hashes,
> depending on how they were created.
>
> If you have a variant type in C++ then you can write
> your comparision and hashing functions using either a
> switch() on a "type" member of the variant, or make the
> "type" member be a pointer to a IType interface, which
> implements appropriate hashing/comparision for the data
> item in question.
>
> class Variant;
>
> class IType {
>   public:
>     virtual char const * name() = 0;
>     virtual int compare( Variant const * a, Variant const * b ) = 0;
>     virtual unsigned int hash( Variant const * ptr ) = 0;
>     ... copy, create, destroy, etc ...
> };
>
> class CString : public IType {
>   public:
>     char const * name() { return "string"; }
>     int compare( Variant const * a, Variant const * b ) {
>       assert( a->type_ == b->type_ );
>       return strcmp( (char *)a->indirect, (char *)b->indirect );
>     }
>     unsigned int hash( Variant const * ptr ) {
>       return string_hash_function( (char *)ptr->indirect );
>     }
> };
>
> IType * gStringType = new CString();
>
> class Variant {
>   public:
>     IType * type_;
>     union {
>       void * indirect;
>       double numeric;
>       int integer;
>     };
>     bool operator<( Variant const & o ) {
>       if( type_ < o.type_ ) return true;
>       if( type_ > o.type_ ) return false;
>       return type_->compare( this, &o ) < 0;
>     }
>     unsigned int hash() {
>       return type_->hash( this );
>     }
> };
>
> It's been my experience that when you end up doing
> variants in C++, you really want to be using a scripting
> language with good hash table support (like Lua, Python
> or Perl) rather than C++. Unless you're in the interface
> between the scripting language and C++, but then you
> usually don't need to put the data into a C++ hash
> table.
>
> Cheers,
>
> 			/ h+
>
>
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of
> cruise
> Sent: Friday, August 20, 2004 8:10 AM
> To: gda...@li...
> Subject: [Algorithms] Hashing arbitary data/pointers
>
>
> I have a collection of key/value pairs, and naturally it
> makes sense to have
> some kind of hash (or other kind of quick lookup) on they key
> - but the key
> can
> be any kind of data - string, int, float, pointer to a class, etc.
> This lookup will be used /a lot/ so the faster the better. My
> first thought
> is
> store the data as a void*, and do some kind of octree or hash
> on the pointer
> value. Does this sound tractable, or am I attempting
> something completely
> stupid
> with this?
>
> --
> [ cruise / casual-tempest.net / transference.org ]
>    "quantam sufficit"
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by Shop4tech.com-Lowest price on Blank Media
> 100pk Sonic DVD-R 4x for only $29 -100pk Sonic DVD+R for only $33
> Save 50% off Retail on Ink & Toner - Free Shipping and Free Gift.
> http://www.shop4tech.com/z/Inkjet_Cartridges/9_108_r285
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by Shop4tech.com-Lowest price on Blank Media
> 100pk Sonic DVD-R 4x for only $29 -100pk Sonic DVD+R for only $33
> Save 50% off Retail on Ink & Toner - Free Shipping and Free Gift.
> http://www.shop4tech.com/z/Inkjet_Cartridges/9_108_r285
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>
>