www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Why Does Dscanner Warn About a Missing toHash if opEquals is Defined?

reply Jack Stouffer <jack jackstouffer.com> writes:
Is it really a problem? What are the pitfalls of defining one but 
not the other?
Jul 31 2016
parent reply LaTeigne <LaTeigne blabla.fr> writes:
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.
Jul 31 2016
parent reply Jack Stouffer <jack jackstouffer.com> writes:
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.
Jul 31 2016
parent reply BLM768 <blm768 gmail.com> writes:
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)
Jul 31 2016
parent reply Jack Stouffer <jack jackstouffer.com> writes:
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?
Jul 31 2016
next sibling parent reply pineapple <meapineapple gmail.com> writes:
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.
Aug 01 2016
parent qlksgj <qlksgj qlksgj.kl> writes:
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.
Aug 01 2016
prev sibling next sibling parent BLM768 <blm768 gmail.com> writes:
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
Aug 02 2016
prev sibling parent mlsgmls <mlsgmls mlsgmls.de> writes:
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/
Aug 03 2016