GetHashCode方法与=

need to use this2a function scenario,可能是Distinct,可能是Dictionary,都是和HashTable有关,So it is necessary to introduce the hash table first.

哈希表

哈希表是一种数据结构,又叫散列表.This data structure has2部分组成：

• 动态数组,That is, one column to the left0-15,Each element is calledbucket
• 每个bucket,Corresponds to a singly linked list,May be an empty linked list

Newly inserted elements are passed through a hash function（Commonly used is the remainder method）,对应到每一个bucket中,Then insert it at the end of the linked list.

GetHashCode

In fact, it is the implementation of the hash function,The return value is the hash code,

equals

找到了bucket之后,Will judge again whether or notbucketThe existing elements in are equal,若不相等,则插入.

执行顺序：

• 先执行GetHashCode用于快速判断,
  • 若没有相同的hashcode,put in a new onebucket,无需执行equals
  • 若有相同的hashcode,put the samehashcode对应的bucket,再执行equals
    • 若equals返回true,即相等,则不放入（去重的时候,就认为2个元素相同）
    • 若equals返回false,即不相等,则放入

Distinct

情况1

	public class Point
    {
        public double X { get; set; }
        public double Y { get; set; }
        public double Z { get; set; }

        public Point(double x, double y, double z)
        {
            X= x;
            Y= y;
            Z= z;
        }

        public override bool Equals(object obj)
        {
            var result = base.Equals(obj);
            return result;
        }

        public override int GetHashCode()
        {
            int result = base.GetHashCode();
            return result;
        }
    }

Point p0 = new Point(1.0001, 2.0001, 3.0001);
Point p1 = new Point(1, 2, 3);
Point p2 = new Point(1, 2, 3);
var points = new List<Point> { p0, p1, p2 };
var newPoints = points.Distinct().ToList();

执行了Distinct去重函数,会自动调用Point自身的GetHashCode和Equals,本例中,What we implement is default overloading,

• GetHashCode,对于引用类型,返回的是对象的地址,So as long as it's not the same object,must return differenthashcode,So in local,GetHashCode对于p0、p1、p2返回3个不同的值,So no need to do it anymoreequals的验证.

因此DistinctThe result contains p0、p1、p2共3个点

情况2

我们来修改一下GetHashCode和Equals,That is, whether it is the same object or not,Let's just comparePointInstances of the type are not close together,if within the given range,considered to be the same point

 	public class Point
    {
        public double X { get; set; }
        public double Y { get; set; }
        public double Z { get; set; }

        public Point(double x, double y, double z)
        {
            X= x;
            Y= y;
            Z= z;
        }

        public override bool Equals(object obj)
        {
            var other = obj as Point;
            return Math.Abs(X-other.X)<0.01&& 
                Math.Abs(Y - other.Y) < 0.01 && 
                Math.Abs(Z - other.Z) < 0.01 ;
        }

        public override int GetHashCode()
        {
            return 1;
        }
    }

Point p0 = new Point(1.0001, 2.0001, 3.0001);
Point p1 = new Point(1, 2, 3);
Point p2 = new Point(1, 2, 3);
var points = new List<Point> { p0, p1, p2 };
var newPoints = points.Distinct().ToList();

Distinct执行过程：

• 插入p0点,并计算其hashcode,放入某一个bucket,p0为该bucketThe first element in the linked list in
• 插入p1点,并计算其hashcode,发现与p0相同,放入p0所在的bucket,再执行equals,发现与p0相同,丢弃
• 插入p2点,并计算其hashcode,发现与p0相同,放入p0所在的bucket,再执行equals,发现与p0相同,丢弃

因此DistinctThe result contains p0共1个点

情况3

		public override bool Equals(object obj)
        {
            var other = obj as Point;
            return X == other.X &&
                Y == other.Y &&
                Z == other.Z;
        }

        public override int GetHashCode()
        {
            return 1;
        }

Distinct执行过程：

• 插入p0点,并计算其hashcode,放入某一个bucket,p0为该bucketThe first element in the linked list in
• 插入p1点,并计算其hashcode,发现与p0相同,放入p0所在的bucket,再执行equals,发现与p0不同,挂在p0后面,At this time there is a linked list2个元素
• 插入p2点,并计算其hashcode,发现与p0相同,放入p0所在的bucket,再执行equals,发现与p0不同,但是与p1相同,丢弃

因此DistinctThe result contains p0、p1共2个点.

小结

不同的场景,不同的实现.But if you are lazyGetHashCode返回同样的值,最终通过equal去判断,Although the desired effect can be achieved,但是同一个bucketThere are too many elements in the final hanging,The lookup of the linked list is also very slow...所以最好在GetHashCodeIt also needs to be rewritten accordingly,Try to be in the first step,You can put different elements in different placesbucket中.

HashSet和Dictionary

Point p0 = new Point(1.0001, 2.0001, 3.0001);
Point p1 = new Point(1, 2, 3);
Point p2 = new Point(1, 2, 3);
HashSet<Point> set = new HashSet<Point>();
set.Add(p0);
set.Add(p1);
set.Add(p2);
Dictionary<Point, string> keyValuePairs = new Dictionary<Point, string>();
keyValuePairs.Add(p0, "0");
keyValuePairs.Add(p1, "1");
keyValuePairs.Add(p2, "2");

Calling method and sequence sumDistinct一模一样.

IEqualityComparer

上面是把2个函数的实现,放在Point内部进行的.Sometimes what we get is provided by someone elseAPI,No permission to modify it,How to rewrite it？

可以实现一个IEqualityComparer：

 	public class PointComparer : IEqualityComparer<Point>
    {
        public bool Equals(Point x, Point y)
        {
            return Math.Abs(x.X-y.X)<0.000001&& Math.Abs(x.Y - y.Y) < 0.01&&Math.Abs(x.Z - y.Z) < 0.01;
        }

        public int GetHashCode(Point obj)
        {
            return 1;
        }
    }

这样子,在调用Distinct的时候,You can specify the comparator manually：

var newPoints = points.Distinct(new PointComparer()).ToList();
var set = new HashSet<Point>(new PointComparer());
var keyValuePairs = new Dictionary<Point, string>(new PointComparer());

C++STL中的相应容器

c#	c++	底层数据结构
Dictionary	unorder_map	hashtable
HashSet	unorder_set	hashtable
SortedDictionary（没用过）	map/set	rb_tree

A hash table versus a red-black tree：

相对散列表,The binary search tree doesn't seem to have any advantages,那我们为什么还要用二叉查找树呢？

第一,散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序.而对于二叉查找树来说,我们只需要中序遍历,就可以在 O(n) 的时间复杂度内,输出有序的数据序列.

第二,散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在 O(logn).
比如：红黑树的插入、删除、查找各种操作性能都比较稳定.对于工程应用来说,要面对各种异常情况,为了支撑这种工业级的应用,我们更倾向于这种Balanced binary search tree with stable performance

第三,笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快.加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高.

第四,散列表的构造比二叉查找树要复杂,需要考虑的东西很多.比如散列函数的设计、冲突解决办法、扩容、缩容等.平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定.

Balanced binary search tree with stable performance

第三,笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快.加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高.

第四,散列表的构造比二叉查找树要复杂,需要考虑的东西很多.比如散列函数的设计、冲突解决办法、扩容、缩容等.平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定.