[Suggestion]Specialized Dictionary<ReadOnlyMemory<TKey>,TValue> with first class ReadOnlySpan<TKey> support

[Pheubel]

Parsing tokens from a string with string.split and a dictionary causes allocations.
These allocations can be avoided by handling the token string as a span and splitting the tokens and using them for dictionary look-ups.

Proposed API

A dictionary based on Dictionary<TKey,TValue> but with additional functions for first class ReadOnlySpan support.

[DebuggerDisplay("Count = {Count}")]
public class MemoryDictionary<TKey, TValue> : IDictionary<ReadOnlyMemory<TKey>, TValue>, IDictionary, IReadOnlyDictionary<ReadOnlyMemory<TKey>, TValue>
    where TKey : notnull, IEquatable<TKey>
{
    private int[] _buckets;
    private Entry[] _entries;
    private int _count;
    private int _freeList;
    private int _freeCount;
    private int _version;
    private IMemoryEqualityComparer<TKey> _comparer;
    private KeyCollection _keys;
    private ValueCollection _values;
    private const int StartOfFreeList = -3;

    public MemoryDictionary();
    public MemoryDictionary(int capacity);
    public MemoryDictionary(IMemoryEqualityComparer<TKey> comparer);
    public MemoryDictionary(int capacity, IMemoryEqualityComparer<TKey> comparer);
    public MemoryDictionary(IDictionary<ReadOnlyMemory<TKey>, TValue> dictionary);
    public MemoryDictionary(IDictionary<ReadOnlyMemory<TKey>, TValue> dictionary, IMemoryEqualityComparer<TKey> comparer);
    public MemoryDictionary(IEnumerable<KeyValuePair<ReadOnlyMemory<TKey>, TValue>> collection);
    public MemoryDictionary(IEnumerable<KeyValuePair<ReadOnlyMemory<TKey>, TValue>> collection, IMemoryEqualityComparer<TKey> comparer);

    public int Count { get; }
    public KeyCollection Keys { get; }
    public ValueCollection Values { get; }
    public IMemoryEqualityComparer<TKey> Comparer { get; }

    public TValue this[ReadOnlyMemory<TKey> key] { get; set; }

    public TValue Get(ReadOnlyMemory<TKey> key);
    public TValue GetWithSpan(ReadOnlySpan<TKey> key);
    public bool TryGetValue(ReadOnlyMemory<TKey> key, out TValue value);
    public bool TryGetValueWithSpan(ReadOnlySpan<TKey> key, [MaybeNullWhen(false)] out TValue value);

    public Enumerator GetEnumerator();

    public void Add(ReadOnlyMemory<TKey> key, TValue value);
    public bool TryAdd(ReadOnlyMemory<TKey> key, TValue value);

    public bool Remove(ReadOnlyMemory<TKey> key);
    public bool Remove(ReadOnlyMemory<TKey> key, out TValue value) => RemoveWithSpan(key.Span, out value);
    public bool RemoveWithSpan(ReadOnlySpan<TKey> key);
    public bool RemoveWithSpan(ReadOnlySpan<TKey> key, [MaybeNullWhen(false)] out TValue value);

    public void Clear();

    public bool ContainsKey(ReadOnlyMemory<TKey> key);
    public bool ContainsValue(TValue value);

    private int FindEntry(ReadOnlyMemory<TKey> key);
    private int FindEntry(ReadOnlySpan<TKey> key);

    private bool TryInsert(ReadOnlyMemory<TKey> key, TValue value, InsertionBehavior behavior);

    private void CopyTo(KeyValuePair<ReadOnlyMemory<TKey>, TValue>[] array, int index);
    private int Initialize(int capacity);

    public int EnsureCapacity(int capacity);
    private void Resize();
    private void Resize(int newSize, bool forceNewHashCodes);
    public void TrimExcess();
    public void TrimExcess(int capacity);
            
    private static bool IsCompatibleKey(object key);

    ICollection<ReadOnlyMemory<TKey>> IDictionary<ReadOnlyMemory<TKey>, TValue>.Keys { get; }
    IEnumerable<ReadOnlyMemory<TKey>> IReadOnlyDictionary<ReadOnlyMemory<TKey>, TValue>.Keys { get; }
    ICollection IDictionary.Keys { get; }

    ICollection<TValue> IDictionary<ReadOnlyMemory<TKey>, TValue>.Values { get; }
    IEnumerable<TValue> IReadOnlyDictionary<ReadOnlyMemory<TKey>, TValue>.Values { get; }
    ICollection IDictionary.Values { get; }

    object IDictionary.this[object key] { get; set; }

    IEnumerator IEnumerable.GetEnumerator();
    IDictionaryEnumerator IDictionary.GetEnumerator();

    void ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.Add(KeyValuePair<ReadOnlyMemory<TKey>, TValue> keyValuePair);
    void IDictionary.Add(object key, object value);
    bool ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.Contains(KeyValuePair<ReadOnlyMemory<TKey>, TValue> keyValuePair);
    bool IDictionary.Contains(object key);
    bool ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.Remove(KeyValuePair<ReadOnlyMemory<TKey>, TValue> keyValuePair);
    void IDictionary.Remove(object key);

    IEnumerator<KeyValuePair<ReadOnlyMemory<TKey>, TValue>> IEnumerable<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.GetEnumerator();

    bool ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.IsReadOnly { get; }
    bool IDictionary.IsReadOnly { get; }

    bool IDictionary.IsFixedSize { get; }

    void ICollection.CopyTo(Array array, int index);
    void ICollection<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>.CopyTo(KeyValuePair<ReadOnlyMemory<TKey>, TValue>[] array, int index);
    
    bool ICollection.IsSynchronized { get; }
    object ICollection.SyncRoot { get; }
    
    private enum InsertionBehavior : byte
    {
        None = 0,
        OverwriteExisting = 1,
        ThrowOnExisting = 2
    }

    private struct Entry
    {
        public int next;
        public uint hashCode;
        public ReadOnlyMemory<TKey> key;
        public TValue value;
    }

    public struct Enumerator : IEnumerator<KeyValuePair<ReadOnlyMemory<TKey>, TValue>>,
        IDictionaryEnumerator
    {
        private readonly MemoryDictionary<TKey, TValue> _dictionary;
        private readonly int _version;
        private int _index;
        private KeyValuePair<ReadOnlyMemory<TKey>, TValue> _current;
        private readonly int _getEnumeratorRetType;  // What should Enumerator.Current return

        internal const int DictEntry = 1;
        internal const int KeyValuePair = 2;

        internal Enumerator(MemoryDictionary<TKey, TValue> dictionary, int getEnumeratorRetType);

        public bool MoveNext();

        public KeyValuePair<ReadOnlyMemory<TKey>, TValue> Current { get; }

        public void Dispose();

        object IEnumerator.Current { get; }

        void IEnumerator.Reset();

        DictionaryEntry IDictionaryEnumerator.Entry { get; }

        object IDictionaryEnumerator.Key { get; }

        object IDictionaryEnumerator.Value { get; }
    }

    [DebuggerDisplay("Count = {Count}")]
    public sealed class KeyCollection : ICollection<ReadOnlyMemory<TKey>>, ICollection, IReadOnlyCollection<ReadOnlyMemory<TKey>>
    {
        private MemoryDictionary<TKey, TValue> _dictionary;

        public KeyCollection(MemoryDictionary<TKey, TValue> dictionary);

        public Enumerator GetEnumerator();

        public void CopyTo(ReadOnlyMemory<TKey>[] array, int index);

        public int Count { get; }

        bool ICollection<ReadOnlyMemory<TKey>>.IsReadOnly { get; }

        void ICollection<ReadOnlyMemory<TKey>>.Add(ReadOnlyMemory<TKey> item);

        void ICollection<ReadOnlyMemory<TKey>>.Clear();

        bool ICollection<ReadOnlyMemory<TKey>>.Contains(ReadOnlyMemory<TKey> item);

        bool ICollection<ReadOnlyMemory<TKey>>.Remove(ReadOnlyMemory<TKey> item);

        IEnumerator<ReadOnlyMemory<TKey>> IEnumerable<ReadOnlyMemory<TKey>>.GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator();

        void ICollection.CopyTo(Array array, int index);

        bool ICollection.IsSynchronized { get; }

        object ICollection.SyncRoot { get; }

        public struct Enumerator : IEnumerator<ReadOnlyMemory<TKey>>, IEnumerator
        {
            private readonly MemoryDictionary<TKey, TValue> _dictionary;
            private int _index;
            private readonly int _version;
            private ReadOnlyMemory<TKey> _currentKey;

            internal Enumerator(MemoryDictionary<TKey, TValue> dictionary);

            public void Dispose();

            public bool MoveNext();

            public ReadOnlyMemory<TKey> Current { get; }

            object IEnumerator.Current { get; }

            void IEnumerator.Reset();
        }
    }

    [DebuggerDisplay("Count = {Count}")]
    public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue>
    {
        private MemoryDictionary<TKey, TValue> _dictionary;

        public ValueCollection(MemoryDictionary<TKey, TValue> dictionary);

        public Enumerator GetEnumerator();

        public void CopyTo(TValue[] array, int index);

        public int Count { get; }

        bool ICollection<TValue>.IsReadOnly { get; }

        void ICollection<TValue>.Add(TValue item);

        bool ICollection<TValue>.Remove(TValue item);

        void ICollection<TValue>.Clear();

        bool ICollection<TValue>.Contains(TValue item);

        IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator();

        void ICollection.CopyTo(Array array, int index);

        bool ICollection.IsSynchronized { get; }

        object ICollection.SyncRoot { get; }

        public struct Enumerator : IEnumerator<TValue>, IEnumerator
        {
            private readonly MemoryDictionary<TKey, TValue> _dictionary;
            private int _index;
            private readonly int _version;
            private TValue _currentValue;

            internal Enumerator(MemoryDictionary<TKey, TValue> dictionary);

            public void Dispose();

            public bool MoveNext();

            public TValue Current { get; }

            object IEnumerator.Current { get; }

            void IEnumerator.Reset();
        }
    }
}

For equality comparing keys with spans the normal IEqualityComparer has to be extended

public interface IMemoryEqualityComparer<T> : IEqualityComparer<ReadOnlyMemory<T>>
{
    bool Equals(ReadOnlyMemory<T> x, ReadOnlySpan<T> y);
    int GetHashCode(ReadOnlySpan<T> span);
}

The default MemoryEqualityComparer would look like this

public class MemoryEqualityComparer<T> : IMemoryEqualityComparer<T>
    where T : IEquatable<T>
{
    public static MemoryEqualityComparer<T> Default { get; }

    private MemoryEqualityComparer();

    public bool Equals(ReadOnlyMemory<T> x, ReadOnlyMemory<T> y);
    public bool Equals(ReadOnlyMemory<T> x, ReadOnlySpan<T> y);

    public int GetHashCode(ReadOnlyMemory<T> memory);
    public int GetHashCode(ReadOnlySpan<T> span);
}

example of usage:

[Flags]
public enum ScopeField
{
    Identity = 1 << 0,
    IdentityEmail = Identity | (1 << 1),
    IdentityMemberships = Identity | (1 << 2)
}

private readonly static Dictionary<ReadOnlyMemory<char>, ScopeField> _mapping = new Dictionary<ReadOnlyMemory<char>, ScopeField>()
{
    ["identity".AsMemory()] = ScopeField.Identity,
    ["identity[email]".AsMemory()] = ScopeField.IdentityEmail,
    ["identity.memberships".AsMemory()] = ScopeField.IdentityMemberships
};

public static ScopeField ParseScopeStringWithSpan(string scopeString)
{
    ScopeField scopeValue = 0;
    var scopeSpan = scopeString.AsSpan();

    while (scopeSpan.Length != 0)
    {
        int sliceIndex = scopeSpan.IndexOf(' ');
        if (sliceIndex != -1)
        {
            if (sliceIndex == 0)
            { 
                scopeSpan = scopeSpan.Slice(1);
                continue;
            }

            scopeValue |= _mapping.GetWithSpan(scopeSpan.Slice(0, sliceIndex));
            scopeSpan = scopeSpan.Slice(sliceIndex + 1);
        }
        else
        {
            scopeValue |= _mapping.GetWithSpan(scopeSpan);
            break;
        }
    }

    return scopeValue;
}

[scalablecory]

Related: https://github.com/dotnet/corefx/issues/31942

[GrabYourPitchforks]

This API design needs to be thought through (including figuring out the lifetime of the Memory<T> once it is in the dictionary). Maybe we can start a prototype in corefxlab: https://github.com/dotnet/corefxlab