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();
        }

这时,我们再运行上面的方法就可以得到下面的结果:

You may also like...

Leave a Reply

Your email address will not be published.