Using the field of an object as a generic Dictionary key
Solution 1
By default, the two important methods are GetHashCode()
and Equals()
. It is important that if two things are equal (Equals()
returns true), that they have the same hash-code. For example, you might "return FooID;" as the GetHashCode()
if you want that as the match. You can also implement IEquatable<Foo>
, but that is optional:
class Foo : IEquatable<Foo> {
public string Name { get; set;}
public int FooID {get; set;}
public override int GetHashCode() {
return FooID;
}
public override bool Equals(object obj) {
return Equals(obj as Foo);
}
public bool Equals(Foo obj) {
return obj != null && obj.FooID == this.FooID;
}
}
Finally, another alternative is to provide an IEqualityComparer<T>
to do the same.
Solution 2
As you want the FooID
to be the identifier for the group, you should use that as key in the dictionary instead of the Foo object:
Dictionary<int, List<Stuff>>
If you would use the Foo
object as key, you would just implement the GetHashCode
and Equals
method to only consider the FooID
property. The Name
property would just be dead weight as far as the Dictionary
was concerned, so you would just use Foo
as a wrapper for an int
.
Therefore it's better to use the FooID
value directly, and then you don't have to implement anything as the Dictionary
already supports using an int
as a key.
Edit:
If you want to use the Foo
class as key anyway, the IEqualityComparer<Foo>
is easy to implement:
public class FooEqualityComparer : IEqualityComparer<Foo> {
public int GetHashCode(Foo foo) { return foo.FooID.GetHashCode(); }
public bool Equals(Foo foo1, Foo foo2) { return foo1.FooID == foo2.FooID; }
}
Usage:
Dictionary<Foo, List<Stuff>> dict = new Dictionary<Foo, List<Stuff>>(new FooEqualityComparer());
Solution 3
For Foo you will need to override object.GetHashCode() and object.Equals()
The dictionary will call GetHashCode() to calculate a hash bucket for each value and Equals to compare whether two Foo's are identical.
Make sure to calculate good hash codes (avoid many equal Foo objects having the same hashcode), but make sure two equals Foos have the same hash code. You might want to start with the Equals-Method and then (in GetHashCode()) xor the hash code of every member you compare in Equals.
public class Foo {
public string A;
public string B;
override bool Equals(object other) {
var otherFoo = other as Foo;
if (otherFoo == null)
return false;
return A==otherFoo.A && B ==otherFoo.B;
}
override int GetHashCode() {
return 17 * A.GetHashCode() + B.GetHashCode();
}
}
Solution 4
What about Hashtable
class!
Hashtable oMyDic = new Hashtable();
Object oAnyKeyObject = null;
Object oAnyValueObject = null;
oMyDic.Add(oAnyKeyObject, oAnyValueObject);
foreach (DictionaryEntry de in oMyDic)
{
// Do your job
}
In above way, you can use any object (your class object) as a generic Dictionary key :)
Solution 5
I had the same problem. I can now use any object I've tried as a key due to overriding Equals and GetHashCode.
Here is a class that I built with methods to use inside of the overrides of Equals(object obj) and GetHashCode(). I decided to use generics and a hashing algorithm that should be able to cover most objects. Please let me know if you see anything here that doesn't work for some types of object and you have a way to improve it.
public class Equality<T>
{
public int GetHashCode(T classInstance)
{
List<FieldInfo> fields = GetFields();
unchecked
{
int hash = 17;
foreach (FieldInfo field in fields)
{
hash = hash * 397 + field.GetValue(classInstance).GetHashCode();
}
return hash;
}
}
public bool Equals(T classInstance, object obj)
{
if (ReferenceEquals(null, obj))
{
return false;
}
if (ReferenceEquals(this, obj))
{
return true;
}
if (classInstance.GetType() != obj.GetType())
{
return false;
}
return Equals(classInstance, (T)obj);
}
private bool Equals(T classInstance, T otherInstance)
{
List<FieldInfo> fields = GetFields();
foreach (var field in fields)
{
if (!field.GetValue(classInstance).Equals(field.GetValue(otherInstance)))
{
return false;
}
}
return true;
}
private List<FieldInfo> GetFields()
{
Type myType = typeof(T);
List<FieldInfo> fields = myType.GetTypeInfo().DeclaredFields.ToList();
return fields;
}
}
Here is how it's used in a class:
public override bool Equals(object obj)
{
return new Equality<ClassName>().Equals(this, obj);
}
public override int GetHashCode()
{
unchecked
{
return new Equality<ClassName>().GetHashCode(this);
}
}
Comments
-
Dana about 4 years
If I want to use objects as the keys for a
Dictionary
, what methods will I need to override to make them compare in a specific way?Say I have a a class which has properties:
class Foo { public string Name { get; set; } public int FooID { get; set; } // elided }
And I want to create a:
Dictionary<Foo, List<Stuff>>
I want
Foo
objects with the sameFooID
to be considered the same group. Which methods will I need to override in theFoo
class?To summarize: I want to categorize
Stuff
objects into lists, grouped byFoo
objects.Stuff
objects will have aFooID
to link them to their category. -
Marc Gravell about 15 yearsAside - but xor (^) makes a poor combinator for hash-codes, as it often leads to a lot of diagonal collisions (i.e. {"foo","bar"} vs {"bar","foo"}. A better choice is to multiply and add each term - i.e. 17 * a.GetHashCode() + B.GetHashCode();
-
Raph about 15 years+1 and I don't mean to hijack this thread but I was under the impression that GetHashCode() should return FooId.GetHashCode(). Is this not the right pattern?
-
Jim Mischel about 15 yearsMore correctly, int already supports the methods/interfaces required for it to be used as a key. Dictionary has no direct knowledge of int or any other type.
-
Dana about 15 yearsThanks! I went with the IEqualityComparer<T> as it was only for the Dicarionary that I needed the overriden methods.
-
Dana about 15 yearsI thought about that, but for a variety of reasons it was cleaner and more convenient to use the objects as the dictionary keys.
-
Guffa about 15 yearsWell, it only looks like you are using the object as key, as you are really only using the id as key.
-
froh42 about 15 yearsMarc, I see what you mean. But how do you get at the magic number 17? Is it advantageous to use a prime number as a multiplicator for combining hashes? If so, why?
-
Charles Burns almost 13 yearsMay I suggest returning: (A + B).GetHashCode() rather than: 17 * A.GetHashCode() + B.GetHashCode() This will: 1) Be less likely to have a collision and 2) ensure that there is no integer overflow.
-
kaesve over 10 years(A + B).GetHashCode() makes for a very bad hashing algorithm, as different sets of (A, B) can result in the same hash if they are concatenate to the same string; "hellow" + "ned" is the same as "hell" + "owned" and would result in the same hash.
-
Timeless almost 10 years@kaesve how about (A+" "+B).GetHashCode() ?
-
Jørgen Fogh over 9 yearsYou should be aware that the performance of containers based on hashtables (Dictionary<T>, Dictionary, HashTable, etc.) depends on the quality of the hash function used. If you simply FooID as the hash code, the containers might perform very poorly.
-
Marc Gravell over 9 years@JørgenFogh I am very aware of that; the example presented is consistent with the stated intent. There's a lot of related concerns related to hash immutability; ids change less often than names, and are usually reliably unique and indicators of equivalence. A non-trivial subject, though.
-
Dave_cz about 8 yearsThis method makes it possibile to create duplicate keys! Create Foo with ID, insert it, change ID & insert it again. Now you have duplicate keys! Is this intended?
-
gillonba about 8 yearstry A.GetHashCode() ^ B.GetHashCode()
-
froh42 about 8 years@rotard when you read above that was my original assumption as well, but it has been suggested 17 * a.getHashCode() + b.getHashCode() is better to prevent diagonal collisions. See other comments.
-
Cardin almost 8 yearsAlmost missed the override, as I wasn't expected
Equals(obj)
. Btw, it is alright for the hashcode to be the same, as it is pretty difficult to generate unique ids all the time. When the hashcode is the same, it ends up relying onEquals(obj)
instead. However, there might be performance issues, so keep the hashcode duplication to a minimum. -
user666412 almost 6 yearsShouldn't
FooID
be areadonly
property, since it's acting as a hash? -
Marc Gravell almost 6 years@user666412 yes, it should