C#中的GetHashCode
所谓的hash code其实主要用在一些基于hash的集合中,比如Dictionary<TKey,Tvalue>等等。一般来说,假如两个对象是相等的,那么他们的hash值也是相等的,但是反之,则不一定,也就是说两个hash值相等的对象,他们不一定相等。
需要注意的是.NET的默认的GetHashCode是不保证一定相等的,在不同的.NET版本,不同的平台上面,返回的值都有可能不同。所以,不要使用默认的这个函数来作为唯一的判断。所以,有这两点需要注意:
- 同样的hash值不表示他们对象是相等的。
- 不要把hash值保存下来,或者在不同的应用之间传递,然后使用这个值来进行判断,因为脱离了这个应用,即使同样的对象,他的hash值也是可能不同的,这和平台,进程等等都有关系。
GetHashCode可以被子类override,换句话说,假如你不override这个函数,那么就会默认使用父类(object)的GetHashCode函数。他的计算是基于对象的引用来计算的,也就是说两个对象只要他们的引用一样,那么他们默认的GetHashCode的值也是一样的。
假如你override了GetHashCode,那么你也需要同样override Equal函数的实现,反过来也是,就是说你ovverride了Equal的实现,那么你也需要override他们GetHashCode的实现,这样他们能够返回同样的值。
下面我们来看一些例子:
public struct Point { private int x; private int y; public Point(int x, int y) { this.x = x; this.y = y; } public override bool Equals(object obj) { if (!(obj is Point)) return false; Point p = (Point)obj; return x == p.x & y == p.y; } public override int GetHashCode() { return x ^ y; } }
这是一个简单的Point的结构,我们重写了GetHashCode的方法,这样,我们就可以看到他的HashCode使用想x^y来计算的,这个可以简单保证当x,y相等的时候,他们的hashcode是相等的。
我们在main函数中调用这个函数,可以看到下面这行代码的输出就是13.
Point p = new Point(5, 8); Console.WriteLine(p.GetHashCode());
但是这里有一个最大的问题,即使(x,y)和(y,x)的hash值其实是一样的,虽然说我们一般不能保证hash值相同,对象就相同,但是我们上面的实现重复值也太多了。所以这种情况,我们一般会使用Tuple<T1,T2>来重新计算。
private int x; private int y; public Point(int x, int y) { this.x = x; this.y = y; } public override bool Equals(object obj) { if (!(obj is Point)) return false; Point p = (Point)obj; return x == p.x & y == p.y; } public override int GetHashCode() { return Tuple.Create(x,y).GetHashCode(); }
这时,我们在main中来带调用这两个看看:
Point p = new Point(5, 8); Console.WriteLine(p.GetHashCode()); Point pt = new Point(8, 5); Console.WriteLine(pt.GetHashCode());
这样一来,我们会发现调换x和y之后,他们的hash值相差还是蛮多的:
除了这种Tuple的实现,另外一种常用的方法就是使用移位法,也就是会把每一个元素通过移位附上不同的权重,一般来说我们会使用循环移位,就是超出31bit的位再加到末尾:
public int ShiftAndWrap(int value, int positions) { positions = positions & 0x1F; // Save the existing bit pattern, but interpret it as an unsigned integer. uint number = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0); // Preserve the bits to be discarded. uint wrapped = number >> (32 - positions); // Shift and wrap the discarded bits. return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) | wrapped), 0); }
有了这个方法,我们就可以把上面计算hashcode的函数改成下面这样了:
public override int GetHashCode() { return ShiftAndWrap(x.GetHashCode(), 2) ^ y.GetHashCode(); }
这时,我们再运行上面的方法就可以得到下面的结果:
Recent Comments