下面的内容中有很多一部分是笔者自己的想法,所以有些说法可能会有失偏颇,还望指正。
Wanger说GetHashCode()是他在Effective C#所有的50个建议中唯一一项关于不推荐函数的建议。GetHashCode()这个方法只会用于一个地方:给基于Hash的Collection(比如HashTable和Dictionary)的Key定义Hash值,也就是对象做为Key,而对象的GetHashCode()为该Key获取Hash值。
说到Hash,先说一下Hash查找算法。
我们知道大部分的查找算法,顺序查找,二分查找或者是B-Tree查找,由于查找的关键字和待查找的记录地址之间没有必然的联系,都是基于比较的,无非是在比较的次数上有多有少。最理想的算法当然是不比较,能够直接通过关键字得到待查找的记录的地址,这就是Hash查找了。通过Hash函数,将记录的Key值直接对应到记录的地址,一个Key对应一个地址,由于Key值是某种语言中所有允许标志符的全集,比某个程序中可能用到的地址空间大很多,这样就势必会有不同的Key值对应相同地址的情况,良好的Hash算法要求,经过Hash函数运算由Key得到的地址空间是均匀的,也就是地址空间是随机的。但是不可能完全避免上述情况,于是又有各种侦探和解决地址冲突的算法。
OK,上面的内容是数据结构的基础知识,大家应该都知道,不过做为一个完整的读后感,不提这些好像不完整,如果熟知的话,可以略过以上内容。
对应到HashTable 中,自定义的类就是Key,而GetHashCode()就是那个Hash算法,GethHashCode()得到的值就是HashTable存储的对象的内存地址。
于是就有Wanger提到的一个良好的GetHashCode()必须满足的三个条件。
1.两个对象Equals,则通过GetHashCode()得到的值必须相同。
对象做为Key值,必须对应一个Value对象,如果得到的值不同,则会出现一个Key对应多个Value对象的情况,这违背了Key的原始意义,不过如果你非要违背这个原则,在HashTable的语法中也是没有任何问题的(这个在后面会举例论述)只不过违背了Key的语意。
2.通过GetHashCode()得到的值必须是恒定不变的。
这个很明显,如果在存储以后这个值可以随意变动,在通过Key取Value的时候就会有问题,在语法上会报经典的“未将对象引用设置到对象实例”。
3.通过GetHashCode()得到的值必须在整数的取值范围内是均匀分布的。
这样做的目的是提高HashTable的查找效率。
Wanger随后给出了Object的GetHashCode()和ValueType的GetHashCode()的算法,以及是否满足上述三条原则。
下面简要叙述一下,有兴趣的可以看一下原著。
Object,默认的Equals()是通过Object创建时生成的Identity来比较的,而GetHashCode()是从1开始递增的序列值,所以如果Equals相等,则GetHashCode()必然相等。当然第二条也能满足,因为没办法修改这个GetHashCode的值。第三条就不能满足了,除非是创建大量的Object。
ValueType,Equals()是通过比较各个字段的值,而GetHashCode()是通过比较第一个字段的值来实现的,这样也能保证第一条。第二条就不一定能保证了,如果第一个字段不是Readonly的,那由它得到的HashCode也是变化的。第三条规则取决于第一个字段怎么使用。
下面举个简单的例子。
/// <summary>
/// 做为键的类
/// </summary>
class keyClass
{
private string name;
public string _name
{
get
{
return name;
}
set
{
name = value;
}
}
private string code;
public string _code
{
get
{
return code;
}
set
{
code = value;
}
}
public override bool Equals(object obj)
{
if(null == obj)
return false;
if(obj.GetType()!=this.GetType())
return false;
return(((keyClass)obj)._name.Equals(this._name));
}
public override int GetHashCode()
{
return this._code.GetHashCode();
}
}
测试类
/// <summary>
/// 测试键值的Hashtable
/// </summary>
class HashTableTest
{
/// <summary>
/// 应用程序的主入口点。
/// </summary>
[STAThread]
static void Main(string[] args)
{
keyClass testKey = new keyClass();
testKey._code = "110";
testKey._name = "222";
keyClass testKey2 = new keyClass();
testKey2._code = "111";
testKey2._name = "222";
System.Collections.Hashtable aa = new Hashtable();
aa.Add(testKey,"test");
aa.Add(testKey2,"test2");
Console.WriteLine(aa[testKey].ToString());
Console.WriteLine(aa[testKey2].ToString());
Console.ReadLine();
}
}
单步跟踪一下上述代码就会发现HashTable创建和查找的过程。
创建:
首先根据键对象的GetHashTable()(当然在创建HashTable的时候可以制定其他的Hash函数做为寻址函数,这里不予讨论)得到HashCode,如果在存储桶中该地址没有被占用,则将其存入其中,如果占用了则调用当前Key对象的Equals方法判断占用该地址的对象跟当前Key对象是否是同一对象,如果是则抛出异常,说该项已经存在于HashTable中(我不知道是否有办法在存储桶中存储两个HasCode和Key值都相同的对象,不过理论上应该是不允许的)。如果不是同一对象则在存储桶中另外找个地方把对象存起来。
查找
首先根据键对象的GetHashTable()(当然在创建HashTable的时候可以制定其他的Hash函数做为寻址函数,这里不予讨论)得到HashCode,然后将存储桶中对应的key对象跟当前的Key值通过Equals方法比较,看是否为同一对象,如果不同则继续查找。
靠,这不就是Hash算法的过程嘛!
对啊,我也没说不是啊。
那你直接说跟Hash的查找的算法一样不就行了
唉,不是要凑篇幅嘛!
自从.NET Framework 2.0引入泛型之后,对集合的使用就开创了新的局面。首先我们不用考虑类型是否安全,利用泛型以及对泛型参数的约束完全可以保障这一点;其次,集合元素不会因为频繁的Boxing和Unboxing而影响集合遍历与操作的性能。泛型带来的这两点好处毋庸置疑。在Dictionary<TKey, TValue>中,除了字符串,我们普遍会使用值类型作为它的key,例如int类型。而枚举类型作为一种值类型,在某些时候特别是需要位操作的时候,也会经常用作key。问题就出现在这里。
我们知道,Dictionary的key必须是唯一的标识,因此Dictionary需要对key进行判等的操作,如果key的类型没有实现 IEquatable接口,则默认根据System.Object.Equals()和GetHashCode()方法判断值是否相等。我们可以看看常用作key的几种类型在.NET Framework中的定义:
public sealed
class String : IComparable, ICloneable, IConvertible,
IComparable<string>, IEnumerable<string>, IEnumerable,
IEquatable<string>
public struct
Int32 : IComparable, IFormattable,
IConvertible, IComparable<int>, IEquatable<int>
public abstractclass
Enum : ValueType,
IComparable, IFormattable, IConvertible
注意Enum类型的定义与前两种类型的不同,它并没有实现IEquatable接口。因此,当我们使用Enum类型作为key值时,Dictionary的内部操作就需要将Enum类型转换为System.Object,这就导致了Boxing的产生。没错,我们很难发现这个陷阱,它是导致Enum作为 key值的性能瓶颈。
我们该如何解决这一问题?最简单的方法是将Enum的值先转换为int,然后将其作为key传入Dictionary中。还有一种作法是定义一个实现了IEqualityComparer<T>接口的类。因为Dictionary构造函数的其中一个重载版本,可以接收 IEqualityComparer<T>类型,通过它完成对key的判断。IEqualityComparer<T>接口的定义如下所示:
public interface IEqualityComparer<T>
{
bool Equals(T x, T y);
int GetHashCode(T obj);
}
遗憾的是我们却不能直接提供针对Enum的实现,例如:
class EnumComparer<TEnum> : IEqualityComparer<TEnum>
{
public bool Equals(TEnum x, TEnum y)
{
return (x == y);
}
public int GetHashCode(TEnum obj)
{
return (int)obj;
}
}
因为我们不能直接对泛型类型进行==操作,以及将泛型对象强制转换为int类型。在Code Project上,有一篇名为Accelerating
Enum-Based Dictionaries with Generic EnumComparer的文章,利用Reflection.Emit实现Equals()和GetHashCode()方法。不过在该文的评论中,提供了更好的一个方法,就是利用C# 3.0的Lambda表达式:
public class
EnumComparer<T> : IEqualityComparer<T> where T :
struct
{
public bool Equals(T first, T second)
{
var firstParam = Expression.Parameter(typeof(T),"first");
var secondParam = Expression.Parameter(typeof(T),"second");
var equalExpression = Expression.Equal(firstParam, secondParam);
return Expression.Lambda<Func<T, T,
bool>>
(equalExpression, new[]
{ firstParam, secondParam }).
Compile().Invoke(first, second);
}
public int GetHashCode(T instance)
{
var parameter = Expression.Parameter(typeof(T),"instance");
var convertExpression = Expression.Convert(parameter,
typeof(int));
return Expression.Lambda<Func<T,
int>>
(convertExpression, new[]{parameter}).
Compile().Invoke(instance);
}
}
此时,我们就可以如此使用Dictionary对象:
public enum DayOfWeek{//...}
var dictionary = new Dictionary<DayOfWeek,
int>(new EnumComparer<DayOfWeek>());
采取这样的做法比直接用Enum类型作为Dictionary的key差不多要快8倍。这难道不让人为之惊诧吗?
class LongArray
{
public long[] array;
public LongArray(long[] arrays)
{
array = arrays;
}
public override int GetHashCode()
{
int Result = 0;
for (var i = 0; i < array.Length; i++)
{
Result += (i + 1) * (int)array[i];
}
return Result;
}
public override bool Equals (Object Arrays) //重写Equals方法
{
var data = ((LongArray)Arrays).array;
if (data.Length == array.Length)
{
for (var i = 0; i < array.Length; i++)
{
if (data[i] == array[i])
{
continue;
}
else
{
return false;
}
}
return true;
}
return false;
}
}
本文出自 “晴窗笔记” 博客,请务必保留此出处http://wayfarer.blog.51cto.com/1300239/280088
相关推荐
C# Equals 和 GetHashCode 方法重写,
winform 重写GetHashCode源码! 很值得下载看看!资源免费,大家分享!!
主要介绍了C#中Equals和GetHashCode使用及区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
C#5.0本质论第四版,高清扫描的,对C#5.0技术讲的比较详细,第1章 C#概述 1 1.1 Hello,World 1 1.2 C#语法基础 3 1.2.1 C#关键字 3 1.2.2 标识符 4 1.2.3 类型定义 5 1.2.4 Main 6 1.2.5...
继续分享下GetHashCode和ExpandoObject这两个比较好玩的方法。
9.1.2 重写gethashcode() 9.1.3 重写equals() 9.1.4 相等性实现的指导原则 9.2 运算符重载 9.2.1 比较运算符 9.2.2 二元运算符 9.2.3 赋值运算符与二元运算符的结合 9.2.4 条件逻辑运算符 9.2.5 一元...
我有以下课程 public class ModInfo : IEquatable { public int ID { get; set; } public string MD5 { get; set; } public bool Equals...我使用如下方法将一些数据加载到该类的列表中: public void Relo
Effective C# (Covers C# 4.0): 50 Specific Ways to Improve Your C#, Second Edition 352 pages Publisher: Addison-Wesley Professional; 2 edition (March 15, 2010) Language: English ISBN-10: 0321658701...
理解 ReferenceEquals, static Equals, instance Equals 和 比较运算符(==)之间的关系 10.理解 GetHashCode方法的缺陷 11.在编写循环时,优先使用 foreach. 12.在定义变量的时候就将其初始化 13.使用静态...
这是的 .NET 端口的努力EqualsVerifier 可用于 .NET 单元测试,以验证是否满足类中Equals和GetHashCode方法的约定。 文档待定。 同时,您可以访问上的文档这真是太棒了!!!捐款我通过和接受提示。
网上有C#共享内存类,不过功能太简单了,并且写内存每次都从开头写。故对此进行了改进,并做了个小例子,供需要的人参考。 主要改进点: 通过利用共享内存的一部分空间(以下称为“数据信息区”)来存储当前内存中...
=/ToString/Prase/Equals/GetHashCode),定义了7种不同的构造函数,甚至可以 用"KeyEventArgs"做为参数进行构造,使得系统可以响应用户随时的Hotkey定义! Delegate:HotkeyHandler--用于热键响应的委托,其中传入参数为...
在您的类中添加或删除字段时,不再忘记更新您的哈希码方法! 该框架运行时生成的代码与手工编码的实现一样快。 有时甚至更快,因为我们使用了一些优化技巧。 您将自动确保遵循最佳实践- 例如在“未检查”块内进行...
测试listBox1.Items.Remove是用ToString还是利用gethashCode来定位元素的