Minimal memory FixedTypeKeyHashtable

FixedTypeKeyHashtable.cs

using System;
using System.Buffers;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

// ReSharper disable LocalVariableHidesMember

//modified from http://neue.cc/2017/07/11_555.html
sealed class FixedTypeKeyHashtable<TValue>
{
    readonly KeyValuePair<Type, TValue>[] pairs;
    readonly int[] buckets;
    readonly int indexFor;

    public FixedTypeKeyHashtable(Dictionary<Type, TValue> dictionary, float loadFactor = 0.75f)
    {
        var initialCapacity = (int)(dictionary.Count / loadFactor);

        // make power of 2
        var capacity = 1;
        while (capacity < initialCapacity)
        {
            capacity <<= 1;
        }

        var indexFor = capacity - 1;
        var pairs = new KeyValuePair<Type, TValue>[dictionary.Count];
        var buckets = new int[capacity + 1];
        var tempArray = ArrayPool<int>.Shared.Rent(dictionary.Count + capacity);
        try
        {
            var bucketPositions = tempArray.AsSpan(0, dictionary.Count);
            var bucketCountUp = tempArray.AsSpan(dictionary.Count, capacity);
            bucketCountUp.Clear();
            int index = 0;
            foreach (var item in dictionary)
            {
                var hash = item.Key.GetHashCode() & indexFor;
                bucketPositions[index++] = hash;
            }

            foreach (var t in bucketPositions)
            {
                bucketCountUp[t]++;
            }

            var sum = 0;
            for (int i = 0; i < bucketCountUp.Length; i++)
            {
                sum += bucketCountUp[i];
                buckets[i + 1] = sum;
            }


            index = 0;
            foreach (var item in dictionary)
            {
                var hash = bucketPositions[index];
                var entry = buckets[hash] + (--bucketCountUp[hash]);
                pairs[entry] = item;
                index++;
            }

            this.buckets = buckets;
            this.indexFor = indexFor;
            this.pairs = pairs;
        }
        finally
        {
            ArrayPool<int>.Shared.Return(tempArray);
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool TryGetValue(Type type, out TValue value)
    {
        Unsafe.SkipInit(out value);
        var typeHash = type.GetHashCode();

        var index = typeHash & indexFor;
        var end = buckets[index + 1];
        index = buckets[index];

        var pairs = this.pairs;
        for (; index < end; index++)
        {
            var e = pairs[index];
            if (type == e.Key)
            {
                value = e.Value;
                return true;
            }
        }

        return false;
    }
}