On Wednesday, 24 October 2012 at 20:32:00 UTC, Walter Bright wrote:
> The default compare for structs is a bit compare of the contents.


Thanks for the reply.


And hmm, that should be changed IMO. ;)
Bitwise comparison is nearly useless.

On Wed, Oct 24, 2012 at 10:16:27PM +0200, Mehrdad wrote: [...]
> struct Set(T)
> {
> 	int[T] dict;
> 	hash_t toHash() const
> 	{
> 		typeof(return) r = 0;
> 		foreach (item; this.dict.keys)
> 		{
> 			???       // what should be here?
> 		}
> 		return r;
> 	}
> }

Try this:

	hash_t toHash() const
	{
		hash_t h = 0;
		foreach (item; this.dict.keys)
		{
			// We use a commutative operation here (+) so
			// that the order of keys don't matter.
			h += hashOf(&item, item.sizeof);
		}
		return h;
	}


T

-- 
What do you get if you drop a piano down a mineshaft? A flat minor.

On Wednesday, 24 October 2012 at 20:37:08 UTC, H. S. Teoh wrote:
> On Wed, Oct 24, 2012 at 10:16:27PM +0200, Mehrdad wrote:
> [...]
>> struct Set(T)
>> {
>> 	int[T] dict;
>> 	hash_t toHash() const
>> 	{
>> 		typeof(return) r = 0;
>> 		foreach (item; this.dict.keys)
>> 		{
>> 			???       // what should be here?
>> 		}
>> 		return r;
>> 	}
>> }
>
> Try this:
>
> 	hash_t toHash() const
> 	{
> 		hash_t h = 0;
> 		foreach (item; this.dict.keys)
> 		{
> 			// We use a commutative operation here (+) so
> 			// that the order of keys don't matter.
> 			h += hashOf(&item, item.sizeof);
> 		}
> 		return h;
> 	}
>
>
> T

Wouldn't that do a bitwise comparison?

On Wednesday, 24 October 2012 at 20:38:08 UTC, Mehrdad wrote:
> Wouldn't that do a bitwise comparison?

sorry, I mean bitwise _hash_

Is there any reason why we don't have something like this in Phobos?



hash_t toHash(T)(in T t) if (isIntegral!(T) || isSomeChar!(T))
{
	return t;
}

hash_t toHash(T)(in T[] t)
{
	typeof(return) h = 0;
	foreach (item; t)
	{ h = h * 37 + item.toHash(); }
	return h;
}

hash_t toHash(T)(in T t) if (!isIntegral!(T) && !isSomeChar!(T) && !isArray!(T))
{
	typeof(return) h = 0;
	foreach (ref a; t.tupleof)
	{ h = h * 37 + a.toHash(); }
	return h;
}

hash_t toHash(T...)(in Tuple!(T) t)
{
	typeof(return) h = 0;
	foreach (item; t)
	{ h = h * 37 + item.toHash(); }
	return h;
}

On Wed, Oct 24, 2012 at 10:38:07PM +0200, Mehrdad wrote:
> On Wednesday, 24 October 2012 at 20:37:08 UTC, H. S. Teoh wrote:
> >On Wed, Oct 24, 2012 at 10:16:27PM +0200, Mehrdad wrote: [...]
> >>struct Set(T)
> >>{
> >>	int[T] dict;
> >>	hash_t toHash() const
> >>	{
> >>		typeof(return) r = 0;
> >>		foreach (item; this.dict.keys)
> >>		{
> >>			???       // what should be here?
> >>		}
> >>		return r;
> >>	}
> >>}
> >
> >Try this:
> >
> >	hash_t toHash() const
> >	{
> >		hash_t h = 0;
> >		foreach (item; this.dict.keys)
> >		{
> >			// We use a commutative operation here (+) so
> >			// that the order of keys don't matter.
> >			h += hashOf(&item, item.sizeof);
> >		}
> >		return h;
> >	}
> >
> >
> >T
> 
> Wouldn't that do a bitwise comparison?

Umm, the idea of a hash is to *quickly* compute a value that's (mostly) unique for a given object. In most cases, the bit representation is good enough. If you want a thorough recursive comparison of all subobjects, you should overload opEquals and use that instead.

Or use compile-time reflection to iterate over every member of the given object and recursively iterate and hash them. Though I fail to see the point of it, since it defeats the purpose of a hash in the first place - you might as well just do the usual recursive compare instead.


T

-- 
Never step over a puddle, always step around it. Chances are that whatever made it is still dripping.

On Wednesday, 24 October 2012 at 20:47:30 UTC, H. S. Teoh wrote:
> Umm, the idea of a hash is to *quickly* compute a value that's (mostly) unique for a given object. In most cases, the bit representation is good enough.

I don't understand what you're saying.

hash(tuple("foo".dup))  MUST be equal to  hash(tuple("foo".dup")).

Bitwise hashing makes no sense whatsoever.

Better example:



private import std.traits, std.typecons, std.typetuple;

hash_t toHash(T)(in T t)
	if (isIntegral!(T) || isSomeChar!(T))
{ return t; }

hash_t toHash(T)(in T[] t)
{
	typeof(return) h = 0;
	foreach (item; t)
	{ h = (h * 37) ^ item.toHash(); }
	return h;
}

hash_t toHash(V, K)(in V[K] t)
{
	typeof(return) h = 0;
	foreach (k, v; t)
	{ h ^= k.toHash(); }
	return h;
}

hash_t toHash(T)(in T t)
	if (!isIntegral!(T) &&
	    !isSomeChar!(T) &&
	    !isArray!(T) &&
            !isAssociativeArray!(T))
{
	typeof(return) h = 0;
	foreach (ref a; t.tupleof)
	{ h = (h * 37) ^ a.toHash(); }
	return h;
}

void main()
{
	import std.stdio;
	writeln(tuple("hi", [[1: 2].keys.dup], [1: 2, 8: 4]).toHash());
	writeln(tuple("hi", [[1: 2].keys.dup], [1: 2, 8: 4]).toHash());  // same thing as above
}





We really _need_ something like this in Phobos IMHO.

On 10/24/2012 10:16 PM, Mehrdad wrote:
> ...
>
> Maybe you can fill in the blanks?
>
>

import std.stdio;
struct Set(T){
    int[T] dict;
    hash_t toHash() const{
        typeof(return) r = 0;
        foreach(item; this.dict.keys){
            r+=typeid(T).getHash(&item);
        }
        return r;
    }
}

On Wednesday, 24 October 2012 at 19:41:42 UTC, Mehrdad wrote:
> So you can't really write a real program in D, to put it blunty.

 So should I drop a project I'm working on and go to C++? That isn't something I look forward to doing...