DotNet源碼學習-HASHSET（初探）

命名空間：System.Collections.Generic 先看一下官方說明：類提供了高級的設置操作。集是不包含重覆元素的集合，其元素無特定順序。 HashSet <T>對象的容量是對象可以容納的元素數。當向對象添加元素時，HashSet <T>對象的容量會自動增加。 HashSet<Strin ...

命名空間：System.Collections.Generic

先看一下官方說明：類提供了高級的設置操作。集是不包含重覆元素的集合，其元素無特定順序。

HashSet <T>對象的容量是對象可以容納的元素數。當向對象添加元素時，HashSet <T>對象的容量會自動增加。

HashSet<String> hashSet = new HashSet<string>();
hashSet.Add("test");
hashSet.Add("test");
Console.WriteLine(hashSet.Count);

列印結果：1

HashSet的預設構造方法：

public HashSet()
            : this((IEqualityComparer<T>?)null)
        { }

註：: this語法為調用自身對象的其他構造方法。

public HashSet(IEqualityComparer<T>? comparer)
{
     if (comparer == EqualityComparer<T>.Default)
     {
          comparer = null;
     }
     _comparer = comparer;
     _lastIndex = 0;
     _count = 0;
     _freeList = -1;
     _version = 0;
}

第二中創建方式，將集合作為參數。

List<string> list = new List<string>();
list.Add("test");
list.Add("test");
HashSet<string> hSet = new HashSet<string>(list);
Console.WriteLine(hSet.Count);

此時控台輸出：1

此時調用的構造方法為：

public HashSet(IEnumerable<T> collection, IEqualityComparer<T>? comparer)
            : this(comparer)
{
    if (collection == null)
    {
        throw new ArgumentNullException(nameof(collection));
    }
    var otherAsHashSet = collection as HashSet<T>;
    if (otherAsHashSet != null && AreEqualityComparersEqual(this, otherAsHashSet))
    {
        CopyFrom(otherAsHashSet);
    }
    else
    {
        // to avoid excess resizes, first set size based on collection's count. Collection
        // may contain duplicates, so call TrimExcess if resulting hashset is larger than
        // threshold
        ICollection<T>? coll = collection as ICollection<T>;
        int suggestedCapacity = coll == null ? 0 : coll.Count;
        Initialize(suggestedCapacity);
        UnionWith(collection);
        if (_count > 0 && _slots.Length / _count > ShrinkThreshold)
        {
            TrimExcess();
        }
    }
}

在該構造方法中若存在重覆值則通過查找大於或等於容量的下一個質數來使用建議的容量。

private int Initialize(int capacity)
{
    Debug.Assert(_buckets == null, "Initialize was called but _buckets was non-null");
    int size = HashHelpers.GetPrime(capacity);
    _buckets = new int[size];
    _slots = new Slot[size];
    return size;
}

下麵為生成質數方法：

public static int GetPrime(int min)
{
    if (min < 0)
        throw new ArgumentException(SR.Arg_HTCapacityOverflow);
    foreach (int prime in s_primes)
    {
        if (prime >= min)
            return prime;
    }
    // Outside of our predefined table. Compute the hard way.
    for (int i = (min | 1); i < int.MaxValue; i += 2)
    {
        if (IsPrime(i) && ((i - 1) % HashPrime != 0))
            return i;
    }
    return min;
}

再次擴展-》

public static bool IsPrime(int candidate)
{
  if ((candidate & 1) != 0)
  {
    int limit = (int)Math.Sqrt(candidate);//取平方
    for (int divisor = 3; divisor <= limit; divisor += 2)
    {
      if ((candidate % divisor) == 0)
        return false;
    }
    return true;
  }
  return candidate == 2;
}

internal struct Slot
{
  internal int hashCode;      // Lower 31 bits of hash code, -1 if unused
  internal int next;          // Index of next entry, -1 if last
  internal T value;
}

存儲LIst集合：

public void UnionWith(IEnumerable<T> other)
{
  if (other == null)
  {
    throw new ArgumentNullException(nameof(other));
  }
  foreach (T item in other)
  {
    AddIfNotPresent(item);
  }
}

繼續往下追蹤：

private bool AddIfNotPresent(T value)
{
  if (_buckets == null)
  {
    Initialize(0);
  }

  int hashCode;
  int bucket;
  int collisionCount = 0;
  Slot[] slots = _slots;

  IEqualityComparer<T>? comparer = _comparer;

  if (comparer == null)
  {
  //取HASHCODE
    hashCode = value == null ? 0 : InternalGetHashCode(value.GetHashCode());
    bucket = hashCode % _buckets!.Length;

    if (default(T)! != null) // TODO-NULLABLE: default(T) == null warning (https://github.com/dotnet/roslyn/issues/34757)
    {
      for (int i = _buckets[bucket] - 1; i >= 0; i = slots[i].next)
      {
        if (slots[i].hashCode == hashCode && EqualityComparer<T>.Default.Equals(slots[i].value, value))
        {
          return false;
        }

        if (collisionCount >= slots.Length)
        {
          // The chain of entries forms a loop, which means a concurrent update has happened.
          throw new InvalidOperationException(SR.InvalidOperation_ConcurrentOperationsNotSupported);
        }
        collisionCount++;
      }
    }
    else
    {
      // Object type: Shared Generic, EqualityComparer<TValue>.Default won't devirtualize
      // https://github.com/dotnet/coreclr/issues/17273
      // So cache in a local rather than get EqualityComparer per loop iteration
      EqualityComparer<T> defaultComparer = EqualityComparer<T>.Default;

      for (int i = _buckets[bucket] - 1; i >= 0; i = slots[i].next)
      {
        if (slots[i].hashCode == hashCode && defaultComparer.Equals(slots[i].value, value))
        {
          return false;
        }

        if (collisionCount >= slots.Length)
        {
          // The chain of entries forms a loop, which means a concurrent update has happened.
          throw new InvalidOperationException(SR.InvalidOperation_ConcurrentOperationsNotSupported);
        }
        collisionCount++;
      }
    }
  }
  else
  {
    hashCode = value == null ? 0 : InternalGetHashCode(comparer.GetHashCode(value));
    bucket = hashCode % _buckets!.Length;

    for (int i = _buckets[bucket] - 1; i >= 0; i = slots[i].next)
    {
      if (slots[i].hashCode == hashCode && comparer.Equals(slots[i].value, value))
      {
        return false;
      }

      if (collisionCount >= slots.Length)
      {
        // The chain of entries forms a loop, which means a concurrent update has happened.
        throw new InvalidOperationException(SR.InvalidOperation_ConcurrentOperationsNotSupported);
      }
      collisionCount++;
    }
  }

  int index;
  if (_freeList >= 0)
  {
    index = _freeList;
    _freeList = slots[index].next;
  }
  else
  {
    if (_lastIndex == slots.Length)
    {
      IncreaseCapacity();
      // this will change during resize
      slots = _slots;
      bucket = hashCode % _buckets.Length;
    }
    index = _lastIndex;
    _lastIndex++;
  }
  slots[index].hashCode = hashCode;
  slots[index].value = value;
  slots[index].next = _buckets[bucket] - 1;
  _buckets[bucket] = index + 1;
  _count++;
  _version++;

  return true;
}
private const int Lower31BitMask = 0x7FFFFFFF;

獲取內部的HASHCODE

private static int InternalGetHashCode(T item, IEqualityComparer<T>? comparer)
{
  if (item == null)
  {
    return 0;
  }
  int hashCode = comparer?.GetHashCode(item) ?? item.GetHashCode();
  return hashCode & Lower31BitMask;
}

劃重點-》

slots[index].hashCode = hashCode;
slots[index].value = value;
slots[index].next = _buckets[bucket] - 1;

最終列表中的值存儲到結構中。

使用對象初始化HASHSET時，如果相同

HashSet<string> hashSet = new HashSet<string>();
 hashSet.Add("test");
 hashSet.Add("test");
 HashSet<string> hSet = new HashSet<string>(hashSet);

private void CopyFrom(HashSet<T> source)
{
  int count = source._count;
  if (count == 0)
  {
    // As well as short-circuiting on the rest of the work done,
    // this avoids errors from trying to access otherAsHashSet._buckets
    // or otherAsHashSet._slots when they aren't initialized.
    return;
  }

  int capacity = source._buckets!.Length;
  int threshold = HashHelpers.ExpandPrime(count + 1);

  if (threshold >= capacity)
  {
    _buckets = (int[])source._buckets.Clone();
    _slots = (Slot[])source._slots.Clone();

    _lastIndex = source._lastIndex;
    _freeList = source._freeList;
  }
  else
  {
    int lastIndex = source._lastIndex;
    Slot[] slots = source._slots;
    Initialize(count);
    int index = 0;
    for (int i = 0; i < lastIndex; ++i)
    {
      int hashCode = slots[i].hashCode;
      if (hashCode >= 0)
      {
        AddValue(index, hashCode, slots[i].value);
        ++index;
      }
    }
    Debug.Assert(index == count);
    _lastIndex = index;
  }
  _count = count;
}

public static int ExpandPrime(int oldSize)//返回要增長到的哈希表大小
{
  int newSize = 2 * oldSize;

  // Allow the hashtables to grow to maximum possible size (~2G elements) before encountering capacity overflow.
  // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
  if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
  {
    Debug.Assert(MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
    return MaxPrimeArrayLength;
  }

  return GetPrime(newSize);
}

這裡只貼出HashSet聲明創建對象的兩種方式。

下篇再研究具體實現〜