欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

从对集合数据去重到Distinct源码分析

程序员文章站 2022-10-05 18:52:41
今天在写代码的时候要对数据进行去重,正打算使用Distinct方法的时候,发现这个用了这么久的东西,竟然不知道它是怎么实现的,于是就有了这篇文章. 1.需求 假如我们有这样一个类 还有这样一组数据 我们要把集合中重复的数据去掉,对的就这么简单个需求,工作中可不会有这么简单的需求. 2.在刚学编程的时 ......

今天在写代码的时候要对数据进行去重,正打算使用Distinct方法的时候,发现这个用了这么久的东西,竟然不知道它是怎么实现的,于是就有了这篇文章.
使用的.net core2.0

1.需求

假如我们有这样一个类

    public class Model
    {
        public int Code { get; set; }
        public int No { get; set; }
        public override string ToString()
        {
            return "No:" + No + ",Code:" + Code;
        }
    }

还有这样一组数据

        public static IEnumerable<Model> GetList()
        {
            return new List<Model>()
            {
                new Model(){No = 1,Code = 1},
                new Model(){No = 1,Code = 2},
                new Model(){No = 7,Code = 1},
                new Model(){No = 11,Code = 1},
                new Model(){No = 55,Code = 1},
                new Model(){No = 11,Code = 1},//重复
                new Model(){No = 6,Code = 7},
                new Model(){No = 1,Code = 1},
                new Model(){No = 6,Code = 7},//重复
            };
        }

我们要把集合中重复的数据去掉,对的就这么简单个需求,工作中可不会有这么简单的需求.

2.在刚学编程的时候我们可能这样写的

在很久以前一直使用这种简单粗暴的方法解决重复问题

        /// <summary>
        /// 双重循环去重
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        public static IEnumerable<Model> MyDistinct(IEnumerable<Model> list)
        {
            var result = new List<Model>();
            foreach (var item in list)
            {
                //标记
                var flag = true;
                foreach (var item2 in result)
                {
                    //已经存在的标记为false
                    if (item2.Code == item.Code && item2.No == item.No)
                    {
                        flag = false;
                    }
                }

                if (flag)
                {
                    result.Add(item);
                }
            }

            return result;
        }

3.后来认识了Distinct

后来知道了Distinct去重,我们写法变成了这样

   /// <summary>
    /// 比较器
    /// </summary>
    public class ModelEquality : IEqualityComparer<Model>
    {
        public bool Equals(Model x, Model y)
        {
            return x.No == y.No && x.Code == y.Code;
        }

        public int GetHashCode(Model obj)
        {
            return obj.No.GetHashCode() + obj.Code.GetHashCode();
        }
    }
//这样就可以得到去重后的集合
GetList().Distinct(new ModelEquality());

4.探究Distinct源码

我们去github找一下源码,微软开源的仓库地址:https://github.com/dotnet/corefx
为了篇幅我删掉了一些不相关的一些代码

namespace System.Linq
{
    public static partial class Enumerable
    {
        public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source) => Distinct(source, null);

        public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
        {
            if (source == null)
            {
                throw Error.ArgumentNull(nameof(source));
            }

            return new DistinctIterator<TSource>(source, comparer);
        }
        private sealed class DistinctIterator<TSource> : Iterator<TSource>, IIListProvider<TSource>
        {
            private readonly IEnumerable<TSource> _source;
            private readonly IEqualityComparer<TSource> _comparer;
            private Set<TSource> _set;
            private IEnumerator<TSource> _enumerator;

            public DistinctIterator(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
            {
                _source = source;
                _comparer = comparer;
            }

            public override bool MoveNext()
            {
                switch (_state)
                {
                    case 1:
                        _enumerator = _source.GetEnumerator();
                        if (!_enumerator.MoveNext())
                        {
                            Dispose();
                            return false;
                        }

                        TSource element = _enumerator.Current;
                        _set = new Set<TSource>(_comparer);
                        _set.Add(element);
                        _current = element;
                        _state = 2;
                        return true;
                    case 2:
                        while (_enumerator.MoveNext())
                        {
                            element = _enumerator.Current;
                            if (_set.Add(element))
                            {
                                _current = element;
                                return true;
                            }
                        }
                        break;
                }

                Dispose();
                return false;
            }

            public override void Dispose()
            {
                //省略...
            }
        }
    }
}

Iterator<TSource>是一个抽象类实现了Iterator<TSource> : IEnumerable<TSource>, IEnumerator<TSource>
我们主要看DistinctIterator类中的代码,发现有这么一个私有成员Set<TSource> _set;,我们再看MoveNext方法中有这么一段

                            element = _enumerator.Current;
                            if (_set.Add(element))
                            {
                                _current = element;
                                return true;
                            }

到这里我似乎明白了什么,回忆下Set集合的特点"无序","不可重复",再看代码中只有对set Add成功才对_current赋值,return true.那么这个Set应该就是内部维护的一个集合,也就是我们要的去重后的数据,那么Set里的Add方法就是关键
同样去掉了一些没有用到的,加了注释

namespace System.Linq
{
    /// <summary>
    /// A lightweight hash set.
    ///一个 轻量级hash set
    /// </summary>
    /// <typeparam name="TElement">The type of the set's items.</typeparam>
    internal sealed class Set<TElement>
    {
        /// <summary>
        /// The comparer used to hash and compare items in the set.
        /// </summary>
        private readonly IEqualityComparer<TElement> _comparer;

        /// <summary>
        /// The hash buckets, which are used to index into the slots.
        /// hash环,每一个指向了下面Slot中的index
        /// </summary>
        private int[] _buckets;

        /// <summary>
        /// The slots, each of which store an item and its hash code.
        /// 数组的每一个储存了他们自身和自己的hash
        /// </summary>
        private Slot[] _slots;

        /// <summary>
        /// The number of items in this set.
        /// </summary>
        private int _count;

        /// <summary>
        /// Constructs a set that compares items with the specified comparer.
        /// </summary>
        /// <param name="comparer">
        /// The comparer. If this is <c>null</c>, it defaults to <see cref="EqualityComparer{TElement}.Default"/>.
        /// </param>
        public Set(IEqualityComparer<TElement> comparer)
        {
            _comparer = comparer ?? EqualityComparer<TElement>.Default;
            //初始化长度7
            _buckets = new int[7];
            //初始化长度7
            _slots = new Slot[7];
        }

        /// <summary>
        /// Attempts to add an item to this set.
        /// 我们要看的方法
        /// </summary>
        /// <param name="value">The item to add.</param>
        /// <returns>
        /// <c>true</c> if the item was not in the set; otherwise, <c>false</c>.
        /// </returns>
        public bool Add(TElement value)
        {
            //取的当前项的hash
            int hashCode = InternalGetHashCode(value);
            //重复的hashCode的话,  _buckets[hashCode % _buckets.Length] - 1的值就不会是-1
            //就会进入下面的if判断
            //
            for (int i = _buckets[hashCode % _buckets.Length] - 1; i >= 0; i = _slots[i]._next)
            {
                //如果存在重复就会直接返回false,没有的话i会变为_next所指向的hash相等的元素,减少了循环次数,类似链表
                if (_slots[i]._hashCode == hashCode && _comparer.Equals(_slots[i]._value, value))
                {
                    return false;
                }
            }
            //Slot数量满了后
            if (_count == _slots.Length)
            {
                //对数组进行扩容
                Resize();
            }
            //元素要添加进_slots的下标位置
            int index = _count;
            //对数量进行增加
            _count++;
            //对当前项的hash 取余
            int bucket = hashCode % _buckets.Length;
            //赋值
            _slots[index]._hashCode = hashCode;
            _slots[index]._value = value;
            //当hash第一次出现的时候值为-1,重复出现的时候为上一个出现重复bucket值存放在slots中的索引,-1是因为下一行+1了
            _slots[index]._next = _buckets[bucket] - 1;
            //指向当前元素索引+1 出现重复的bucket值则会覆盖旧的bucket位置的值
            _buckets[bucket] = index + 1;
            return true;
        }
        /// <summary>
        /// Expands the capacity of this set to double the current capacity, plus one.
        /// 对set扩容
        /// </summary>
        private void Resize()
        {
            int newSize = checked((_count * 2) + 1);
            int[] newBuckets = new int[newSize];
            Slot[] newSlots = new Slot[newSize];
            Array.Copy(_slots, 0, newSlots, 0, _count);
            for (int i = 0; i < _count; i++)
            {
                int bucket = newSlots[i]._hashCode % newSize;
                newSlots[i]._next = newBuckets[bucket] - 1;
                newBuckets[bucket] = i + 1;
            }

            _buckets = newBuckets;
            _slots = newSlots;
        }

        /// <summary>
        /// The number of items in this set.
        /// </summary>
        public int Count => _count;

        /// <summary>
        /// Gets the hash code of the provided value with its sign bit zeroed out, so that modulo has a positive result.
        /// </summary>
        /// <param name="value">The value to hash.</param>
        /// <returns>The lower 31 bits of the value's hash code.</returns>
        private int InternalGetHashCode(TElement value) => value == null ? 0 : _comparer.GetHashCode(value) & 0x7FFFFFFF;

        /// <summary>
        /// An entry in the hash set.
        /// </summary>
        private struct Slot
        {
            /// <summary>
            /// The hash code of the item.
            /// hash值
            /// </summary>
            internal int _hashCode;

            /// <summary>
            /// In the case of a hash collision, the index of the next slot to probe.
            /// 下一个用于检查的元素index
            /// </summary>
            internal int _next;

            /// <summary>
            /// The item held by this slot.
            /// </summary>
            internal TElement _value;
        }
    }
}

5.分析下去重的思路

图用自带画图画的,难看还请见谅.
从对集合数据去重到Distinct源码分析
我后面回放代码,一步一步调试可能会更容易理解.
1.假如我们第一个Model进行hash取余得到的为0,此时_buckets[0]为0,所以不会进入for循环条件,直接进行下面的赋值操作

_slots[0]=当前的元素 next=-1 hash=7
buckets[0]=1 指向当前元素索引+1

2.继续下一个Model进行hash取余,假如又为0,buckets[0]-1为0,满足循环条件,进入判断,取到_slots[0]的值,进行比较,发现相等的话则会直接返回.
3.继续上面的步骤,这次hash取余为3,没出现过,

_slots[1]=当前的元素 next=-1 hash=10
buckets[2]=2 指向当前元素索引+1

.........
4.这个时候又出现了一次hash取余为3,进入判断中,取到_slots[1]的值,进行比较发现不相等,next为-1不会有下一次循环,

_slots[3]=当前的元素 next=1 hash=10
buckets[2]=4 指向当前元素索引+1

注意此时next不是-1了,而是1,也就是上一个相同hash取余的元素在_slots中的位置,此时形成了一个链表.这样少了很多的比较次数.
5.这个时候又出现了一个hash取余为3的,进入判断中,取到_slots[3]的值,进行比较发现不相等,next为1,则再次与_slots[1]的元素进行比较,如果发现相等的舍弃,反之最后加入到set中
假如不相同,则:

_slots[4]=当前的元素 next=3 hash=10
buckets[2]=5 指向当前元素索引+1

6.结束

结束了,我们发现Distinct使用了hash进行去重,实现思路上感觉很值得我学习(我是写不出来的..).
Distinct很依赖于比较器的GetHashCode方法,如果随便返回一个固定值的话,会增加很大的开销.不要为了偷懒再返回一个固定int值了.
希望这篇文章可以对大家有帮助 有启发

代码地址:https://git.coding.net/changyell/DistinctDemo.git

本人是个菜鸟,文章如果有错误的地方,烦请大佬们指正,谢谢...