Is it really a problem? What are the pitfalls of defining one but not the other?

On Sunday, 31 July 2016 at 15:21:01 UTC, Jack Stouffer wrote:
> Is it really a problem? What are the pitfalls of defining one but not the other?

iirc usage in an AA requires both.

On Sunday, 31 July 2016 at 15:30:15 UTC, LaTeigne wrote:
> On Sunday, 31 July 2016 at 15:21:01 UTC, Jack Stouffer wrote:
>> Is it really a problem? What are the pitfalls of defining one but not the other?
>
> iirc usage in an AA requires both.

But D provides a default toHash for every type if it's not defined. I was wondering why not just rely on that version.

On Sunday, 31 July 2016 at 16:39:59 UTC, Jack Stouffer wrote:
> But D provides a default toHash for every type if it's not defined. I was wondering why not just rely on that version.

If two objects are equal, their hashes must also be equal. Consider this example:

struct Nullable(T) {
  bool isNull;
  T value;

  bool opEquals(Nullable!T other) {
    if(this.isNull != other.isNull) return false;
    // Any two nulls are equal.
    if(isNull) return true;
    return this.value == other.value;
  }
}

auto n1 = Nullable!int(true, 3);
auto n2 = Nullable!int(true, 4);

writeln(n1 == n2); // true
writeln(n1.hashOf == n2.hashOf); // false = BAD!

Now that I think about it, maybe this should be in the language docs; I don't think they mention it. (https://dlang.org/spec/operatoroverloading.html#equals)

On Sunday, 31 July 2016 at 17:48:48 UTC, BLM768 wrote:
> writeln(n1.hashOf == n2.hashOf); // false = BAD!

Ok, yeah that is bad.

Next question: what's the fastest hashing implementation that will provide the least collisions? Is there a hash implementation that's perfered for AAs?

On Sunday, 31 July 2016 at 18:57:50 UTC, Jack Stouffer wrote:
> Next question: what's the fastest hashing implementation that will provide the least collisions? Is there a hash implementation that's perfered for AAs?

There's no hashing function that would be specifically better for associative arrays, it's a hashing function either way. The primary things that should affect what your hashing function looks like should be what your inputs - keys for an AA - look like.

djb2 is my go-to for string hashing because it's conceptually simple, efficient, and effective for most use cases.

http://www.cse.yorku.ca/~oz/hash.html

Every hashing function will produce collisions. As long as you handle them, and as long as they aren't inordinately frequent, you'll be fine.

On Monday, 1 August 2016 at 10:35:29 UTC, pineapple wrote:
> Every hashing function will produce collisions.

Not totally true: when the hash map content is static (i.e known at compile time) there are probabilities that a perfect hashing function exists. But these kind of functions are a bit special because each byte of the value maps to another byte. See the gnu tool "gperf" for example.

On Sunday, 31 July 2016 at 18:57:50 UTC, Jack Stouffer wrote:
> Next question: what's the fastest hashing implementation that will provide the least collisions? Is there a hash implementation that's perfered for AAs?

I've heard that FNV-1a is a decent general-purpose option, and it's fairly straightforward.

https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

On Sunday, 31 July 2016 at 18:57:50 UTC, Jack Stouffer wrote:
> On Sunday, 31 July 2016 at 17:48:48 UTC, BLM768 wrote:
>> writeln(n1.hashOf == n2.hashOf); // false = BAD!
>
> Ok, yeah that is bad.
>
> Next question: what's the fastest hashing implementation that will provide the least collisions? Is there a hash implementation that's perfered for AAs?

This could be of interest

http://aras-p.info/blog/2016/08/02/Hash-Functions-all-the-way-down/