GetHashCode and Equals

1 背景

Dictionary和HashTable是.NET中经常使用的数据结构。但是，之前对其原理不是太清楚，本文简单介绍下其工作原理： Object.GetHashCode 和 Object.Equals 的作用。

2 哈希查找

哈希查找是Dictionary和HashTable的基础。建议首先看下哈希查找的工作原理。哈希查找算法分为两部分：1.数据存储算法；2.数据读取算法。这里以.NET的实现为例简要分析下算法流程。

2.1 数据存储算法

Figure 1: 数据存储算法

从图中可以看出，只有在发生冲突的时候Object.Equals方法才会被调用。

2.2 数据读取算法

Figure 2: 数据读取算法

从图中可以看出，在读取数据时，无论发生冲突与否Object.Equals方法都会被调用。

另外，MSDN中有提到，当两个对象相同时其Hash值肯定相同，而两个对象的Hash值相同时两个对象未必相同。所以，为了保证数据存取的正确性，如果需要重载，这两个方法最好一起重载。