Picking 'any' item from a HashSet is very slow - how to do this fast?

It seems that the HashSet class is not optimized for the scenario where its first item is repeatedly removed. The space reserved internally by this class is not reduced after each removal, and instead the corresponding slot is marked as empty. The enumerator of the class enumerates all the internal slots, and yields a value whenever it finds a non-empty slot. This can become extremely inefficient when the internal space of a HashSet has become sparsely populated. For example a HashSet that once hold 1,000,000 elements and has been reduced to a single element, must enumerate 1,000,000 slots before yielding the element stored in its single non-empty slot:

var set = new HashSet<int>(Enumerable.Range(1, 1_000_000));
set.ExceptWith(Enumerable.Range(1, 999_999));
var item = set.First(); // Very slow

This is a problem that is not easy to solve. One solution is to call the TrimExcess method after each batch of deletions. This method minimizes the space reserved internally by the class, by allocating a new array of slots, copying the items from the existing array to the new one, and finally discarding the old array. This is an expensive operation, so calling TrimExcess too frequently could become the new bottleneck of your app.

Another solution could be to use a third-party implementation that doesn't suffer from this problem. For example the Rock.Collections library contains an OrderedHashSet class that keeps the items in the order in which they are added. It achieves this by connecting the internal slots in a linked-list manner. The class can be enumerated not only in normal but also in reversed order. I didn't tested it, but most probably calling First should be an O(1) operation.

Below is a solution that uses reflection to trick the built-in enumerator into starting the enumeration of the slots from a random index, instead of the index 0. It offers acceptable performance, but it suffers from the known problems of reflection (overhead, forward compatibility etc). The static GetRandom method is located inside a generic static class, in order to cache the FieldInfo information separately for each type T.

public static class HashSetRandomizer<T>
{
    private static FieldInfo _lastIndexField;
    private static FieldInfo _indexField;
    private static ThreadLocal<Random> _random;

    static HashSetRandomizer()
    {
        const BindingFlags FLAGS = BindingFlags.NonPublic | BindingFlags.Instance;
        _lastIndexField = typeof(HashSet<T>).GetField("m_lastIndex", FLAGS) // Framework
            ?? typeof(HashSet<T>).GetField("_lastIndex", FLAGS); // Core
        _indexField = typeof(HashSet<T>.Enumerator).GetField("index", FLAGS) // Framework
            ?? typeof(HashSet<T>.Enumerator).GetField("_index", FLAGS); // Core
        _random = new ThreadLocal<Random>(() => new Random());
    }

    public static T GetRandom(HashSet<T> source, Random random = null)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        random = random ?? _random.Value;
        if (_lastIndexField == null)
            throw new NotSupportedException("FieldInfo lastIndex not found.");
        if (_indexField == null)
            throw new NotSupportedException("FieldInfo index not found.");
        if (source.Count > 0)
        {
            int lastIndex = (int)_lastIndexField.GetValue(source);
            if (lastIndex > 0)
            {
                var randomIndex = random.Next(0, lastIndex);
                using (var enumerator = source.GetEnumerator())
                {
                    _indexField.SetValue(enumerator, randomIndex);
                    if (enumerator.MoveNext()) return enumerator.Current;
                }
            }
            foreach (var item in source) return item; // Fallback
        }
        throw new InvalidOperationException("The source sequence is empty.");
    }
}

Usage example. Items are removed randomly from a HashSet, until the set is empty.

var set = new HashSet<int>(Enumerable.Range(1, 1_000_000));
while (set.Count > 0)
{
    var item = HashSetRandomizer<int>.GetRandom(set); // Fast
    set.Remove(item);
}

Removing the last few items is still quite slow, even with this approach.

Using First() all the time requires that the internal Enumerator struct is build all the time. But since it is not important which element you get you can retrieve the IEnumerator object only once and then keep read data from it. So it is basically a normal foreach loop over the HashSet you have to work with the entries.

To prevent any "Collection was modified" exceptions you must not remove the proceeded entry from the HashSet until your iteration is complete. So you can save the entries which has been proceeded and delete them afterwards. The source code might look like this:

HashSet<MyClass> hs /// approx 500,000 items

while(/* metadata based on what's been processed*/ ) // might be adjusted now
{    
    Set<MyClass> toDelete = new HashSet<MyClass>();
    while (MyClass entry in hs) // get Enumerator only once, then iterate normally
    {
        if(ShouldProcess(entry))
        {
            Process(entry);
            toDelete.Remove(entry);
        }
    }
    // finally delete them
    foreach (MyClass entry in toDelete)
    {
        hs.Remove(entry);
    }
}

As you iterate over the whole HashSet and not run your "metadata" check after each entry you might need to adjust your outer while loop due to the fact, that in one outer while loop iteration the whole HashSet is iterated (and entries aren't deleted immediately).