返回

一道 HashSet 面试题引发的蝴蝶效应

没错,我又借着“面试题”的名头来搞事情了,今天要说的是 HashSet ,而这确实是一个实际面试中遇到的问题。当时的场景大概是这样的,面试官在了解了你的知识广度以后,决心来考察一番你的基本功底,抛出了一个看起来平平无奇的问题:说一说你平时工作中都用到了哪些数据结构。你心想,这还不简单,ArrayArrayListListDictionaryHashSetStackQueue…等等各种集合类简直如数家珍,甚至你还能说出这些数据结构间的优劣以及各自使用的场景。可没想到,面试官话锋一转,直接来一句,“你能说说 HashSet 去重的原理吗”,好家伙,你这简直不按套路出牌啊…本着每次面试都有一点收获的初心,于是就有了今天这篇博客,不同的是,顺着这个思路继续深挖下去,博主又发现了几个平时关注不到的技术盲点,所以,博主称之为:一道 HashSet 面试题引发的蝴蝶效应。

HashSet 源代码解读

OK,首先,我们来回答第一个问题,即:HashSet 去重的原理是什么?。为此,博主翻阅了 HashSet 的 源代码。首先,我们会注意到 HashSet 的构造函数,它需要一个类型为IEqualityComparer<T>的参数。从这个命名上我们就可以知道,这是一个用于相等性比较的接口,我们初步推测,HashSet 去重应该和这个接口有关:

 1    public HashSet()
 2        : this(EqualityComparer<T>.Default) { }
 3 
 4    public HashSet(int capacity)
 5        : this(capacity, EqualityComparer<T>.Default) { }
 6 
 7    public HashSet(IEqualityComparer<T> comparer) { }
 8 
 9    public HashSet(IEnumerable<T> collection)
10        : this(collection, EqualityComparer<T>.Default) { }
11
12    public HashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
13        : this(comparer) { }

我们都知道 HashSet 可以去重,比如,我们向 HashSet 添加多个相同的元素,实际上 HashSet 中最终只会有一个元素。所以,我们自然而然地想到,看看 HashSet 中的 Add() 方法呗,或许能从这里看出一点端倪。HashSet 中一共有两个 Add() 方法,它们内部都调用了 AddIfNotPresent() 方法:

1void ICollection<T>.Add(T item) {
2    AddIfNotPresent(item);
3}
4
5 public bool Add(T item) {
6    return AddIfNotPresent(item);
7}

继续循着蛛丝马迹一路 F12 ,我们来看看这个方法的具体实现:

 1private bool AddIfNotPresent(T value) {
 2    if (m_buckets == null) {
 3        Initialize(0);
 4    }
 5 
 6    int hashCode = InternalGetHashCode(value);
 7    int bucket = hashCode % m_buckets.Length;
 8    #if FEATURE_RANDOMIZED_STRING_HASHING && !FEATURE_NETCORE
 9        int collisionCount = 0;
10    #endif
11    for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
12        if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, value)) {
13            return false;
14        }
15        #if FEATURE_RANDOMIZED_STRING_HASHING && !FEATURE_NETCORE
16            collisionCount++;
17        #endif
18    }
19 
20    int index;
21    if (m_freeList >= 0) {
22        index = m_freeList;
23        m_freeList = m_slots[index].next;
24    }
25    else {
26        if (m_lastIndex == m_slots.Length) {
27            IncreaseCapacity();
28            // this will change during resize
29            bucket = hashCode % m_buckets.Length;
30        }
31        index = m_lastIndex;
32        m_lastIndex++;
33    }
34    m_slots[index].hashCode = hashCode;
35    m_slots[index].value = value;
36    m_slots[index].next = m_buckets[bucket] - 1;
37    m_buckets[bucket] = index + 1;
38    m_count++;
39    m_version++;
40 
41    #if FEATURE_RANDOMIZED_STRING_HASHING && !FEATURE_NETCORE
42        if (collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(m_comparer)) {
43            m_comparer = (IEqualityComparer<T>) HashHelpers.GetRandomizedEqualityComparer(m_comparer);
44            SetCapacity(m_buckets.Length, true);
45        }
46    #endif // FEATURE_RANDOMIZED_STRING_HASHING
47 
48    return true;
49}

可以注意到,在这段代码中,首先,会通过 InternalGetHashCode() 方法计算一个 HashCode。其中,Lower31BitMask 是一个常量 0x7FFFFFFF

1private int InternalGetHashCode(T item) {
2    if (item == null) {
3        return 0;
4    } 
5    return m_comparer.GetHashCode(item) & Lower31BitMask;
6}

接下来,在 HashSet 内部使用了Slot 这个结构来存储元素,该结构设计上类似于链表,每一个 Slot 中都记录对应元素的值、HashCode 以及下一个元素的索引。所以,只需要对它做一次遍历,如果对应元素的 HashCode 和 值 都相等,则认为该元素在 HashSet中已经存在了。此时,AddIfNotPresent() 方法会返回 false。这就是 HashSet 去重的原理啦。在比较元素的值是否相等的时候,我们前面提到的 IEqualityComparer<T> 终于登场,它提供的 Equals() 方法恰好可以比较两个元素是否相等:

 1internal struct Slot {
 2    internal int hashCode;  // Lower 31 bits of hash code, -1 if unused
 3    internal int next;  // Index of next entry, -1 if last
 4    internal T value;
 5}
 6
 7public interface IEqualityComparer<in T>
 8{
 9    bool Equals(T x, T y);
10    int GetHashCode(T obj);                
11}

再接下来,如果对应元素的 HashCode 或 值 都不相等,则认为该元素在 HashSet 中不存在。此时,需要考虑 HashSet 的容量是否足以放得下这个新元素。在容量不满足的情况下,就需要对 HashSet 进行扩容。值得一提的是,这里是使用质数进行扩容的:

 1private void IncreaseCapacity() {
 2    Debug.Assert(m_buckets != null, "IncreaseCapacity called on a set with no elements");
 3 
 4    int newSize = HashHelpers.ExpandPrime(m_count);
 5    if (newSize <= m_count) {
 6        throw new ArgumentException(SR.GetString(SR.Arg_HSCapacityOverflow));
 7    }
 8 
 9    // Able to increase capacity; copy elements to larger array and rehash
10    SetCapacity(newSize, false);
11}
12
13public static int ExpandPrime(int oldSize)
14{
15    int newSize = 2 * oldSize;
16 
17    // Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow.
18    // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
19    if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
20    {
21        Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
22        return MaxPrimeArrayLength;
23    }
24 
25    return GetPrime(newSize);
26}

IEqualityComparer接口

OK,现在我们知道了,HashSet 之所以可以去重,一个重要的原因是 IEqualityComparer<T> 。而回到这个接口本身呢,它只有 Equals()GetHashCode(),这其实非常符合我们的认知,因为这两个方法在对象相等的场景中十分常见,有一个准则是:如果重写了 Equals() 方法,那么,应该同时去重写 GetHashCode() 方法,即,两者在表达相等这个含义时应该具有一致性。这里可能会有一点疑问,那就是,我们平时使用 HashSet 的时候,完全不需要指定 IEqualityComparer<T> ,它一样可以正常工作啊?没错,这是因为微软提供了一个默认的实现:EqualityComparer<T>.Default。我们同样来看看它的实现:

 1private static EqualityComparer<T> CreateComparer() {
 2    Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null);
 3 
 4    RuntimeType t = (RuntimeType)typeof(T);
 5    // Specialize type byte for performance reasons
 6    if (t == typeof(byte)) {
 7        return (EqualityComparer<T>)(object)(new ByteEqualityComparer());
 8    }
 9    // If T implements IEquatable<T> return a GenericEqualityComparer<T>
10    if (typeof(IEquatable<T>).IsAssignableFrom(t)) {
11        return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), t);
12    }
13    // If T is a Nullable<U> where U implements IEquatable<U> return a NullableEqualityComparer<U>
14    if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
15        RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
16        if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) {
17            return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), u);
18        }
19    }
20            
21    // See the METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST and METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST_LONG cases in getILIntrinsicImplementation
22    if (t.IsEnum) {
23        TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(t));
24 
25        // Depending on the enum type, we need to special case the comparers so that we avoid boxing
26        // Note: We have different comparers for Short and SByte because for those types we need to make sure we call GetHashCode on the actual underlying type as the 
27        // implementation of GetHashCode is more complex than for the other types.
28        switch (underlyingTypeCode) {
29            case TypeCode.Int16: // short
30               return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), t);
31            case TypeCode.SByte:
32                return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), t);
33            case TypeCode.Int32:
34            case TypeCode.UInt32:
35            case TypeCode.Byte:
36            case TypeCode.UInt16: //ushort
37                return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), t);
38            case TypeCode.Int64:
39            case TypeCode.UInt64:
40                return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), t);
41        }
42    }
43    // Otherwise return an ObjectEqualityComparer<T>
44    return new ObjectEqualityComparer<T>();
45}

在这里,EqualityComparer<T> 类是一个抽象类,实现了 IEqualityComparer<T> 接口。简单来说,对于简单类型如整型、字节型等,微软实现了相应的 IEqualityComparer<T> 接口;而对于复杂的类型,微软提供了 ObjectEqualityComparer<T> 这一实现:

 1internal class ObjectEqualityComparer<T>: EqualityComparer<T>
 2{
 3    [Pure]
 4    public override bool Equals(T x, T y) {
 5        if (x != null) {
 6            if (y != null) return x.Equals(y);
 7            return false;
 8        }
 9        if (y != null) return false;
10        return true;
11    }
12 
13    [Pure]
14    public override int GetHashCode(T obj) {
15        if (obj == null) return 0;
16        return obj.GetHashCode();
17    }
18}

所以,现在又回到我们刚刚聊起的话题,为什么说一个类型的 Equals()GetHashCode() 方法非常重要呢?因为如果我们不能正确地实现这两个方法,微软实现的这个 ObjectEqualityComparer<T> 就会出现问题,导致 HashSet 在判断元素是否存在时出现问题,所以,这是一系列的连锁反应。有人可能会问,博主你说的这个好夸张耶,像我就从来没有重写过这两个方法。OK,现在来回答我的一个问题,如果你定义了一个类型 Foo ,并尝试用它作为一个字典中的 Key ,那么,你觉得这个字典应该怎么判断这个 Key 是否存在呢?我觉得这是一个好问题,因为它引发了我们在 .NET 知识体系中的蝴蝶效应。

排序与去重是亲家

排序与去重,在我看来是亲家关系,因为两者都需要“比较”。所以,下面我想从 .NET 中选取一部分接口来阐述我的观点,以及当我们有了 LINQ 以后,是否就应该抛弃它们。可能这些接口大家平时都用不到多少,但我还是想花点时间来梳理这些知识盲点,因为我发现,与其为整个行业 35 岁的的职业生涯而焦虑,倒不如重新捡起这个行业的初心,好好地学一学数据结构、算法和数学。整个行业的火热,容易让每一个人都陷入一种“我非常厉害”的错觉,我写博客的时候,在心里想了这样一句话:战士上战场,整天就知道 CRUD,连 HashSet 都不知道,早晚是个死。用王布斯的口吻说出来,会不会有一种紧迫感呢?

IEquatable接口

IEquatable<T> 接口在微软官方文档中的定义是,定义值类型或类实现的通用方法,以创建用于确定实例相等性的类型特定方法。我承认,这不是一个特别好的定义,不过,我们可以换个角度来审视这个接口存在的意义。虽然 Object 这个基类提供了 Equals() 方法,但是这个方法只能接受一个 object 类型的参数, 所以,它本身会面临类型安全性缺失装箱两个问题。为了解决这个问题,就必须要定义一个新的 Equals() 方法,确保它可以接收和当前类型一致的参数,所以就需要这样一个接口,你可以理解为它是 Equals() 方法的泛型版本,而众所周知 C# 是一门不支持多继承的语言,所以,这里只能以接口的形式提供出来。这里说一下我的结论,IEquatable<T> 接口对值类型更有用一点,相反,对引用类型就没有那么有用,因为它没有考虑到协变的问题,对引用类型的继承相对无力。下面是一个简单的例子:

 1//定义类型Foo,实现IEquatable<Foo>接口
 2public class Foo : IEquatable<Foo>
 3{
 4    public decimal Value { get; set; }
 5    public decimal Weight { get; set; }
 6
 7    public override bool Equals(object other)
 8    {
 9        return Equals(other as Foo);
10    }
11
12    public bool Equals(Foo other)
13    {
14        if (other == null) return false;
15        return (this.Value == other.Value && this.Weight == other.Weight);
16    }
17}
18
19//平平无奇的代码
20var foo1 = new Foo() { Value = 10, Weight = 1.0M };
21var foo2 = new Foo() { Value = 10, Weight = 1.0M };
22Assert.AreEqual(true, foo1.Equals(foo2));

ICompareable/ICompareable接口

ICompareableICompareable<T>是是同一个接口的非泛型与泛型版本,都需要实现 CompareTo() 方法。可能大家会觉得这几个接口都差不多啊,实际上,大家细心观察就能发现它们的区别,“相等”这一类的接口的返回值是布尔型,关注的是两个对象是否相等;而“比较”这一类的接口的返回值是整数型,关注的是哪个大哪个小。我们继续以 Foo 这个类型为例,分别实现IComparerableIComparerable<T>两个接口:

 1//继续实现IComparable, IComparable<Foo>接口
 2public class Foo : IEquatable<Foo>, IComparable, IComparable<Foo>
 3{
 4    public decimal Value { get; set; }
 5    public decimal Weight { get; set; }
 6
 7    public override bool Equals(object other)
 8    {
 9        return Equals(other as Foo);
10    }
11
12    public bool Equals(Foo other)
13    {
14        if (other == null) return false;
15        return (this.Value == other.Value && this.Weight == other.Weight);
16    }
17
18    public int CompareTo(object obj)
19    {
20        var other = obj as Foo;
21        return CompareTo(other);
22    }
23
24    public int CompareTo([AllowNull] Foo other)
25    {
26        if (other == null) return 1;
27        return (int)((Value * Weight) - (other.Value * other.Weight));
28    }
29}
30
31//平平无奇的代码
32var foo1 = new Foo() { Value = 10, Weight = 1.0M };
33var foo2 = new Foo() { Value = 20, Weight = 1.0M };
34Assert.IsTrue(foo2.CompareTo(foo1) > 0);

IComparer接口

对于排序来说,理论上有ICompareableICompareable<T>这两个接口就可以了,为什么还要再定义一组接口呢?其实,我们结合生活中的场景就能想明白,不管是判断两个对象是否相等,还是对两个对象进行排序,这些条件都属于“变量”。ICompareableICompareable<T>这两个接口设计上的确没什么问题,但这都是一锤子买卖,一旦实现了对应的接口,就意味着如何比较两个对象的逻辑是确定好了的。可生活常识告诉我们,同一组信息不同的人考虑的维度是不一样的,譬如学生的成绩,可以按照某一个科目的成绩来排序,还可以按照各个科目的总成绩甚至是平均分来排序。对于上面的类型 Foo,我们不妨考虑按照 ValueWeight 分别进行排序,此时可以这样写:

 1//按Value排序
 2public class FooValueComparer : IComparer<Foo>
 3{
 4    public int Compare([AllowNull] Foo x, [AllowNull] Foo y)
 5    {
 6        if (x == null && y == null) return 0;
 7        if (x != null && y == null) return 1;
 8        if (x == null && y != null) return -1;
 9        return (int)(x.Value - y.Value);
10    }
11}
12
13//按Weight排序
14public class FooWeightComparer : IComparer<Foo>
15{
16    public int Compare([AllowNull] Foo x, [AllowNull] Foo y)
17    {
18        if (x == null && y == null) return 0;
19        if (x != null && y == null) return 1;
20        if (x == null && y != null) return -1;
21        return (int)(x.Weight - y.Weight);
22    }
23}
24
25//平平无奇的代码
26var list= new List<Foo>{
27    new Foo() { Value = 10, Weight = 2.0M },
28    new Foo() { Value = 10, Weight = 1.0M }
29};
30
31//使用默认的排序器
32list.Sort(); 
33
34//按Value进行排序
35list.Sort(new FooValueComparer());
36list.OrderBy(x => x.Value);
37
38//按Weight进行排序
39list.Sort(new FooWeightComparer());
40list.OrderBy(x => x.Weight);

在这里有一个点是,在不指定排序器的时候,微软帮我们提供了一个默认的排序器。而这个默认排序器会遵循这样的策略。如果类型 T 实现了 IComparable<T> 接口,则返回 GenericComparer<int> 实例;如果类型 T 实现是一个可空类型 Nullable<U> 并且类型 U 实现了 IComparable<T> 接口,则返回 NullableComparer<int> 实例;否则返回 ObjectComparer<T> 实例。

 1private static Comparer<T> CreateComparer() {
 2    RuntimeType t = (RuntimeType)typeof(T);
 3 
 4    // If T implements IComparable<T> return a GenericComparer<T>
 5    #if FEATURE_LEGACYNETCF
 6        // Pre-Apollo Windows Phone call the overload that sorts the keys, not values this achieves the same result
 7        if (CompatibilitySwitches.IsAppEarlierThanWindowsPhone8) {
 8            if (t.ImplementInterface(typeof(IComparable<T>))) {
 9                return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), t);
10            }
11        }
12        else
13    #endif
14    if (typeof(IComparable<T>).IsAssignableFrom(t)) {
15            return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), t);
16    }
17 
18    // If T is a Nullable<U> where U implements IComparable<U> return a NullableComparer<U>
19    if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
20        RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
21        if (typeof(IComparable<>).MakeGenericType(u).IsAssignableFrom(u)) {
22            return (Comparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), u);
23        }
24    }
25
26    // Otherwise return an ObjectComparer<T>
27    return new ObjectComparer<T>();
28}

更有意思的是,GenericComparer<T> 就是利用 IComparable<T>CompareTo() 方法来说实现的:

 1internal class GenericComparer<T> : Comparer<T> where T: IComparable<T>
 2{    
 3    public override int Compare(T x, T y) {
 4        if (x != null) {
 5            if (y != null) return x.CompareTo(y);
 6                return 1;
 7            }
 8        if (y != null) return -1;
 9        return 0;
10    }
11 
12    // Equals method for the comparer itself. 
13    public override bool Equals(Object obj){
14        GenericComparer<T> comparer = obj as GenericComparer<T>;
15        return comparer != null;
16    }        
17 
18    public override int GetHashCode() {
19        return this.GetType().Name.GetHashCode();
20    }
21}

在我们有了 LINQ 以后,通过 OrderByOrderByDescending 就可以进行排序,如果这个排序字段是一个简单类型,比如字符型、整型、日期型,这些简单类型微软都已经实现了相应的“排序”逻辑,而如果这个排序字段是一个复杂类型,比如一个自定义的类或者结构,此时,为了让这些方法能够“适应”这些复杂类型,最好的还是去实现 IComparer<T> 或者 ICompareable<T> 接口,然后传递给这两个排序方法。类似地,还有 Distinct 这个方法,它接收一个 IEqualityComparer<T> 类型的参数,所以,当你对一个列表进行去重(Distinct)操作时,千万不要想当然地人为它会按照你的期望去去重,如果结果不符合你的期望,很大原因是你没有给它提供一个合适的IEqualityComparer<T> 。所以,你看,我们绕了一大圈,从 HashSet 说到 IEqualityComparer<T>,又从排序说到去重,最终又回到了起点,这是多么有趣的一件事情。而去重(Distinct)这件事情,其实涉及到DictionaryHashSet 两个数据结构,通过结构来推演性质,又通过性质来扫清盲点,这可能是这段时间刷 LeetCode 最大的一个收获吧!

本文小结

面试中偶然遇到的 HashSet 问题,让我发现自己的知识体系中存在着盲点。通过解读 HashSet 源代码,我们认识到 HashSet 可以去重的一个重要原因是IEqualityComparer<T> 接口,它决定了两个对象的实例在什么情况下可以被判定为相等。而这个接口,不单单在 HashSet 出现,在 Dictionary 中同样会出现,甚至在我们最熟悉不过的去重(Distinct)中还会出现,所以,通过 HashSet 这一个点上的疑问,我搞清楚了很多相关联的内容,这不是蝴蝶效应又是什么呢?而与去重(Distinct)相关联的则是排序,在此基础上,对 IEquatable<T> 接口、ICompareable/ICompareable<T> 接口、IComparer<T> 接口等知识盲点进行梳理。总而言之,排序需要关注的是 ICompareable/ICompareable<T> 接口、IComparer<T> 接口,去重需要关注的是 IEqualityComparer<T> 接口。好了,今天的这只蝴蝶就飞到这里,欢迎大家在博客中留言,谢谢大家!

Built with Hugo
Theme Stack designed by Jimmy