< Summary

Information
Class: SwiftCollections.SwiftHashSet<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.cs
Line coverage
100%
Covered lines: 374
Uncovered lines: 0
Coverable lines: 374
Total lines: 1029
Line coverage: 100%
Branch coverage
99%
Covered branches: 204
Total branches: 206
Branch coverage: 99%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor()100%11100%
.ctor(...)100%11100%
.ctor(...)100%11100%
.ctor(...)100%44100%
.ctor(...)100%11100%
get_Count()100%11100%
get_Comparer()100%11100%
System.Collections.Generic.ICollection<T>.get_IsReadOnly()100%11100%
get_Item(...)100%11100%
get_State()100%22100%
set_State(...)83.33%66100%
Add(...)100%11100%
System.Collections.Generic.ICollection<T>.Add(...)100%11100%
AddRange(...)100%66100%
AddKnownCountRange(...)100%44100%
AddUnknownCountRange(...)100%44100%
InsertIfNotExists(...)100%2424100%
Remove(...)100%1414100%
Clear()100%44100%
CheckLoadThreshold()100%22100%
EnsureCapacityForAddRange(...)100%22100%
EnsureCapacity(...)100%22100%
Resize(...)100%88100%
TrimExcess()100%1212100%
CalculateAdaptiveResizeFactors(...)83.33%66100%
Initialize(...)100%22100%
Contains(...)100%11100%
Exists(...)100%66100%
Find(...)100%66100%
TryGetValue(...)100%22100%
CopyTo(...)100%44100%
SetComparer(...)100%22100%
SwitchToRandomizedComparer()100%22100%
RehashEntries()100%88100%
FindEntry(...)100%1414100%
GetEnumerator()100%11100%
System.Collections.Generic.IEnumerable<T>.GetEnumerator()100%11100%
System.Collections.IEnumerable.GetEnumerator()100%11100%
.ctor(...)100%11100%
get_Current()100%11100%
System.Collections.IEnumerator.get_Current()100%11100%
MoveNext()100%44100%
Reset()100%11100%
Dispose()100%11100%
ExceptWith(...)100%44100%
IntersectWith(...)100%88100%
IsProperSubsetOf(...)100%88100%
IsProperSupersetOf(...)100%66100%
IsSubsetOf(...)100%88100%
IsSupersetOf(...)100%44100%
Overlaps(...)100%44100%
SetEquals(...)100%66100%
SymmetricExceptWith(...)100%66100%
UnionWith(...)100%22100%

File(s)

/home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.cs

#LineLine coverage
 1//=======================================================================
 2// SwiftHashSet.cs
 3//=======================================================================
 4// MIT License, Copyright (c) 2024–present David Oravsky (mrdav30)
 5// See LICENSE file in the project root for full license information.
 6//=======================================================================
 7
 8using Chronicler;
 9using MemoryPack;
 10using SwiftCollections.Diagnostics;
 11using SwiftCollections.Utility;
 12using System;
 13using System.Collections;
 14using System.Collections.Generic;
 15using System.Runtime.CompilerServices;
 16using System.Text.Json.Serialization;
 17
 18namespace SwiftCollections;
 19
 20/// <summary>
 21/// Represents a high-performance set of unique values with efficient operations for addition, removal, and lookup
 22/// </summary>
 23/// <typeparam name="T">The type of elements in the set.</typeparam>
 24/// <remarks>
 25/// The comparer is not serialized. After deserialization the set reverts
 26/// to the same default comparer selection used by a new instance. String values
 27/// use SwiftCollections' deterministic default comparer. Object values use a
 28/// SwiftCollections comparer that hashes strings deterministically, while other
 29/// object-value determinism still depends on the underlying value type's
 30/// <see cref="object.GetHashCode()"/> implementation. Other types use
 31/// <see cref="EqualityComparer{T}.Default"/>.
 32///
 33/// If a custom comparer is required it can be reapplied using
 34/// <see cref="SetComparer(IEqualityComparer{T})"/>.
 35/// </remarks>
 36[Serializable]
 37[JsonConverter(typeof(StateJsonConverterFactory))]
 38[MemoryPackable]
 39public sealed partial class SwiftHashSet<T> : IStateBacked<SwiftArrayState<T>>, ISet<T>, ICollection<T>, IEnumerable<T>,
 40    where T : notnull
 41{
 42    #region Constants
 43
 44    /// <summary>
 45    /// The default initial capacity of the set.
 46    /// </summary>
 47    public const int DefaultCapacity = 8;
 48
 49    /// <summary>
 50    /// Determines the maximum allowable load factor before resizing the hash set to maintain performance.
 51    /// </summary>
 52    private const float _LoadFactorThreshold = 0.85f;
 53
 54    #endregion
 55
 56    #region Fields
 57
 58    /// <summary>
 59    /// The array containing the entries of the SwiftHashSet.
 60    /// </summary>
 61    /// <remarks>
 62    /// Capacity will always be a power of two for efficient pooling cache.
 63    /// </remarks>
 64    private Entry[] _entries;
 65
 66    /// <summary>
 67    /// The total number of entries in the hash set
 68    /// </summary>
 69    private int _count;
 70
 71    private int _lastIndex;
 72
 73    /// <summary>
 74    /// A mask used for efficiently computing the entry index from a hash code.
 75    /// This is typically the size of the entry array minus one, assuming the size is a power of two.
 76    /// </summary>
 77    private int _entryMask;
 78
 79    /// <summary>
 80    /// The comparer used to determine equality of keys and to generate hash codes.
 81    /// </summary>
 82    private IEqualityComparer<T> _comparer;
 83
 84    /// <summary>
 85    /// Specifies the dynamic growth factor for resizing, adjusted based on recent usage patterns.
 86    /// </summary>
 87    private int _adaptiveResizeFactor;
 88
 89    /// <summary>
 90    /// Tracks the count threshold at which the hash set should resize based on the load factor.
 91    /// </summary>
 92    private uint _nextResizeCount;
 93
 94    /// <summary>
 95    /// Represents the moving average of the fill rate, used to dynamically adjust resizing behavior.
 96    /// </summary>
 97    private double _movingFillRate;
 98
 99    private int _maxStepCount;
 100
 101    /// <summary>
 102    /// A version counter used to track modifications to the set.
 103    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 104    /// </summary>
 105    private uint _version;
 106
 107    #endregion
 108
 109    #region Nested Types
 110
 111    /// <summary>
 112    /// Represents a single value in the set, including its hash code for quick access.
 113    /// </summary>
 114    private struct Entry
 115    {
 116        public T Value;
 117        public int HashCode;    // Lower 31 bits of hash code, -1 if deleted probe tombstone
 118        public bool IsUsed;
 119    }
 120
 121    #endregion
 122
 123    #region Constructors
 124
 125    /// <summary>
 126    /// Initialize a new instance of <see cref="SwiftHashSet{T}"/> with customizable capacity and comparer for optimal p
 127    /// </summary>
 144128    public SwiftHashSet() : this(DefaultCapacity, null) { }
 129
 130    /// <inheritdoc cref="SwiftHashSet()"/>
 12131    public SwiftHashSet(IEqualityComparer<T>? comparer) : this(DefaultCapacity, comparer) { }
 132
 133    /// <summary>
 134    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that is empty and has the default initial 
 135    /// </summary>
 90136    public SwiftHashSet(int capacity, IEqualityComparer<T>? comparer = null)
 137    {
 90138        Initialize(capacity, comparer);
 139
 90140        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 90141        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 90142    }
 143
 144    /// <summary>
 145    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that contains elements copied from the spe
 146    /// </summary>
 147    /// <param name="collection">The collection whose elements are copied to the new set.</param>
 148    /// <param name="comparer">The comparer to use when comparing elements.</param>
 42149    public SwiftHashSet(IEnumerable<T> collection, IEqualityComparer<T>? comparer = null)
 150    {
 42151        SwiftThrowHelper.ThrowIfNull(collection, nameof(collection));
 152
 42153        int count = (collection as ICollection<T>)?.Count ?? DefaultCapacity;
 42154        int size = (int)(count / _LoadFactorThreshold);  // Dynamic padding based on collision estimation
 42155        Initialize(size, comparer);
 156
 42157        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 42158        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 159
 356160        foreach (T item in collection)
 136161            InsertIfNotExists(item);
 42162    }
 163
 164    ///  <summary>
 165    ///  Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class with the specified <see cref="SwiftArrayS
 166    ///  </summary>
 167    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 168    [MemoryPackConstructor]
 6169    public SwiftHashSet(SwiftArrayState<T> state)
 170    {
 6171        State = state;
 172
 6173        SwiftThrowHelper.ThrowIfNull(_entries, nameof(_entries));
 6174        SwiftThrowHelper.ThrowIfNull(_comparer, nameof(_comparer));
 6175    }
 176
 177    #endregion
 178
 179    #region Properties
 180
 181    /// <summary>
 182    /// Gets the number of elements contained in the set.
 183    /// </summary>
 184    [JsonIgnore]
 185    [MemoryPackIgnore]
 82186    public int Count => _count;
 187
 188    /// <summary>
 189    /// Gets the <see cref="IEqualityComparer{T}"/> object that is used to determine equality for the values in the set.
 190    /// </summary>
 191    [JsonIgnore]
 192    [MemoryPackIgnore]
 14193    public IEqualityComparer<T> Comparer => _comparer;
 194
 195    [JsonIgnore]
 196    [MemoryPackIgnore]
 1197    bool ICollection<T>.IsReadOnly => false;
 198
 199    /// <summary>
 200    /// Gets the stored value that matches the specified key.
 201    /// </summary>
 202    /// <param name="key">The lookup value used to find an equal element in the set.</param>
 203    /// <exception cref="KeyNotFoundException">No matching value exists in the set.</exception>
 204    [JsonIgnore]
 205    [MemoryPackIgnore]
 206    public T this[T key]
 207    {
 208        get
 209        {
 2210            int index = FindEntry(key);
 2211            SwiftThrowHelper.ThrowIfKeyInvalid(index, key);
 1212            return _entries[index].Value;
 213        }
 214    }
 215
 216    /// <summary>
 217    /// Gets or sets the current state of the array, including its items and structure.
 218    /// </summary>
 219    /// <remarks>
 220    /// Setting this property replaces the contents of the array with the items from the specified state.
 221    /// If the provided state is empty, the array is cleared.
 222    /// The setter is intended for internal use and may reset internal versioning.
 223    /// </remarks>
 224    [JsonInclude]
 225    [MemoryPackInclude]
 226    public SwiftArrayState<T> State
 227    {
 228        get
 229        {
 6230            if (_count == 0)
 1231                return new SwiftArrayState<T>(Array.Empty<T>());
 232
 5233            T[] items = new T[_count];
 5234            CopyTo(items, 0);
 235
 5236            return new SwiftArrayState<T>(items);
 237        }
 238        internal set
 239        {
 6240            SwiftThrowHelper.ThrowIfNull(value.Items, nameof(value));
 241
 6242            T[] items = value.Items;
 6243            int count = items.Length;
 244
 6245            if (count == 0)
 246            {
 1247                Initialize(DefaultCapacity);
 1248                _count = 0;
 1249                _version = 0;
 1250                return;
 251            }
 252
 5253            int size = (int)(count / _LoadFactorThreshold);
 5254            Initialize(size);
 255
 54256            foreach (T item in items)
 22257                if (item != null)
 22258                    InsertIfNotExists(item);
 259
 5260            _version = 0;
 5261        }
 262    }
 263
 264    #endregion
 265
 266    #region Collection Manipulation
 267
 268    /// <inheritdoc/>
 269    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 270    public bool Add(T item)
 271    {
 214754272        CheckLoadThreshold();
 214754273        return InsertIfNotExists(item);
 274    }
 275
 1276    void ICollection<T>.Add(T item) => Add(item);
 277
 278    /// <summary>
 279    /// Adds the elements of the specified collection to the set, ignoring null values and duplicates.
 280    /// </summary>
 281    /// <remarks>
 282    /// If the source collection is the same instance as the set, the method returns without making any changes.
 283    /// The method preserves single-pass enumeration for sources that do not support multiple iterations.</remarks>
 284    /// <param name="items">The collection of elements to add to the set. Elements that are null or already present in t
 285    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 286    public void AddRange(IEnumerable<T> items)
 287    {
 5288        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 289
 5290        if (ReferenceEquals(this, items))
 1291            return;
 292
 4293        if (items is ICollection<T> collection)
 294        {
 2295            AddKnownCountRange(collection, collection.Count);
 2296            return;
 297        }
 298
 2299        if (items is IReadOnlyCollection<T> readOnlyCollection)
 300        {
 1301            AddKnownCountRange(readOnlyCollection, readOnlyCollection.Count);
 1302            return;
 303        }
 304
 1305        AddUnknownCountRange(items);
 1306    }
 307
 308    private void AddKnownCountRange(IEnumerable<T> items, int count)
 309    {
 3310        EnsureCapacityForAddRange(count);
 311
 20312        foreach (T item in items)
 7313            if (item != null)
 7314                InsertIfNotExists(item);
 3315    }
 316
 317    private void AddUnknownCountRange(IEnumerable<T> items)
 318    {
 8319        foreach (T item in items)
 3320            if (item != null)
 3321                Add(item);
 1322    }
 323
 324    /// <summary>
 325    /// Adds the specified element to the set if it's not already present.
 326    /// </summary>
 327    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 328    private bool InsertIfNotExists(T item)
 329    {
 214920330        SwiftThrowHelper.ThrowIfNullGeneric(item, nameof(item));
 331
 214919332        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 214919333        int entryIndex = hashCode & _entryMask;
 334
 214919335        int firstDeletedIndex = -1;
 214919336        int step = 1;
 214919337        int probeLimit = _entries.Length;
 371814338        while ((uint)step <= (uint)probeLimit)
 339        {
 371813340            ref Entry entry = ref _entries[entryIndex];
 371813341            if (entry.IsUsed)
 342            {
 156878343                if (entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 13344                    return false; // Item already exists
 345            }
 214935346            else if (entry.HashCode == -1)
 347            {
 40348                if (firstDeletedIndex < 0) firstDeletedIndex = entryIndex;
 349            }
 350            else
 351            {
 352                break;
 353            }
 354
 156895355            entryIndex = (entryIndex + step * step) & _entryMask; // Quadratic probing
 156895356            step++;
 357        }
 358
 214906359        if (firstDeletedIndex >= 0)
 9360            entryIndex = firstDeletedIndex;
 214897361        else if ((uint)step > (uint)probeLimit)
 362        {
 1363            Resize(_entries.Length * _adaptiveResizeFactor);
 1364            return InsertIfNotExists(item);
 365        }
 366
 329535367        if ((uint)entryIndex > (uint)_lastIndex) _lastIndex = entryIndex;
 368
 214905369        _entries[entryIndex].HashCode = hashCode;
 214905370        _entries[entryIndex].Value = item;
 214905371        _entries[entryIndex].IsUsed = true;
 214905372        _count++;
 214905373        _version++;
 374
 214905375        if ((uint)step > (uint)_maxStepCount)
 376        {
 1398377            _maxStepCount = step;
 1398378            if (_comparer is not IRandomedEqualityComparer && _maxStepCount > 100)
 23379                SwitchToRandomizedComparer();  // Attempt to recompute hash code with potential randomization for better
 380        }
 381
 214905382        return true;
 383    }
 384
 385    /// <summary>
 386    /// Removes the specified element from the set.
 387    /// </summary>
 388    /// <param name="item">The element to remove from the set.</param>
 389    /// <returns>
 390    /// True if the element is successfully found and removed; otherwise, false.
 391    /// </returns>
 392    public bool Remove(T item)
 393    {
 100568394        SwiftThrowHelper.ThrowIfNullGeneric(item, nameof(item));
 395
 100567396        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 100567397        int entryIndex = hashCode & _entryMask;
 398
 100567399        int step = 0;
 149970400        while ((uint)step <= (uint)_lastIndex)
 401        {
 149969402            ref Entry entry = ref _entries[entryIndex];
 403            // Stop probing if an unused entry is found (not deleted)
 149969404            if (!entry.IsUsed && entry.HashCode != -1)
 4405                return false;
 149965406            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 407            {
 408                // Mark entry as deleted
 100562409                entry.IsUsed = false;
 100562410                entry.Value = default!;
 100562411                entry.HashCode = -1;
 100562412                _count--;
 100563413                if ((uint)_count == 0) _lastIndex = 0;
 100562414                _version++;
 100562415                return true;
 416            }
 417
 418            // Entry not found in expected entry, it either doesn't exist or was moved via quadratic probing
 49403419            step++;
 49403420            entryIndex = (entryIndex + step * step) & _entryMask;
 421        }
 1422        return false; // Item not found after full loop
 423    }
 424
 425    /// <summary>
 426    /// Removes all elements from the set.
 427    /// </summary>
 428    public void Clear()
 429    {
 1050430        if ((uint)_count == 0) return;
 431
 18994432        for (uint i = 0; i <= (uint)_lastIndex; i++)
 433        {
 434            // Clear is a full reset, not a delete; future probes must be able to stop
 435            // at these now-empty slots instead of treating them as tombstones.
 8449436            _entries[i].HashCode = 0;
 8449437            _entries[i].Value = default!;
 8449438            _entries[i].IsUsed = false;
 439        }
 440
 1048441        _count = 0;
 1048442        _lastIndex = 0;
 1048443        _maxStepCount = 0;
 1048444        _movingFillRate = 0;
 1048445        _adaptiveResizeFactor = 4;
 446
 1048447        _version++;
 1048448    }
 449
 450    #endregion
 451
 452    #region Capacity Management
 453
 454    /// <summary>
 455    /// Ensures that the hash set is resized when the current load factor exceeds the predefined threshold.
 456    /// </summary>
 457    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 458    private void CheckLoadThreshold()
 459    {
 214754460        if ((uint)_count >= _nextResizeCount)
 35461            Resize(_entries.Length * _adaptiveResizeFactor);
 214754462    }
 463
 464    /// <summary>
 465    /// Ensures there is enough room to add a batch of items without repeatedly checking the load threshold.
 466    /// </summary>
 467    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 468    private void EnsureCapacityForAddRange(int incomingCount)
 469    {
 3470        if (incomingCount <= 0)
 1471            return;
 472
 2473        long requiredCount = (long)_count + incomingCount;
 2474        SwiftThrowHelper.ThrowIfTrue(requiredCount > int.MaxValue, message: "The collection is too large.");
 475
 2476        double minimumCapacity = Math.Ceiling(requiredCount / (double)_LoadFactorThreshold);
 2477        EnsureCapacity((int)Math.Min(minimumCapacity, int.MaxValue));
 2478    }
 479
 480    /// <summary>
 481    /// Ensures that the set can hold up to the specified number of elements without resizing.
 482    /// </summary>
 483    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 484    public void EnsureCapacity(int capacity)
 485    {
 4486        capacity = SwiftHashTools.NextPowerOfTwo(capacity);  // Capacity must be a power of 2 for proper masking
 4487        if (capacity > _entries.Length)
 2488            Resize(capacity);
 4489    }
 490
 491    /// <summary>
 492    /// Resizes the hash set to the specified capacity, redistributing all entries to maintain efficiency.
 493    /// </summary>
 494    /// <param name="newSize"></param>
 495    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 496    private void Resize(int newSize)
 497    {
 38498        Entry[] newEntries = new Entry[newSize];
 38499        int newMask = newSize - 1;
 500
 38501        int lastIndex = 0;
 184558502        for (uint i = 0; i <= (uint)_lastIndex; i++)
 503        {
 92241504            if (_entries[i].IsUsed)
 505            {
 85679506                ref Entry oldEntry = ref _entries[i];
 85679507                int newIndex = oldEntry.HashCode & newMask;
 508                // If current entry not available, perform Quadratic probing to find the next available entry
 85679509                int step = 1;
 90625510                while (newEntries[newIndex].IsUsed)
 511                {
 4946512                    newIndex = (newIndex + step * step) & newMask;
 4946513                    step++;
 514                }
 85679515                newEntries[newIndex] = oldEntry;
 134246516                if (newIndex > lastIndex) lastIndex = newIndex;
 517            }
 518        }
 519
 38520        _lastIndex = lastIndex;
 521
 38522        CalculateAdaptiveResizeFactors(newSize);
 523
 38524        _entries = newEntries;
 38525        _entryMask = newMask;
 526
 38527        _version++;
 38528    }
 529
 530    /// <summary>
 531    /// Sets the capacity of a <see cref="SwiftHashSet{T}"/> to the actual
 532    /// number of elements it contains, rounded up to a nearby next power of 2 value.
 533    /// </summary>
 534    public void TrimExcess()
 535    {
 3536        int newSize = _count <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(_count);
 4537        if (newSize >= _entries.Length) return;
 538
 2539        Entry[] newEntries = new Entry[newSize];
 2540        int newMask = newSize - 1;
 541
 2542        int lastIndex = 0;
 40543        for (int i = 0; i <= (uint)_lastIndex; i++)
 544        {
 18545            if (_entries[i].IsUsed)
 546            {
 15547                ref Entry oldEntry = ref _entries[i];
 15548                int newIndex = oldEntry.HashCode & newMask;
 549                // If current entry not available, perform quadratic probing to find the next available entry
 15550                int step = 1;
 18551                while (newEntries[newIndex].IsUsed)
 552                {
 3553                    newIndex = (newIndex + step * step) & newMask;
 3554                    step++;
 555                }
 15556                newEntries[newIndex] = oldEntry;
 28557                if (newIndex > lastIndex) lastIndex = newIndex;
 558            }
 559        }
 560
 2561        _lastIndex = lastIndex;
 562
 2563        CalculateAdaptiveResizeFactors(newSize);
 564
 2565        _entryMask = newMask;
 2566        _entries = newEntries;
 567
 2568        _version++;
 2569    }
 570
 571    /// <summary>
 572    ///  Updates adaptive resize parameters based on the current fill rate to balance memory usage and performance.
 573    /// </summary>
 574    /// <param name="newSize"></param>
 575    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 576    private void CalculateAdaptiveResizeFactors(int newSize)
 577    {
 578        // Calculate current fill rate and update moving average
 40579        double currentFillRate = (double)_count / newSize;
 40580        _movingFillRate = _movingFillRate == 0 ? currentFillRate : (_movingFillRate * 0.7 + currentFillRate * 0.3);
 581
 40582        if (_movingFillRate > 0.3f)
 3583            _adaptiveResizeFactor = 2; // Growth stabilizing
 37584        else if (_movingFillRate < 0.28f)
 37585            _adaptiveResizeFactor = 4; // Rapid growth
 586
 587        // Reset the resize threshold based on the new size
 40588        _nextResizeCount = (uint)(newSize * _LoadFactorThreshold);
 40589    }
 590
 591    #endregion
 592
 593    #region Utility Methods
 594
 595    /// <summary>
 596    /// Initializes the hash set with a given capacity, ensuring it starts with an optimal internal structure.
 597    /// </summary>
 598    /// <param name="capacity"></param>
 599    /// <param name="comparer"></param>
 600    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 601    private void Initialize(int capacity, IEqualityComparer<T>? comparer = null)
 602    {
 138603        _comparer = SwiftHashTools.GetDefaultEqualityComparer(comparer);
 604
 138605        int size = capacity < DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 138606        _entries = new Entry[size];
 138607        _entryMask = size - 1;
 608
 138609        _nextResizeCount = (uint)(size * _LoadFactorThreshold);
 138610        _adaptiveResizeFactor = 4; // start agressive
 138611        _movingFillRate = 0.0;
 138612    }
 613
 614    /// <summary>
 615    /// Determines whether the set contains the specified element.
 616    /// </summary>
 617    /// <param name="item">The element to locate in the set.</param>
 618    /// <returns>
 619    /// True if the set contains the specified element; otherwise, false.
 620    /// </returns>
 621    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 1378622    public bool Contains(T item) => FindEntry(item) >= 0;
 623
 624    /// <summary>
 625    /// Determines whether the <see cref="SwiftHashSet{T}"/> contains an element that matches the conditions defined by 
 626    /// </summary>
 627    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 628    /// <returns><c>true</c> if the <see cref="SwiftHashSet{T}"/> contains one or more elements that match the specified
 629    public bool Exists(Predicate<T> match)
 630    {
 3631        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 632
 16633        for (int i = 0; i <= _lastIndex; i++)
 634        {
 7635            if (_entries[i].IsUsed && match(_entries[i].Value))
 1636                return true;
 637        }
 638
 1639        return false;
 640    }
 641
 642    /// <summary>
 643    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 644    /// </summary>
 645    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 646    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 647    public T Find(Predicate<T> match)
 648    {
 2649        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 650
 16651        for (int i = 0; i <= _lastIndex; i++)
 652        {
 7653            if (_entries[i].IsUsed && match(_entries[i].Value))
 1654                return _entries[i].Value;
 655        }
 656
 1657        return default!;
 658    }
 659
 660    /// <summary>
 661    /// Searches the set for a given value and returns the equal value it finds, if any.
 662    /// </summary>
 663    public bool TryGetValue(T expected, out T actual)
 664    {
 2665        int index = FindEntry(expected);
 2666        if (index >= 0)
 667        {
 1668            actual = _entries[index].Value;
 1669            return true;
 670        }
 1671        actual = default!;
 1672        return false;
 673    }
 674
 675    /// <summary>
 676    /// Copies the elements of the set to an array, starting at the specified array index.
 677    /// </summary>
 678    public void CopyTo(T[] array, int arrayIndex)
 679    {
 11680        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 10681        SwiftThrowHelper.ThrowIfArrayIndexInvalid(arrayIndex, array.Length);
 8682        SwiftThrowHelper.ThrowIfArgument(array.Length - arrayIndex < _count, nameof(array), "The array is not large enou
 683
 114684        for (uint i = 0; i <= (uint)_lastIndex; i++)
 685        {
 50686            if (_entries[i].IsUsed)
 28687                array[arrayIndex++] = _entries[i].Value;
 688        }
 7689    }
 690
 691    /// <summary>
 692    /// Switches the hash set's comparer and rehashes all entries
 693    /// using the new comparer to redistribute them across <see cref="_entries"/>.
 694    /// </summary>
 695    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 696    public void SetComparer(IEqualityComparer<T>? comparer = null)
 697    {
 5698        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 4699        if (ReferenceEquals(comparer, _comparer))
 1700            return;
 701
 3702        _comparer = comparer;
 3703        RehashEntries();
 3704    }
 705
 706    /// <summary>
 707    /// Replaces the hash set's comparer with a randomized comparer to mitigate high collision rates.
 708    /// </summary>
 709    private void SwitchToRandomizedComparer()
 710    {
 23711        if (SwiftHashTools.IsWellKnownEqualityComparer(_comparer))
 1712            _comparer = (IEqualityComparer<T>)SwiftHashTools.GetSwiftEqualityComparer(_comparer);
 22713        else return; // nothing to do here
 714
 1715        RehashEntries();
 1716        _maxStepCount = 0;
 717
 1718        _version++;
 1719    }
 720
 721    /// <summary>
 722    /// Reconstructs the internal entry structure to align with updated hash codes, ensuring efficient access and storag
 723    /// </summary>
 724    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 725    private void RehashEntries()
 726    {
 4727        Entry[] newEntries = new Entry[_entries.Length];
 4728        int newMask = newEntries.Length - 1;
 729
 4730        int lastIndex = 0;
 584731        for (uint i = 0; i <= (uint)_lastIndex; i++)
 732        {
 288733            if (_entries[i].IsUsed)
 734            {
 101735                ref Entry oldEntry = ref _entries[i];
 101736                oldEntry.HashCode = _comparer.GetHashCode(oldEntry.Value) & 0x7FFFFFFF;
 101737                int newIndex = oldEntry.HashCode & newMask;
 101738                int step = 1;
 125739                while (newEntries[newIndex].IsUsed)
 740                {
 24741                    newIndex = (newIndex + step * step) & newMask; // Quadratic probing
 24742                    step++;
 743                }
 101744                newEntries[newIndex] = _entries[i];
 118745                if (newIndex > lastIndex) lastIndex = newIndex;
 746            }
 747        }
 748
 4749        _lastIndex = lastIndex;
 750
 4751        _entryMask = newMask;
 4752        _entries = newEntries;
 753
 4754        _version++;
 4755    }
 756
 757    /// <summary>
 758    /// Searches for an entry in the hash set by following its probing sequence, returning its index if found.
 759    /// </summary>
 760    /// <param name="item"></param>
 761    /// <returns></returns>
 762    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 763    private int FindEntry(T item)
 764    {
 1383765        if (item == null) return -1;
 766
 1381767        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 1381768        int entryIndex = hashCode & _entryMask;
 769
 1381770        int step = 0;
 13570771        while ((uint)step <= (uint)_lastIndex)
 772        {
 13569773            ref Entry entry = ref _entries[entryIndex];
 774            // Stop probing if an unused entry is found (not deleted)
 13569775            if (!entry.IsUsed && entry.HashCode != -1)
 530776                return -1;
 13039777            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 850778                return entryIndex; // Match found
 779
 780            // Perform quadratic probing to see if maybe the entry was shifted.
 12189781            step++;
 12189782            entryIndex = (entryIndex + step * step) & _entryMask;
 783
 784        }
 1785        return -1; // Item not found, full loop completed
 786    }
 787
 788    #endregion
 789
 790    #region Enumerators
 791
 792    /// <summary>
 793    /// Returns an enumerator that iterates through the set.
 794    /// </summary>
 37795    public SwiftHashSetEnumerator GetEnumerator() => new(this);
 15796    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1797    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 798
 799    /// <summary>
 800    /// Provides an enumerator for iterating through the elements of the hash set, ensuring consistency during enumerati
 801    /// </summary>
 802    public struct SwiftHashSetEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 803    {
 804        private readonly SwiftHashSet<T> _set;
 805        private readonly Entry[] _entries;
 806        private readonly uint _version;
 807        private int _index;
 808        private T _current;
 809
 810        internal SwiftHashSetEnumerator(SwiftHashSet<T> set)
 811        {
 37812            _set = set;
 37813            _version = set._version;
 37814            _entries = set._entries; // Cache the entry array
 37815            _index = -1;
 37816            _current = default!;
 37817        }
 818
 819        /// <inheritdoc/>
 73820        public readonly T Current => _current;
 821
 822        readonly object IEnumerator.Current
 823        {
 824            get
 825            {
 1826                SwiftThrowHelper.ThrowIfTrue(_index > (uint)_set._lastIndex, message: "Enumeration has either not starte
 1827                return _current;
 828            }
 829        }
 830
 831        /// <inheritdoc/>
 832        public bool MoveNext()
 833        {
 105834            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 835
 104836            uint last = (uint)_set._lastIndex;
 161837            while (++_index <= last)
 838            {
 130839                if (_entries[_index].IsUsed)
 840                {
 73841                    _current = _entries[_index].Value;
 73842                    return true;
 843                }
 844            }
 845
 31846            _current = default!;
 31847            return false;
 848        }
 849
 850        /// <inheritdoc/>
 851        public void Reset()
 852        {
 1853            SwiftThrowHelper.ThrowIfTrue(_version != _set._version, message: "Collection was modified during enumeration
 854
 1855            _index = -1;
 1856            _current = default!;
 1857        }
 858
 859        /// <inheritdoc/>
 34860        public void Dispose() => _index = -1;
 861    }
 862
 863    #endregion
 864
 865    #region ISet<T> Implementations
 866
 867    /// <inheritdoc/>
 868    public void ExceptWith(IEnumerable<T> other)
 869    {
 2870        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 871
 2872        if (ReferenceEquals(this, other))
 873        {
 1874            Clear();
 1875            return;
 876        }
 877
 1878        var otherSet = new SwiftHashSet<T>(other, _comparer);
 879
 8880        foreach (var item in otherSet)
 3881            Remove(item);
 1882    }
 883
 884    /// <inheritdoc/>
 885    public void IntersectWith(IEnumerable<T> other)
 886    {
 2887        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 888
 2889        if (ReferenceEquals(this, other))
 1890            return;
 891
 1892        var otherSet = new SwiftHashSet<T>(other, _comparer);
 893
 12894        for (int i = 0; i <= _lastIndex; i++)
 895        {
 5896            if (_entries[i].IsUsed)
 897            {
 4898                var value = _entries[i].Value;
 4899                if (!otherSet.Contains(value))
 2900                    Remove(value);
 901            }
 902        }
 1903    }
 904
 905    /// <inheritdoc/>
 906    public bool IsProperSubsetOf(IEnumerable<T> other)
 907    {
 3908        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 909
 3910        var otherSet = new SwiftHashSet<T>(other, _comparer);
 911
 3912        if (Count >= otherSet.Count)
 1913            return false;
 914
 14915        for (int i = 0; i <= _lastIndex; i++)
 6916            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 1917                return false;
 918
 1919        return true;
 920    }
 921
 922    /// <inheritdoc/>
 923    public bool IsProperSupersetOf(IEnumerable<T> other)
 924    {
 3925        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 926
 3927        var otherSet = new SwiftHashSet<T>(other, _comparer);
 928
 3929        if (Count <= otherSet.Count)
 1930            return false;
 931
 9932        foreach (var item in otherSet)
 3933            if (!Contains(item))
 1934                return false;
 935
 1936        return true;
 1937    }
 938
 939    /// <inheritdoc/>
 940    public bool IsSubsetOf(IEnumerable<T> other)
 941    {
 3942        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 943
 3944        var otherSet = new SwiftHashSet<T>(other, _comparer);
 945
 3946        if (otherSet.Count < Count)
 1947            return false;
 948
 14949        for (int i = 0; i <= _lastIndex; i++)
 6950            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 1951                return false;
 952
 1953        return true;
 954    }
 955
 956    /// <inheritdoc/>
 957    public bool IsSupersetOf(IEnumerable<T> other)
 958    {
 2959        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 960
 13961        foreach (var item in other)
 962        {
 5963            if (!Contains(item))
 1964                return false;
 965        }
 966
 1967        return true;
 1968    }
 969
 970    /// <inheritdoc/>
 971    public bool Overlaps(IEnumerable<T> other)
 972    {
 2973        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 974
 9975        foreach (var item in other)
 3976            if (Contains(item))
 1977                return true;
 978
 1979        return false;
 1980    }
 981
 982    /// <inheritdoc/>
 983    public bool SetEquals(IEnumerable<T> other)
 984    {
 10985        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 986
 10987        var otherSet = new SwiftHashSet<T>(other, _comparer);
 988
 10989        if (otherSet.Count != Count)
 1990            return false;
 991
 76992        foreach (var item in otherSet)
 30993            if (!Contains(item))
 2994                return false;
 995
 7996        return true;
 2997    }
 998
 999    /// <inheritdoc/>
 1000    public void SymmetricExceptWith(IEnumerable<T> other)
 1001    {
 21002        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 1003
 21004        if (ReferenceEquals(this, other))
 1005        {
 11006            Clear();
 11007            return;
 1008        }
 1009
 11010        var otherSet = new SwiftHashSet<T>(other, _comparer);
 1011
 61012        foreach (var item in otherSet)
 1013        {
 21014            if (!Remove(item))
 11015                Add(item);
 1016        }
 11017    }
 1018
 1019    /// <inheritdoc/>
 1020    public void UnionWith(IEnumerable<T> other)
 1021    {
 11022        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 1023
 61024        foreach (var item in other)
 21025            Add(item);
 11026    }
 1027
 1028    #endregion
 1029}
Generated by: ReportGenerator 5.5.10.0
07/01/2026 - 04:31:31
GitHub | reportgenerator.io

Methods/Properties

.ctor()
.ctor(System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(System.Int32,System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(System.Collections.Generic.IEnumerable`1<T>,System.Collections.Generic.IEqualityComparer`1<T>)
.ctor(SwiftCollections.SwiftArrayState`1<T>)
get_Count()
get_Comparer()
System.Collections.Generic.ICollection<T>.get_IsReadOnly()
get_Item(T)
get_State()
set_State(SwiftCollections.SwiftArrayState`1<T>)
Add(T)
System.Collections.Generic.ICollection<T>.Add(T)
AddRange(System.Collections.Generic.IEnumerable`1<T>)
AddKnownCountRange(System.Collections.Generic.IEnumerable`1<T>,System.Int32)
AddUnknownCountRange(System.Collections.Generic.IEnumerable`1<T>)
InsertIfNotExists(T)
Remove(T)
Clear()
CheckLoadThreshold()
EnsureCapacityForAddRange(System.Int32)
EnsureCapacity(System.Int32)
Resize(System.Int32)
TrimExcess()
CalculateAdaptiveResizeFactors(System.Int32)
Initialize(System.Int32,System.Collections.Generic.IEqualityComparer`1<T>)
Contains(T)
Exists(System.Predicate`1<T>)
Find(System.Predicate`1<T>)
TryGetValue(T,T&)
CopyTo(T[],System.Int32)
SetComparer(System.Collections.Generic.IEqualityComparer`1<T>)
SwitchToRandomizedComparer()
RehashEntries()
FindEntry(T)
GetEnumerator()
System.Collections.Generic.IEnumerable<T>.GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()
.ctor(SwiftCollections.SwiftHashSet`1<T>)
get_Current()
System.Collections.IEnumerator.get_Current()
MoveNext()
Reset()
Dispose()
ExceptWith(System.Collections.Generic.IEnumerable`1<T>)
IntersectWith(System.Collections.Generic.IEnumerable`1<T>)
IsProperSubsetOf(System.Collections.Generic.IEnumerable`1<T>)
IsProperSupersetOf(System.Collections.Generic.IEnumerable`1<T>)
IsSubsetOf(System.Collections.Generic.IEnumerable`1<T>)
IsSupersetOf(System.Collections.Generic.IEnumerable`1<T>)
Overlaps(System.Collections.Generic.IEnumerable`1<T>)
SetEquals(System.Collections.Generic.IEnumerable`1<T>)
SymmetricExceptWith(System.Collections.Generic.IEnumerable`1<T>)
UnionWith(System.Collections.Generic.IEnumerable`1<T>)