PooledDictionary get fails with ValueTuple key

[jtmueller]

Describe the bug Lookups fail in a PooledDictionary<(int, int), string> but succeed in a Dictionary<(int, int), string>.

To Reproduce

class Program
{
    private static void PooledTest()
    {
        var dict = new PooledDictionary<(int, int), string>
        {
            { (1, 0), "1,0" },
            { (2, 0), "2,0" },
            { (0, 1), "0,1" },
            { (0, 2), "0,2" }
        };

        bool found1 = dict.TryGetValue((1, 0), out var _);
        bool found2 = dict.TryGetValue((2, 0), out var _);
        bool found3 = dict.TryGetValue((0, 1), out var _);
        bool found4 = dict.TryGetValue((0, 2), out var _);

        Console.WriteLine("PooledDictionary: {0}, {1}, {2}, {3}", found1, found2, found3, found4);
    }

    private static void DictTest()
    {
        var dict = new Dictionary<(int, int), string>
        {
            { (1, 0), "1,0" },
            { (2, 0), "2,0" },
            { (0, 1), "0,1" },
            { (0, 2), "0,2" }
        };

        bool found1 = dict.TryGetValue((1, 0), out var _);
        bool found2 = dict.TryGetValue((2, 0), out var _);
        bool found3 = dict.TryGetValue((0, 1), out var _);
        bool found4 = dict.TryGetValue((0, 2), out var _);

        Console.WriteLine("Dictionary: {0}, {1}, {2}, {3}", found1, found2, found3, found4);
    }

    static void Main(string[] args)
    {
        DictTest();
        PooledTest();
    }
}

Expected behavior

Dictionary: True, True, True, True
PooledDictionary: False, False, False, True

We should get the same results from both dictionary types, without having to specify custom comparers.

[jtmueller]

This appears to be more serious than I previously thought. It's not specific to ValueTuple keys. Instead, it appears to be any time there is more than 1 and less than 8 items in the dictionary, the lookup fails.

[jtmueller]

The cause of this bug was an optimization I put into Resize: In this scenario, we're going from a capacity of 3 to a capacity of 7, but the underlying array we got from the ArrayPool is actually a 16-element array. In an attempt to short-circuit the "allocate new array, copy everything, and sort the entries into the new set of buckets" code, I failed to do the "sort the entries into the new set of buckets" part.

Revised code skips over the "allocate new arrays and copy everything" part when the underlying array is large enough for the new capacity, but it now correctly sorts the entries into the new set of buckets, so lookups succeed when they should.