今天在寫代碼的時候要對數據進行去重,正打算使用Distinct方法的時候,發現這個用了這麼久的東西,竟然不知道它是怎麼實現的,於是就有了這篇文章. 1.需求 假如我們有這樣一個類 還有這樣一組數據 我們要把集合中重覆的數據去掉,對的就這麼簡單個需求,工作中可不會有這麼簡單的需求. 2.在剛學編程的時 ...
今天在寫代碼的時候要對數據進行去重,正打算使用Distinct方法的時候,發現這個用了這麼久的東西,竟然不知道它是怎麼實現的,於是就有了這篇文章.
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.分析下去重的思路
圖用自帶畫圖畫的,難看還請見諒.
我後面回放代碼,一步一步調試可能會更容易理解.
1.假如我們第一個Model進行hash取餘得到的為0,此時_buckets[0]為0,所以不會進入for迴圈條件,直接進行下麵的賦值操作
_slots[0]=當前的元素 next=-1 hash=7
buckets[0]=1 指向當前元素索引+12.繼續下一個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 指向當前元素索引+16.結束
結束了,我們發現Distinct使用了hash進行去重,實現思路上感覺很值得我學習(我是寫不出來的..).
Distinct很依賴於比較器的GetHashCode方法,如果隨便返回一個固定值的話,會增加很大的開銷.不要為了偷懶再返回一個固定int值了.
希望這篇文章可以對大家有幫助 有啟發
代碼地址:https://git.coding.net/changyell/DistinctDemo.git
本人是個菜鳥,文章如果有錯誤的地方,煩請大佬們指正,謝謝...
