Generic Dictionary Equality Comparer

up vote
4
down vote

favorite

I created the below comparer to allow me to use a generic dictionary as a key to another generic dictionary.

My GetHashCode implementation creates a hash based on all keys and their values; but I suspect its distribution could be improved?

Also my Equals method returns true only if the two arguments have exactly the same keys, with each key having exactly the same values. However, potentially there's a more efficient approach to this comparison which I've neglected?

using System.Collections.Generic;
using System.Linq;

namespace MyCompany.Collections.Generic

 public class DictionaryEqualityComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
 
 readonly IEqualityComparer<TKey> keyComparer;
 readonly IEqualityComparer<TValue> valueComparer;

 public DictionaryEqualityComparer(): this(null, null)
 public DictionaryEqualityComparer(IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
 
 this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
 this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;
 

 public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)
 b == null) return (a == null && b == null); //if either value is null return false, or true if both are null
 return a.Count == b.Count //unless they have the same number of items, the dictionaries do not match
 && a.Keys.Intersect(b.Keys, keyComparer).Count() == a.Count //unless they have the same keys, the dictionaries do not match
 && a.Keys.Where(key => ValueEquals(a[key], b[key])).Count() == a.Count; //unless each keys' value is the same in both, the dictionaries do not match
 

 public int GetHashCode(IDictionary<TKey, TValue> obj)
 
 //I suspect there's a more efficient formula for even distribution, but this does the job for now
 long hashCode = obj.Count;
 foreach (var key in obj.Keys)
 
 hashCode += (key?.GetHashCode() ?? 1000) + (obj[key]?.GetHashCode() ?? 0);
 hashCode %= int.MaxValue; //ensure we don't go outside the bounds of MinValue-MaxValue
 
 return (int)hashCode; //safe conversion thanks to the above %
 

 private bool ValueEquals(TValue x, TValue y)
 
 return valueComparer.Equals(x, y);

edited 3 hours ago

t3chb0t

32.8k744105

asked 3 hours ago

JohnLBevan

6451520

NB: After posting realised that my GetHashCode method doesn't handle nulls; so have since amended the first line to if (obj == null) return 0; long hashCode = obj.Count + 1;; so that null is handled, and an empty dictionary has a different hashcode to a null one.
â€“Â JohnLBevan
2 hours ago

add a commentÂ |Â

up vote
4
down vote

favorite

I created the below comparer to allow me to use a generic dictionary as a key to another generic dictionary.

My GetHashCode implementation creates a hash based on all keys and their values; but I suspect its distribution could be improved?

using System.Collections.Generic;
using System.Linq;

namespace MyCompany.Collections.Generic

 public class DictionaryEqualityComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
 
 readonly IEqualityComparer<TKey> keyComparer;
 readonly IEqualityComparer<TValue> valueComparer;

 public DictionaryEqualityComparer(): this(null, null)
 public DictionaryEqualityComparer(IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
 
 this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
 this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;
 

 public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)
 b == null) return (a == null && b == null); //if either value is null return false, or true if both are null
 return a.Count == b.Count //unless they have the same number of items, the dictionaries do not match
 && a.Keys.Intersect(b.Keys, keyComparer).Count() == a.Count //unless they have the same keys, the dictionaries do not match
 && a.Keys.Where(key => ValueEquals(a[key], b[key])).Count() == a.Count; //unless each keys' value is the same in both, the dictionaries do not match
 

 public int GetHashCode(IDictionary<TKey, TValue> obj)
 
 //I suspect there's a more efficient formula for even distribution, but this does the job for now
 long hashCode = obj.Count;
 foreach (var key in obj.Keys)
 
 hashCode += (key?.GetHashCode() ?? 1000) + (obj[key]?.GetHashCode() ?? 0);
 hashCode %= int.MaxValue; //ensure we don't go outside the bounds of MinValue-MaxValue
 
 return (int)hashCode; //safe conversion thanks to the above %
 

 private bool ValueEquals(TValue x, TValue y)
 
 return valueComparer.Equals(x, y);

edited 3 hours ago

t3chb0t

32.8k744105

asked 3 hours ago

JohnLBevan

6451520

NB: After posting realised that my GetHashCode method doesn't handle nulls; so have since amended the first line to if (obj == null) return 0; long hashCode = obj.Count + 1;; so that null is handled, and an empty dictionary has a different hashcode to a null one.
â€“Â JohnLBevan
2 hours ago

add a commentÂ |Â

up vote
4
down vote

favorite

I created the below comparer to allow me to use a generic dictionary as a key to another generic dictionary.

My GetHashCode implementation creates a hash based on all keys and their values; but I suspect its distribution could be improved?

using System.Collections.Generic;
using System.Linq;

namespace MyCompany.Collections.Generic

 public class DictionaryEqualityComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
 
 readonly IEqualityComparer<TKey> keyComparer;
 readonly IEqualityComparer<TValue> valueComparer;

 public DictionaryEqualityComparer(): this(null, null)
 public DictionaryEqualityComparer(IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
 
 this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
 this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;
 

 public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)
 b == null) return (a == null && b == null); //if either value is null return false, or true if both are null
 return a.Count == b.Count //unless they have the same number of items, the dictionaries do not match
 && a.Keys.Intersect(b.Keys, keyComparer).Count() == a.Count //unless they have the same keys, the dictionaries do not match
 && a.Keys.Where(key => ValueEquals(a[key], b[key])).Count() == a.Count; //unless each keys' value is the same in both, the dictionaries do not match
 

 public int GetHashCode(IDictionary<TKey, TValue> obj)
 
 //I suspect there's a more efficient formula for even distribution, but this does the job for now
 long hashCode = obj.Count;
 foreach (var key in obj.Keys)
 
 hashCode += (key?.GetHashCode() ?? 1000) + (obj[key]?.GetHashCode() ?? 0);
 hashCode %= int.MaxValue; //ensure we don't go outside the bounds of MinValue-MaxValue
 
 return (int)hashCode; //safe conversion thanks to the above %
 

 private bool ValueEquals(TValue x, TValue y)
 
 return valueComparer.Equals(x, y);

edited 3 hours ago

t3chb0t

32.8k744105

asked 3 hours ago

JohnLBevan

6451520

I created the below comparer to allow me to use a generic dictionary as a key to another generic dictionary.

My GetHashCode implementation creates a hash based on all keys and their values; but I suspect its distribution could be improved?

using System.Collections.Generic;
using System.Linq;

namespace MyCompany.Collections.Generic

 public class DictionaryEqualityComparer<TKey, TValue> : IEqualityComparer<IDictionary<TKey, TValue>>
 
 readonly IEqualityComparer<TKey> keyComparer;
 readonly IEqualityComparer<TValue> valueComparer;

 public DictionaryEqualityComparer(): this(null, null)
 public DictionaryEqualityComparer(IEqualityComparer<TKey> keyComparer, IEqualityComparer<TValue> valueComparer)
 
 this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
 this.valueComparer = valueComparer ?? EqualityComparer<TValue>.Default;
 

 public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)
 b == null) return (a == null && b == null); //if either value is null return false, or true if both are null
 return a.Count == b.Count //unless they have the same number of items, the dictionaries do not match
 && a.Keys.Intersect(b.Keys, keyComparer).Count() == a.Count //unless they have the same keys, the dictionaries do not match
 && a.Keys.Where(key => ValueEquals(a[key], b[key])).Count() == a.Count; //unless each keys' value is the same in both, the dictionaries do not match
 

 public int GetHashCode(IDictionary<TKey, TValue> obj)
 
 //I suspect there's a more efficient formula for even distribution, but this does the job for now
 long hashCode = obj.Count;
 foreach (var key in obj.Keys)
 
 hashCode += (key?.GetHashCode() ?? 1000) + (obj[key]?.GetHashCode() ?? 0);
 hashCode %= int.MaxValue; //ensure we don't go outside the bounds of MinValue-MaxValue
 
 return (int)hashCode; //safe conversion thanks to the above %
 

 private bool ValueEquals(TValue x, TValue y)
 
 return valueComparer.Equals(x, y);

c# .net generics dictionary

edited 3 hours ago

t3chb0t

32.8k744105

asked 3 hours ago

JohnLBevan

6451520

edited 3 hours ago

t3chb0t

32.8k744105

asked 3 hours ago

JohnLBevan

6451520

edited 3 hours ago

t3chb0t

32.8k744105

edited 3 hours ago

t3chb0t

32.8k744105

edited 3 hours ago

t3chb0t

32.8k744105

asked 3 hours ago

JohnLBevan

6451520

asked 3 hours ago

JohnLBevan

6451520

asked 3 hours ago

JohnLBevan

6451520

NB: After posting realised that my GetHashCode method doesn't handle nulls; so have since amended the first line to if (obj == null) return 0; long hashCode = obj.Count + 1;; so that null is handled, and an empty dictionary has a different hashcode to a null one.
â€“Â JohnLBevan
2 hours ago

add a commentÂ |Â

NB: After posting realised that my GetHashCode method doesn't handle nulls; so have since amended the first line to if (obj == null) return 0; long hashCode = obj.Count + 1;; so that null is handled, and an empty dictionary has a different hashcode to a null one.
â€“Â JohnLBevan
2 hours ago

NB: After posting realised that my GetHashCode method doesn't handle nulls; so have since amended the first line to if (obj == null) return 0; long hashCode = obj.Count + 1;; so that null is handled, and an empty dictionary has a different hashcode to a null one.
â€“Â JohnLBevan
2 hours ago

add a commentÂ |Â

1 Answer
1

active

oldest

votes

up vote
3
down vote

It looks pretty OK to me, may be I would create Equals(...) like:

public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)

 if (a == null

It should be sufficient to look up by one of the dictionaries, because we know they are equal in size, so an entry in a should find an equal entry in b if the are equal all in all. I haven't tested it but it seems that it should be faster compared to Intersect().Count() && ...Where() because there is only one iteration/lookup?

answered 42 mins ago

Henrik Hansen

5,4081620

2

Nice one; that's a great solution. I may swap !a.Any(kvpA => !b.TryGetValue(kvpA.Key, out TValue vB) || !valueComparer.Equals(kvpA.Value, vB)); for a.All(kvpA => b.TryGetValue(kvpA.Key, out TValue vB) && valueComparer.Equals(kvpA.Value, vB)); to remove a few double negatives, but really like this approach; thanks for the tip.
â€“Â JohnLBevan
30 mins ago

@JohnLBevan: that's better and equally efficient.
â€“Â Henrik Hansen
6 mins ago

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "",
contentPolicyHtml: "",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206645%2fgeneric-dictionary-equality-comparer%23new-answer', 'question_page');

);

Post as a guest

Name

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

up vote
3
down vote

It looks pretty OK to me, may be I would create Equals(...) like:

public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)

 if (a == null

answered 42 mins ago

Henrik Hansen

5,4081620

2

Nice one; that's a great solution. I may swap !a.Any(kvpA => !b.TryGetValue(kvpA.Key, out TValue vB) || !valueComparer.Equals(kvpA.Value, vB)); for a.All(kvpA => b.TryGetValue(kvpA.Key, out TValue vB) && valueComparer.Equals(kvpA.Value, vB)); to remove a few double negatives, but really like this approach; thanks for the tip.
â€“Â JohnLBevan
30 mins ago

@JohnLBevan: that's better and equally efficient.
â€“Â Henrik Hansen
6 mins ago

add a commentÂ |Â

up vote
3
down vote

It looks pretty OK to me, may be I would create Equals(...) like:

public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)

 if (a == null

answered 42 mins ago

Henrik Hansen

5,4081620

2

Nice one; that's a great solution. I may swap !a.Any(kvpA => !b.TryGetValue(kvpA.Key, out TValue vB) || !valueComparer.Equals(kvpA.Value, vB)); for a.All(kvpA => b.TryGetValue(kvpA.Key, out TValue vB) && valueComparer.Equals(kvpA.Value, vB)); to remove a few double negatives, but really like this approach; thanks for the tip.
â€“Â JohnLBevan
30 mins ago

@JohnLBevan: that's better and equally efficient.
â€“Â Henrik Hansen
6 mins ago

add a commentÂ |Â

up vote
3
down vote

It looks pretty OK to me, may be I would create Equals(...) like:

public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)

 if (a == null

answered 42 mins ago

Henrik Hansen

5,4081620

It looks pretty OK to me, may be I would create Equals(...) like:

public bool Equals(IDictionary<TKey, TValue> a, IDictionary<TKey, TValue> b)

 if (a == null

answered 42 mins ago

Henrik Hansen

5,4081620

answered 42 mins ago

Henrik Hansen

5,4081620

answered 42 mins ago

Henrik Hansen

5,4081620

answered 42 mins ago

Henrik Hansen

5,4081620

2

Nice one; that's a great solution. I may swap !a.Any(kvpA => !b.TryGetValue(kvpA.Key, out TValue vB) || !valueComparer.Equals(kvpA.Value, vB)); for a.All(kvpA => b.TryGetValue(kvpA.Key, out TValue vB) && valueComparer.Equals(kvpA.Value, vB)); to remove a few double negatives, but really like this approach; thanks for the tip.
â€“Â JohnLBevan
30 mins ago

@JohnLBevan: that's better and equally efficient.
â€“Â Henrik Hansen
6 mins ago

add a commentÂ |Â

2

Nice one; that's a great solution. I may swap !a.Any(kvpA => !b.TryGetValue(kvpA.Key, out TValue vB) || !valueComparer.Equals(kvpA.Value, vB)); for a.All(kvpA => b.TryGetValue(kvpA.Key, out TValue vB) && valueComparer.Equals(kvpA.Value, vB)); to remove a few double negatives, but really like this approach; thanks for the tip.
â€“Â JohnLBevan
30 mins ago

@JohnLBevan: that's better and equally efficient.
â€“Â Henrik Hansen
6 mins ago

Nice one; that's a great solution. I may swap !a.Any(kvpA => !b.TryGetValue(kvpA.Key, out TValue vB) || !valueComparer.Equals(kvpA.Value, vB)); for a.All(kvpA => b.TryGetValue(kvpA.Key, out TValue vB) && valueComparer.Equals(kvpA.Value, vB)); to remove a few double negatives, but really like this approach; thanks for the tip.
â€“Â JohnLBevan
30 mins ago

@JohnLBevan: that's better and equally efficient.
â€“Â Henrik Hansen
6 mins ago

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky