< Summary

Information
Class: SwiftCollections.SwiftHashSet<T>
Assembly: SwiftCollections
File(s): /home/runner/work/SwiftCollections/SwiftCollections/src/SwiftCollections/Collection/SwiftHashSet.cs
Line coverage
95%
Covered lines: 441
Uncovered lines: 19
Coverable lines: 460
Total lines: 950
Line coverage: 95.8%
Branch coverage
93%
Covered branches: 201
Total branches: 216
Branch coverage: 93%
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(...)75%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()50%2285.71%
set_State(...)87.5%88100%
Add(...)100%11100%
System.Collections.Generic.ICollection<T>.Add(...)100%11100%
AddRange(...)100%181894.73%
InsertIfNotExists(...)100%1414100%
Remove(...)92.85%1414100%
Clear()100%44100%
CheckLoadThreshold()100%22100%
EnsureCapacityForAddRange(...)66.66%6677.77%
EnsureCapacity(...)100%22100%
Resize(...)100%88100%
TrimExcess()83.33%121285.71%
CalculateAdaptiveResizeFactors(...)100%66100%
Initialize(...)100%22100%
Contains(...)100%11100%
Exists(...)100%66100%
Find(...)100%66100%
TryGetValue(...)100%22100%
CopyTo(...)100%88100%
SetComparer(...)100%2285.71%
SwitchToRandomizedComparer()100%2287.5%
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()50%22100%
MoveNext()100%66100%
Reset()50%2283.33%
Dispose()100%11100%
ExceptWith(...)75%4470%
IntersectWith(...)100%8893.33%
IsProperSubsetOf(...)87.5%8890%
IsProperSupersetOf(...)83.33%6690%
IsSubsetOf(...)87.5%8890%
IsSupersetOf(...)100%44100%
Overlaps(...)100%44100%
SetEquals(...)83.33%6690%
SymmetricExceptWith(...)100%66100%
UnionWith(...)100%22100%

File(s)

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

#LineLine coverage
 1using MemoryPack;
 2using System;
 3using System.Collections;
 4using System.Collections.Generic;
 5using System.Runtime.CompilerServices;
 6using System.Text.Json.Serialization;
 7
 8namespace SwiftCollections;
 9
 10/// <summary>
 11/// Represents a high-performance set of unique values with efficient operations for addition, removal, and lookup
 12/// </summary>
 13/// <typeparam name="T">The type of elements in the set.</typeparam>
 14/// <remarks>
 15/// The comparer is not serialized. After deserialization the set reverts
 16/// to the same default comparer selection used by a new instance. String values
 17/// use SwiftCollections' deterministic default comparer. Object values use a
 18/// SwiftCollections comparer that hashes strings deterministically, while other
 19/// object-value determinism still depends on the underlying value type's
 20/// <see cref="object.GetHashCode()"/> implementation. Other types use
 21/// <see cref="EqualityComparer{T}.Default"/>.
 22///
 23/// If a custom comparer is required it can be reapplied using
 24/// <see cref="SetComparer(IEqualityComparer{T})"/>.
 25/// </remarks>
 26[Serializable]
 27[JsonConverter(typeof(SwiftStateJsonConverterFactory))]
 28[MemoryPackable]
 29public sealed partial class SwiftHashSet<T> : ISet<T>, ICollection<T>, IEnumerable<T>, IEnumerable, IReadOnlyCollection<
 30{
 31    #region Constants
 32
 33    /// <summary>
 34    /// The default initial capacity of the set.
 35    /// </summary>
 36    public const int DefaultCapacity = 8;
 37
 38    /// <summary>
 39    /// Determines the maximum allowable load factor before resizing the hash set to maintain performance.
 40    /// </summary>
 41    private const float _LoadFactorThreshold = 0.85f;
 42
 43    #endregion
 44
 45    #region Fields
 46
 47    /// <summary>
 48    /// The array containing the entries of the SwiftHashSet.
 49    /// </summary>
 50    /// <remarks>
 51    /// Capacity will always be a power of two for efficient pooling cache.
 52    /// </remarks>
 53    private Entry[] _entries;
 54
 55    /// <summary>
 56    /// The total number of entries in the hash set
 57    /// </summary>
 58    private int _count;
 59
 60    private int _lastIndex;
 61
 62    /// <summary>
 63    /// A mask used for efficiently computing the entry index from a hash code.
 64    /// This is typically the size of the entry array minus one, assuming the size is a power of two.
 65    /// </summary>
 66    private int _entryMask;
 67
 68    /// <summary>
 69    /// The comparer used to determine equality of keys and to generate hash codes.
 70    /// </summary>
 71    private IEqualityComparer<T> _comparer;
 72
 73    /// <summary>
 74    /// Specifies the dynamic growth factor for resizing, adjusted based on recent usage patterns.
 75    /// </summary>
 76    private int _adaptiveResizeFactor;
 77
 78    /// <summary>
 79    /// Tracks the count threshold at which the hash set should resize based on the load factor.
 80    /// </summary>
 81    private uint _nextResizeCount;
 82
 83    /// <summary>
 84    /// Represents the moving average of the fill rate, used to dynamically adjust resizing behavior.
 85    /// </summary>
 86    private double _movingFillRate;
 87
 88    private int _maxStepCount;
 89
 90    /// <summary>
 91    /// A version counter used to track modifications to the set.
 92    /// Incremented on mutations to detect changes during enumeration and ensure enumerator validity.
 93    /// </summary>
 94    private uint _version;
 95
 96    #endregion
 97
 98    #region Nested Types
 99
 100    /// <summary>
 101    /// Represents a single value in the set, including its hash code for quick access.
 102    /// </summary>
 103    private struct Entry
 104    {
 105        public T Value;
 106        public int HashCode;    // Lower 31 bits of hash code, -1 if unused
 107        public bool IsUsed;
 108    }
 109
 110    #endregion
 111
 112    #region Constructors
 113
 114    /// <summary>
 115    /// Initialize a new instance of <see cref="SwiftHashSet{T}"/> with customizable capacity and comparer for optimal p
 116    /// </summary>
 183117    public SwiftHashSet() : this(DefaultCapacity, null) { }
 118
 119    /// <inheritdoc cref="SwiftHashSet()"/>
 18120    public SwiftHashSet(IEqualityComparer<T> comparer) : this(DefaultCapacity, comparer) { }
 121
 122    /// <summary>
 123    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that is empty and has the default initial 
 124    /// </summary>
 71125    public SwiftHashSet(int capacity, IEqualityComparer<T> comparer = null)
 71126    {
 71127        Initialize(capacity, comparer);
 71128    }
 129
 130    /// <summary>
 131    /// Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class that contains elements copied from the spe
 132    /// </summary>
 133    /// <param name="collection">The collection whose elements are copied to the new set.</param>
 134    /// <param name="comparer">The comparer to use when comparing elements.</param>
 32135    public SwiftHashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer = null)
 32136    {
 32137        SwiftThrowHelper.ThrowIfNull(collection, nameof(collection));
 138
 32139        int count = (collection as ICollection<T>)?.Count ?? DefaultCapacity;
 32140        int size = (int)(count / _LoadFactorThreshold);  // Dynamic padding based on collision estimation
 32141        Initialize(size, comparer);
 142
 310143        foreach (T item in collection)
 107144            InsertIfNotExists(item);
 32145    }
 146
 147    ///  <summary>
 148    ///  Initializes a new instance of the <see cref="SwiftHashSet{T}"/> class with the specified <see cref="SwiftArrayS
 149    ///  </summary>
 150    ///  <param name="state">The state containing the internal array, count, offset, and version for initialization.</pa
 151    [MemoryPackConstructor]
 6152    public SwiftHashSet(SwiftArrayState<T> state)
 6153    {
 6154        State = state;
 6155    }
 156
 157    #endregion
 158
 159    #region Properties
 160
 161    /// <summary>
 162    /// Gets the number of elements contained in the set.
 163    /// </summary>
 164    [JsonIgnore]
 165    [MemoryPackIgnore]
 63166    public int Count => _count;
 167
 168    /// <summary>
 169    /// Gets the <see cref="IEqualityComparer{T}"/> object that is used to determine equality for the values in the set.
 170    /// </summary>
 171    [JsonIgnore]
 172    [MemoryPackIgnore]
 13173    public IEqualityComparer<T> Comparer => _comparer;
 174
 175    [JsonIgnore]
 176    [MemoryPackIgnore]
 1177    bool ICollection<T>.IsReadOnly => false;
 178
 179    /// <summary>
 180    /// Gets the stored value that matches the specified key.
 181    /// </summary>
 182    /// <param name="key">The lookup value used to find an equal element in the set.</param>
 183    /// <exception cref="KeyNotFoundException">No matching value exists in the set.</exception>
 184    [JsonIgnore]
 185    [MemoryPackIgnore]
 186    public T this[T key]
 187    {
 188        get
 2189        {
 2190            int index = FindEntry(key);
 2191            SwiftThrowHelper.ThrowIfKeyInvalid(index, key);
 1192            return _entries[index].Value;
 1193        }
 194    }
 195
 196    [JsonInclude]
 197    [MemoryPackInclude]
 198    public SwiftArrayState<T> State
 199    {
 200        get
 5201        {
 5202            if (_count == 0)
 0203                return new SwiftArrayState<T>(Array.Empty<T>());
 204
 5205            T[] items = new T[_count];
 5206            CopyTo(items, 0);
 207
 5208            return new SwiftArrayState<T>(items);
 5209        }
 210        internal set
 6211        {
 6212            T[] items = value.Items;
 6213            int count = items?.Length ?? 0;
 214
 6215            if (count == 0)
 1216            {
 1217                Initialize(DefaultCapacity);
 1218                _count = 0;
 1219                _version = 0;
 1220                return;
 221            }
 222
 5223            int size = (int)(count / _LoadFactorThreshold);
 5224            Initialize(size);
 225
 59226            foreach (T item in items)
 22227                if (item != null)
 22228                    InsertIfNotExists(item);
 229
 5230            _version = 0;
 6231        }
 232    }
 233
 234    #endregion
 235
 236    #region Collection Manipulation
 237
 238    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 239    public bool Add(T item)
 213522240    {
 213522241        CheckLoadThreshold();
 213522242        return InsertIfNotExists(item);
 213521243    }
 244
 1245    void ICollection<T>.Add(T item) => Add(item);
 246
 247    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 248    public void AddRange(IEnumerable<T> items)
 3249    {
 3250        SwiftThrowHelper.ThrowIfNull(items, nameof(items));
 251
 3252        if (ReferenceEquals(this, items))
 0253            return;
 254
 3255        if (items is ICollection<T> collection)
 1256        {
 1257            EnsureCapacityForAddRange(collection.Count);
 258
 9259            foreach (T item in collection)
 6260                if (item != null) InsertIfNotExists(item);
 261
 1262            return;
 263        }
 264
 2265        if (items is IReadOnlyCollection<T> readOnlyCollection)
 1266        {
 1267            EnsureCapacityForAddRange(readOnlyCollection.Count);
 268
 11269            foreach (T item in readOnlyCollection)
 8270                if (item != null) InsertIfNotExists(item);
 271
 1272            return;
 273        }
 274
 275        // Preserve single-pass enumeration for lazy or one-shot sources.
 9276        foreach (T item in items)
 6277            if (item != null) Add(item);
 3278    }
 279
 280    /// <summary>
 281    /// Adds the specified element to the set if it's not already present.
 282    /// </summary>
 283    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 284    private bool InsertIfNotExists(T item)
 213658285    {
 213658286        SwiftThrowHelper.ThrowIfNull(item, nameof(item));
 287
 213657288        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 213657289        int entryIndex = hashCode & _entryMask;
 290
 213657291        int step = 1;
 363170292        while (_entries[entryIndex].IsUsed)
 149525293        {
 149525294            if (_entries[entryIndex].HashCode == hashCode && _comparer.Equals(_entries[entryIndex].Value, item))
 12295                return false; // Item already exists
 296
 149513297            entryIndex = (entryIndex + step * step) & _entryMask; // Quadratic probing
 149513298            step++;
 149513299        }
 300
 327167301        if ((uint)entryIndex > (uint)_lastIndex) _lastIndex = entryIndex;
 302
 213645303        _entries[entryIndex].HashCode = hashCode;
 213645304        _entries[entryIndex].Value = item;
 213645305        _entries[entryIndex].IsUsed = true;
 213645306        _count++;
 213645307        _version++;
 308
 213645309        if ((uint)step > (uint)_maxStepCount)
 201310        {
 201311            _maxStepCount = step;
 201312            if (_comparer is not IRandomedEqualityComparer && _maxStepCount > 100)
 1313                SwitchToRandomizedComparer();  // Attempt to recompute hash code with potential randomization for better
 201314        }
 315
 213645316        return true;
 213657317    }
 318
 319    /// <summary>
 320    /// Removes the specified element from the set.
 321    /// </summary>
 322    /// <param name="item">The element to remove from the set.</param>
 323    /// <returns>
 324    /// True if the element is successfully found and removed; otherwise, false.
 325    /// </returns>
 326    public bool Remove(T item)
 100565327    {
 100565328        SwiftThrowHelper.ThrowIfNull(item, nameof(item));
 329
 100564330        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 100564331        int entryIndex = hashCode & _entryMask;
 332
 100564333        int step = 0;
 150821334        while ((uint)step <= (uint)_lastIndex)
 150820335        {
 150820336            ref Entry entry = ref _entries[entryIndex];
 337            // Stop probing if an unused entry is found (not deleted)
 150820338            if (!entry.IsUsed && entry.HashCode != -1)
 4339                return false;
 150816340            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 100559341            {
 342                // Mark entry as deleted
 100559343                entry.IsUsed = false;
 100559344                entry.Value = default;
 100559345                entry.HashCode = -1;
 100559346                _count--;
 100559347                if ((uint)_count == 0) _lastIndex = 0;
 100559348                _version++;
 100559349                return true;
 350            }
 351
 352            // Entry not found in expected entry, it either doesn't exist or was moved via quadratic probing
 50257353            step++;
 50257354            entryIndex = (entryIndex + step * step) & _entryMask;
 50257355        }
 1356        return false; // Item not found after full loop
 100564357    }
 358
 359    /// <summary>
 360    /// Removes all elements from the set.
 361    /// </summary>
 362    public void Clear()
 7363    {
 8364        if ((uint)_count == 0) return;
 365
 246366        for (uint i = 0; i <= (uint)_lastIndex; i++)
 117367        {
 117368            _entries[i].HashCode = -1;
 117369            _entries[i].Value = default;
 117370            _entries[i].IsUsed = false;
 117371        }
 372
 6373        _count = 0;
 6374        _lastIndex = 0;
 6375        _maxStepCount = 0;
 6376        _movingFillRate = 0;
 6377        _adaptiveResizeFactor = 4;
 378
 6379        _version++;
 7380    }
 381
 382    #endregion
 383
 384    #region Capacity Management
 385
 386    /// <summary>
 387    /// Ensures that the hash set is resized when the current load factor exceeds the predefined threshold.
 388    /// </summary>
 389    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 390    private void CheckLoadThreshold()
 213522391    {
 213522392        if ((uint)_count >= _nextResizeCount)
 35393            Resize(_entries.Length * _adaptiveResizeFactor);
 213522394    }
 395
 396    /// <summary>
 397    /// Ensures there is enough room to add a batch of items without repeatedly checking the load threshold.
 398    /// </summary>
 399    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 400    private void EnsureCapacityForAddRange(int incomingCount)
 2401    {
 2402        if (incomingCount <= 0)
 0403            return;
 404
 2405        long requiredCount = (long)_count + incomingCount;
 2406        if (requiredCount > int.MaxValue)
 0407            throw new InvalidOperationException("The collection is too large.");
 408
 2409        double minimumCapacity = Math.Ceiling(requiredCount / (double)_LoadFactorThreshold);
 2410        EnsureCapacity(minimumCapacity >= int.MaxValue ? int.MaxValue : (int)minimumCapacity);
 2411    }
 412
 413    /// <summary>
 414    /// Ensures that the set can hold up to the specified number of elements without resizing.
 415    /// </summary>
 416    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 417    public void EnsureCapacity(int capacity)
 4418    {
 4419        capacity = SwiftHashTools.NextPowerOfTwo(capacity);  // Capacity must be a power of 2 for proper masking
 4420        if (capacity > _entries.Length)
 2421            Resize(capacity);
 4422    }
 423
 424    /// <summary>
 425    /// Resizes the hash set to the specified capacity, redistributing all entries to maintain efficiency.
 426    /// </summary>
 427    /// <param name="newSize"></param>
 428    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 429    private void Resize(int newSize)
 37430    {
 37431        Entry[] newEntries = new Entry[newSize];
 37432        int newMask = newSize - 1;
 433
 37434        int lastIndex = 0;
 184522435        for (uint i = 0; i <= (uint)_lastIndex; i++)
 92224436        {
 92224437            if (_entries[i].IsUsed)
 85668438            {
 85668439                ref Entry oldEntry = ref _entries[i];
 85668440                int newIndex = oldEntry.HashCode & newMask;
 441                // If current entry not available, perform Quadratic probing to find the next available entry
 85668442                int step = 1;
 90635443                while (newEntries[newIndex].IsUsed)
 4967444                {
 4967445                    newIndex = (newIndex + step * step) & newMask;
 4967446                    step++;
 4967447                }
 85668448                newEntries[newIndex] = oldEntry;
 134240449                if (newIndex > lastIndex) lastIndex = newIndex;
 85668450            }
 92224451        }
 452
 37453        _lastIndex = lastIndex;
 454
 37455        CalculateAdaptiveResizeFactors(newSize);
 456
 37457        _entries = newEntries;
 37458        _entryMask = newMask;
 459
 37460        _version++;
 37461    }
 462
 463    /// <summary>
 464    /// Sets the capacity of a <see cref="SwiftHashSet{T}"/> to the actual
 465    /// number of elements it contains, rounded up to a nearby next power of 2 value.
 466    /// </summary>
 467    public void TrimExcess()
 1468    {
 1469        int newSize = _count <= DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(_count);
 1470        if (newSize >= _entries.Length) return;
 471
 1472        Entry[] newEntries = new Entry[newSize];
 1473        int newMask = newSize - 1;
 474
 1475        int lastIndex = 0;
 26476        for (int i = 0; i <= (uint)_lastIndex; i++)
 12477        {
 12478            if (_entries[i].IsUsed)
 12479            {
 12480                ref Entry oldEntry = ref _entries[i];
 12481                int newIndex = oldEntry.HashCode & newMask;
 482                // If current entry not available, perform quadratic probing to find the next available entry
 12483                int step = 1;
 12484                while (newEntries[newIndex].IsUsed)
 0485                {
 0486                    newIndex = (newIndex + step * step) & newMask;
 0487                    step++;
 0488                }
 12489                newEntries[newIndex] = oldEntry;
 23490                if (newIndex > lastIndex) lastIndex = newIndex;
 12491            }
 12492        }
 493
 1494        _lastIndex = lastIndex;
 495
 1496        CalculateAdaptiveResizeFactors(newSize);
 497
 1498        _entryMask = newMask;
 1499        _entries = newEntries;
 500
 1501        _version++;
 1502    }
 503
 504    /// <summary>
 505    ///  Updates adaptive resize parameters based on the current fill rate to balance memory usage and performance.
 506    /// </summary>
 507    /// <param name="newSize"></param>
 508    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 509    private void CalculateAdaptiveResizeFactors(int newSize)
 38510    {
 511        // Calculate current fill rate and update moving average
 38512        double currentFillRate = (double)_count / newSize;
 38513        _movingFillRate = _movingFillRate == 0 ? currentFillRate : (_movingFillRate * 0.7 + currentFillRate * 0.3);
 514
 38515        if (_movingFillRate > 0.3f)
 2516            _adaptiveResizeFactor = 2; // Growth stabilizing
 36517        else if (_movingFillRate < 0.28f)
 36518            _adaptiveResizeFactor = 4; // Rapid growth
 519
 520        // Reset the resize threshold based on the new size
 38521        _nextResizeCount = (uint)(newSize * _LoadFactorThreshold);
 38522    }
 523
 524    #endregion
 525
 526    #region Utility Methods
 527
 528    /// <summary>
 529    /// Initializes the hash set with a given capacity, ensuring it starts with an optimal internal structure.
 530    /// </summary>
 531    /// <param name="capacity"></param>
 532    /// <param name="comparer"></param>
 533    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 534    private void Initialize(int capacity, IEqualityComparer<T> comparer = null)
 109535    {
 109536        _comparer = SwiftHashTools.GetDefaultEqualityComparer(comparer);
 537
 109538        int size = capacity < DefaultCapacity ? DefaultCapacity : SwiftHashTools.NextPowerOfTwo(capacity);
 109539        _entries = new Entry[size];
 109540        _entryMask = size - 1;
 541
 109542        _nextResizeCount = (uint)(size * _LoadFactorThreshold);
 109543        _adaptiveResizeFactor = 4; // start agressive
 109544        _movingFillRate = 0.0;
 109545    }
 546
 547    /// <summary>
 548    /// Determines whether the set contains the specified element.
 549    /// </summary>
 550    /// <param name="item">The element to locate in the set.</param>
 551    /// <returns>
 552    /// True if the set contains the specified element; otherwise, false.
 553    /// </returns>
 554    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 1237555    public bool Contains(T item) => FindEntry(item) >= 0;
 556
 557    /// <summary>
 558    /// Determines whether the <see cref="SwiftHashSet{T}"/> contains an element that matches the conditions defined by 
 559    /// </summary>
 560    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 561    /// <returns><c>true</c> if the <see cref="SwiftHashSet{T}"/> contains one or more elements that match the specified
 562    public bool Exists(Predicate<T> match)
 3563    {
 3564        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 565
 16566        for (int i = 0; i <= _lastIndex; i++)
 7567        {
 7568            if (_entries[i].IsUsed && match(_entries[i].Value))
 1569                return true;
 6570        }
 571
 1572        return false;
 2573    }
 574
 575    /// <summary>
 576    /// Searches for an element that matches the conditions defined by the specified predicate, and returns the first ma
 577    /// </summary>
 578    /// <param name="match">The predicate that defines the conditions of the element to search for.</param>
 579    /// <returns>The first element that matches the conditions defined by the specified predicate, if found; otherwise, 
 580    public T Find(Predicate<T> match)
 2581    {
 2582        SwiftThrowHelper.ThrowIfNull(match, nameof(match));
 583
 16584        for (int i = 0; i <= _lastIndex; i++)
 7585        {
 7586            if (_entries[i].IsUsed && match(_entries[i].Value))
 1587                return _entries[i].Value;
 6588        }
 589
 1590        return default;
 2591    }
 592
 593    /// <summary>
 594    /// Searches the set for a given value and returns the equal value it finds, if any.
 595    /// </summary>
 596    public bool TryGetValue(T expected, out T actual)
 2597    {
 2598        int index = FindEntry(expected);
 2599        if (index >= 0)
 1600        {
 1601            actual = _entries[index].Value;
 1602            return true;
 603        }
 1604        actual = default;
 1605        return false;
 2606    }
 607
 608    /// <summary>
 609    /// Copies the elements of the set to an array, starting at the specified array index.
 610    /// </summary>
 611    public void CopyTo(T[] array, int arrayIndex)
 11612    {
 11613        SwiftThrowHelper.ThrowIfNull(array, nameof(array));
 12614        if ((uint)arrayIndex > array.Length) throw new ArgumentOutOfRangeException(nameof(arrayIndex));
 9615        if (array.Length - arrayIndex < _count) throw new InvalidOperationException("The array is not large enough to ho
 616
 92617        for (uint i = 0; i <= (uint)_lastIndex; i++)
 39618        {
 39619            if (_entries[i].IsUsed)
 28620                array[arrayIndex++] = _entries[i].Value;
 39621        }
 7622    }
 623
 624    /// <summary>
 625    /// Switches the hash set's comparer and rehashes all entries
 626    /// using the new comparer to redistribute them across <see cref="_entries"/>.
 627    /// </summary>
 628    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 629    public void SetComparer(IEqualityComparer<T> comparer = null)
 3630    {
 3631        SwiftThrowHelper.ThrowIfNull(comparer, nameof(comparer));
 3632        if (ReferenceEquals(comparer, _comparer))
 0633            return;
 634
 3635        _comparer = comparer;
 3636        RehashEntries();
 3637    }
 638
 639    /// <summary>
 640    /// Replaces the hash set's comparer with a randomized comparer to mitigate high collision rates.
 641    /// </summary>
 642    private void SwitchToRandomizedComparer()
 1643    {
 1644        if (SwiftHashTools.IsWellKnownEqualityComparer(_comparer))
 1645            _comparer = (IEqualityComparer<T>)SwiftHashTools.GetSwiftEqualityComparer(_comparer);
 0646        else return; // nothing to do here
 647
 1648        RehashEntries();
 1649        _maxStepCount = 0;
 650
 1651        _version++;
 1652    }
 653
 654    /// <summary>
 655    /// Reconstructs the internal entry structure to align with updated hash codes, ensuring efficient access and storag
 656    /// </summary>
 657    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 658    private void RehashEntries()
 4659    {
 4660        Entry[] newEntries = new Entry[_entries.Length];
 4661        int newMask = newEntries.Length - 1;
 662
 4663        int lastIndex = 0;
 584664        for (uint i = 0; i <= (uint)_lastIndex; i++)
 288665        {
 288666            if (_entries[i].IsUsed)
 101667            {
 101668                ref Entry oldEntry = ref _entries[i];
 101669                oldEntry.HashCode = _comparer.GetHashCode(oldEntry.Value) & 0x7FFFFFFF;
 101670                int newIndex = oldEntry.HashCode & newMask;
 101671                int step = 1;
 123672                while (newEntries[newIndex].IsUsed)
 22673                {
 22674                    newIndex = (newIndex + step * step) & newMask; // Quadratic probing
 22675                    step++;
 22676                }
 101677                newEntries[newIndex] = _entries[i];
 122678                if (newIndex > lastIndex) lastIndex = newIndex;
 101679            }
 288680        }
 681
 4682        _lastIndex = lastIndex;
 683
 4684        _entryMask = newMask;
 4685        _entries = newEntries;
 686
 4687        _version++;
 4688    }
 689
 690    /// <summary>
 691    /// Searches for an entry in the hash set by following its probing sequence, returning its index if found.
 692    /// </summary>
 693    /// <param name="item"></param>
 694    /// <returns></returns>
 695    [MethodImpl(MethodImplOptions.AggressiveInlining)]
 696    private int FindEntry(T item)
 1241697    {
 1242698        if (item == null) return -1;
 699
 1240700        int hashCode = _comparer.GetHashCode(item) & 0x7FFFFFFF;
 1240701        int entryIndex = hashCode & _entryMask;
 702
 1240703        int step = 0;
 6722704        while ((uint)step <= (uint)_lastIndex)
 6719705        {
 6719706            ref Entry entry = ref _entries[entryIndex];
 707            // Stop probing if an unused entry is found (not deleted)
 6719708            if (!entry.IsUsed && entry.HashCode != -1)
 522709                return -1;
 6197710            if (entry.IsUsed && entry.HashCode == hashCode && _comparer.Equals(entry.Value, item))
 715711                return entryIndex; // Match found
 712
 713            // Perform quadratic probing to see if maybe the entry was shifted.
 5482714            step++;
 5482715            entryIndex = (entryIndex + step * step) & _entryMask;
 716
 5482717        }
 3718        return -1; // Item not found, full loop completed
 1241719    }
 720
 721    #endregion
 722
 723    #region Enumerators
 724
 725    /// <summary>
 726    /// Returns an enumerator that iterates through the set.
 727    /// </summary>
 29728    public SwiftHashSetEnumerator GetEnumerator() => new SwiftHashSetEnumerator(this);
 12729    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
 1730    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 731
 732    /// <summary>
 733    /// Provides an enumerator for iterating through the elements of the hash set, ensuring consistency during enumerati
 734    /// </summary>
 735    public struct SwiftHashSetEnumerator : IEnumerator<T>, IEnumerator, IDisposable
 736    {
 737        private readonly SwiftHashSet<T> _set;
 738        private readonly Entry[] _entries;
 739        private readonly uint _version;
 740        private int _index;
 741        private T _current;
 742
 743        internal SwiftHashSetEnumerator(SwiftHashSet<T> set)
 29744        {
 29745            _set = set;
 29746            _version = set._version;
 29747            _entries = set._entries; // Cache the entry array
 29748            _index = -1;
 29749            _current = default;
 29750        }
 751
 57752        public readonly T Current => _current;
 753
 754        readonly object IEnumerator.Current
 755        {
 756            get
 1757            {
 1758                if (_index > (uint)_set._lastIndex) throw new InvalidOperationException("Bad enumeration");
 1759                return _current;
 1760            }
 761        }
 762
 763        public bool MoveNext()
 84764        {
 84765            if (_version != _set._version)
 1766                throw new InvalidOperationException("Collection was modified during enumeration.");
 767
 83768            uint last = (uint)_set._lastIndex;
 124769            while (++_index <= last)
 99770            {
 99771                if (_entries[_index].IsUsed)
 58772                {
 58773                    _current = _entries[_index].Value;
 58774                    return true;
 775                }
 41776            }
 777
 25778            _current = default;
 25779            return false;
 83780        }
 781
 782        public void Reset()
 1783        {
 1784            if (_version != _set._version)
 0785                throw new InvalidOperationException("Collection was modified during enumeration.");
 786
 1787            _index = -1;
 1788            _current = default;
 1789        }
 790
 52791        public readonly void Dispose() { }
 792    }
 793
 794    #endregion
 795
 796    #region ISet<T> Implementations
 797
 798    public void ExceptWith(IEnumerable<T> other)
 1799    {
 1800        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 801
 1802        if (ReferenceEquals(this, other))
 0803        {
 0804            Clear();
 0805            return;
 806        }
 807
 1808        var otherSet = new SwiftHashSet<T>(other, _comparer);
 809
 9810        foreach (var item in otherSet)
 3811            Remove(item);
 1812    }
 813
 814    public void IntersectWith(IEnumerable<T> other)
 1815    {
 1816        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 817
 1818        if (ReferenceEquals(this, other))
 0819            return;
 820
 1821        var otherSet = new SwiftHashSet<T>(other, _comparer);
 822
 12823        for (int i = 0; i <= _lastIndex; i++)
 5824        {
 5825            if (_entries[i].IsUsed)
 4826            {
 4827                var value = _entries[i].Value;
 4828                if (!otherSet.Contains(value))
 2829                    Remove(value);
 4830            }
 5831        }
 1832    }
 833
 834    public bool IsProperSubsetOf(IEnumerable<T> other)
 2835    {
 2836        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 837
 2838        var otherSet = new SwiftHashSet<T>(other, _comparer);
 839
 2840        if (Count >= otherSet.Count)
 1841            return false;
 842
 8843        for (int i = 0; i <= _lastIndex; i++)
 3844            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 0845                return false;
 846
 1847        return true;
 2848    }
 849
 850    public bool IsProperSupersetOf(IEnumerable<T> other)
 2851    {
 2852        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 853
 2854        var otherSet = new SwiftHashSet<T>(other, _comparer);
 855
 2856        if (Count <= otherSet.Count)
 1857            return false;
 858
 5859        foreach (var item in otherSet)
 1860            if (!Contains(item))
 0861                return false;
 862
 1863        return true;
 2864    }
 865
 866    public bool IsSubsetOf(IEnumerable<T> other)
 2867    {
 2868        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 869
 2870        var otherSet = new SwiftHashSet<T>(other, _comparer);
 871
 2872        if (otherSet.Count < Count)
 1873            return false;
 874
 8875        for (int i = 0; i <= _lastIndex; i++)
 3876            if (_entries[i].IsUsed && !otherSet.Contains(_entries[i].Value))
 0877                return false;
 878
 1879        return true;
 2880    }
 881
 882    public bool IsSupersetOf(IEnumerable<T> other)
 2883    {
 2884        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 885
 15886        foreach (var item in other)
 5887        {
 5888            if (!Contains(item))
 1889                return false;
 4890        }
 891
 1892        return true;
 2893    }
 894
 895    public bool Overlaps(IEnumerable<T> other)
 2896    {
 2897        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 898
 11899        foreach (var item in other)
 3900            if (Contains(item))
 1901                return true;
 902
 1903        return false;
 2904    }
 905
 906    public bool SetEquals(IEnumerable<T> other)
 5907    {
 5908        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 909
 5910        var otherSet = new SwiftHashSet<T>(other, _comparer);
 911
 5912        if (otherSet.Count != Count)
 0913            return false;
 914
 50915        foreach (var item in otherSet)
 18916            if (!Contains(item))
 1917                return false;
 918
 4919        return true;
 5920    }
 921
 922    public void SymmetricExceptWith(IEnumerable<T> other)
 2923    {
 2924        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 925
 2926        if (ReferenceEquals(this, other))
 1927        {
 1928            Clear();
 1929            return;
 930        }
 931
 1932        var otherSet = new SwiftHashSet<T>(other, _comparer);
 933
 7934        foreach (var item in otherSet)
 2935        {
 2936            if (!Remove(item))
 1937                Add(item);
 2938        }
 2939    }
 940
 941    public void UnionWith(IEnumerable<T> other)
 1942    {
 1943        SwiftThrowHelper.ThrowIfNull(other, nameof(other));
 944
 7945        foreach (var item in other)
 2946            Add(item);
 1947    }
 948
 949    #endregion
 950}
Generated by: ReportGenerator 5.5.4.0
04/03/2026 - 18:03:54
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>)
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>)