Список значений в качестве ключей для карты

Question

У меня есть списки переменной длины, где каждый элемент может быть одним из четырех уникальных, которые мне нужно использовать в качестве ключей для другого объекта на карте. Предположим, что каждое значение может быть 0, 1, 2 или 3 (это не целое число в моем реальном коде, но намного проще объяснить таким образом), поэтому можно привести несколько примеров списков ключей:

[1, 0, 2, 3]
[3, 2, 1]
[1, 0, 0, 1, 1, 3]
[2, 3, 1, 1, 2]
[1, 2]

Итак, для повторения: каждый элемент в списке может быть 0, 1, 2 или 3, и в списке может быть любое количество элементов.

Мой первый подход состоял в том, чтобы попытаться хэшировать содержимое массива, используя встроенный GetHashCode () в .NET, чтобы объединить хеш каждого элемента. Но так как это вернуло бы int, мне пришлось бы иметь дело с коллизиями вручную (два равных значения int идентичны словарю).

Таким образом, мой второй подход состоял в том, чтобы использовать четырехугольное дерево, разбивая каждый элемент в списке на узел, который имеет четыре указателя (по одному на каждое возможное значение) на следующие четыре возможных значения (с корневым узлом, представляющим [] (пустой список), вставка [1, 0, 2] => Foo, [1, 3] => Bar и [1, 0] => Baz в это дерево будет выглядеть так:

Диаграмма дерева четырехугольников http://episerversucks.com/upload/Diagram1111.png

Серые узлы - это неиспользуемые указатели / узлы. Хотя я беспокоюсь о производительности этой установки, но не будет необходимости иметь дело с коллизиями хешей, и дерево не станет слишком глубоким (в большинстве случаев будут храниться списки с 2-6 элементами, редко более 6).

Есть ли какой-то другой магический способ хранения предметов со списками значений в качестве ключей, которые я пропустил?

Answer 1

Обратите внимание, что в F # структура данных Map может успешно использовать элементы list или array в качестве ключей; он использует структурное сравнение (а не хеш-код) для хранения вещей в постоянном дереве.

let myData = [
    [0;1;3], "foo"
    [1;2], "bar"
    [3;1;2;0;3], "qux"
    ]

let mutable m = Map.empty 
for k,v in myData do
    m <- Map.add k v m

printfn "%s" (Map.find [1;2] m)

Answer 2

[Редактировать - Изменен ответ для отражения комментариев @gradbot и @Brian]

Вы говорите, что у вас редко будет более 6 элементов. Если вы можете ограничить максимум 14 элементов, вы можете использовать GetHashCode(). Поскольку для хранения значения вам нужно всего 2 бита, 32 бита в int даст вам возможность создать уникальный хэш-код длиной до 14 элементов и учесть также значение 0.

int[] arr = new [] { 1, 2, 3, 0, 1, 2, 3 };
public override int GetHashCode()
{
    if(arr.Length > 14) throw new Exception("max elems is 14");
    int hash = 1; // start with 1 to take into account a heading 0
    foreach (int i in arr)
    {
        hash = hash << 2;
        hash += i;
    }
    return hash;
}

Если вы хотите сделать хеш обратимым, вам придется также использовать несколько битов для длины. И код может быть настроен так, чтобы разрешить 15 элементов, как упомянуто @ gradbot.

Answer 3

Если в списке редко более шести элементов и каждый элемент содержит только два бита информации, то я думаю, что структура, которую вы хотите для своих «списков ключей», называется «int». :)

Просто используйте, например, первые 4 бита, чтобы сказать, насколько «длинен» список ключей (0-14), и последние 28 (или меньше) битов для хранения фактического ключа. Затем используйте Dictionary<int,Blah>, где int - это представление списка ключей.