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

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 в это дерево будет выглядеть следующим образом:

Quad Tree Diagram http://episerversucks.com/upload/Diagram1111.png

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

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

Answer 1

[Edit - Измененный ответ, чтобы отразить замечания @gradbot и] @ Брайан

Вы говорите, что вы редко будете иметь больше, чем 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 2

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

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

Answer 3

Обратите внимание, что в 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)