Problem Background#
First, I want to mention a pitfall encountered during the development of a previous project regarding using custom types as Dictionary keys.
In the project, we had two business classes, BusinessA and BusinessB. Due to a certain requirement, we needed to establish a mapping relationship between these two classes, so we introduced a Dictionary data structure to associate them:
private Dictionary<BusinessA, BusinessB> businessDic = new Dictionary<BusinessA, BusinessB>();
// Provide an external lookup method to find B from the dictionary using A
public BusinessB FindB(BusinessA a)
{
if (businessDic.ContainsKey(a))
{
return businessDic[a];
}
return null;
}
Since the project was developed collaboratively, as the business logic continued to grow, modifications were made to certain Key objects in the dictionary (the data of the BusinessA object remained unchanged). Later, when we tried to find the corresponding BusinessB object using that object again, we found that it returned null. Our entire development team spent a long time troubleshooting before discovering the cause of this bug.
Problem Analysis#
The root cause of this bug lies in a lack of deep understanding of the underlying storage principles of Dictionary in C#:
When you add a key to the dictionary, the Dictionary uses a hash function to compute the hash code of that key, which is an integer value used to determine the position of the key in the internal array.
Initially, we thought that if a reference type object was used as a Dictionary key, as long as the data of the key object did not change, we could retrieve the corresponding value using the key.
Necessary Conditions for Using Dictionary Keys#
In C#, when using a dictionary (Dictionary<TKey, TValue>) to quickly look up values (Value) using keys, the keys must meet two important conditions:
- Comparability
Keys must be correctly comparable to determine their uniqueness. The dictionary uses the Equals method internally to compare keys, ensuring that the same key maps to the same value.
- Immutability
Once a key is added to the dictionary, ==its value cannot be changed==. If the state of the key changes after being added to the dictionary, the dictionary's lookup mechanism may fail, leading to bugs.
Considerations for Using Reference Types as Keys#
Using Unstable Keys#
To ensure the correctness of the dictionary, keys should remain unchanged during dictionary operations. Generally, modifications to the state of key objects within the dictionary should be avoided. It is recommended to use immutable objects as keys. You can use readonly fields or read-only properties to ensure the immutability of key objects.
Key Equality Comparison#
Ensure that you implement your Equals and GetHashCode methods correctly and simultaneously. The equality comparison should consider all fields that affect the identity of the object, and the GetHashCode method should always return the same value (if the object's state has not changed).
You can see the output of the following example code:
public class BusinessA
{
public int id;
public string name;
public BusinessA(int _id, string _name)
{
id = _id;
name = _name;
}
public override bool Equals(object obj)
{
if (obj == null) return false;
BusinessA another = obj as BusinessA;
if (another != null)
{
return id == another.id && name == another.name;
}
return false;
}
}
public class BusinessB
{
private string describe;
private string score;
public BusinessB(string _des, string _score)
{
describe = _des;
score = _score;
}
}
public class DictionaryDemo : MonoBehaviour
{
private Dictionary<BusinessA, BusinessB> businessDic = new Dictionary<BusinessA, BusinessB>();
private BusinessA bA;
private BusinessB bB;
private BusinessA bAA;
void Start()
{
int id = 100;
string name = "zzz";
// Declare two objects bA and bAA with the same internal data as keys for storage and lookup
bA = new BusinessA(id, name);
bAA = new BusinessA(id, name);
// Declare value
bB = new BusinessB("yyy", "100");
// bA and bB will be added to the dictionary
businessDic.Add(bA, bB);
// Use bAA to find bB in the dictionary
BusinessB findB = FindB(bAA);
BusinessB findB1 = FindB(bA);
// Compare if findB is equal to bB
Debug.Log(bB == findB);
}
public BusinessB FindB(BusinessA a)
{
if (businessDic.ContainsKey(a))
{
return businessDic[a];
}
return null;
}
}
Console output:
From this, we can see that although the internal member data of the two objects bA and bAA is the same, the GetHashCode method has not been overridden, so they are effectively two different objects with different hash values. Using bAA cannot find the Value, returning null, so bB is not equal to findB.
Solution#
From this, we derive the solution: when using a dictionary to store key-value pairs, if you need to use custom types as dictionary keys, then the custom type should override and correctly implement the GetHashCode method.
Verification:
We override the GetHashCode method in BusinessA:
public override int GetHashCode()
{
return string.Format("{0}-{1}", id, name).GetHashCode();
}
Console output:
Thus, although bA and bAA are different object references, after overriding the GetHashCode method, the dictionary lookup can correctly match the corresponding key, allowing us to find the Value, so findB is equal to bB.
==Both Equals and GetHashCode methods are indispensable.==
Summary#
When bugs occur at the code level, it is often due to a lack of understanding of some underlying logic. It is essential to test, verify, and understand the principles regularly. Therefore, when using a dictionary as a data structure for storage and querying, it is still recommended to use immutable types as keys, such as value types (int, float, etc.) or commonly used reference types like string. If you must use custom types as dictionary keys, then two points should be noted: 1. Avoid modifying keys during dictionary operations; 2. The object used as the key must override and correctly implement the Equals and GetHashCode methods. By following these principles, you can avoid bugs caused by using custom type objects as dictionary keys.