digitalmars.D.learn - Why Does Dscanner Warn About a Missing toHash if opEquals is Defined?
- Jack Stouffer (2/2) Jul 31 2016 Is it really a problem? What are the pitfalls of defining one but
- LaTeigne (2/4) Jul 31 2016 iirc usage in an AA requires both.
- Jack Stouffer (3/7) Jul 31 2016 But D provides a default toHash for every type if it's not
- BLM768 (20/22) Jul 31 2016 If two objects are equal, their hashes must also be equal.
- Jack Stouffer (5/6) Jul 31 2016 Ok, yeah that is bad.
- pineapple (12/15) Aug 01 2016 There's no hashing function that would be specifically better for
- qlksgj (6/7) Aug 01 2016 Not totally true: when the hash map content is static (i.e known
- BLM768 (4/7) Aug 02 2016 I've heard that FNV-1a is a decent general-purpose option, and
- mlsgmls (3/9) Aug 03 2016 This could be of interest
Is it really a problem? What are the pitfalls of defining one but not the other?
Jul 31 2016
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
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:But D provides a default toHash for every type if it's not defined. I was wondering why not just rely on that version.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
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
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
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
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
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
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:This could be of interest http://aras-p.info/blog/2016/08/02/Hash-Functions-all-the-way-down/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?
Aug 03 2016