Как реализовать многоиндексный словарь?

В принципе, я хочу что-то вроде Dictionary < Tkey1, TKey2, TValue > , но не (как я видел здесь в другом вопросе) с ключами в AND, но в OR. Чтобы лучше объяснить: я хочу, чтобы найти элемент в словаре, предоставляя только один из ключей, а не оба.

Я также думаю, что мы должны рассмотреть вопрос о безопасности потоков и способности легко масштабироваться до словарей TKey2, TKeyN, TValue > решение...

Ответы

Ответ 1

Я бы использовал структуру данных с этими двумя словарями

Dictionary<TKey1, KeyValuePair<TKey2, TValue>> dict1;
Dictionary<TKey2, KeyValuePair<TKey1, TValue>> dict2;

Таким образом, если вам дано 1 ключ, у вас есть как значение, так и другой ключ, а также для простого удаления и обновления.

Ответ 2

Итак, вам нужен многоиндексный словарь, поддерживающий поиск на основе любого ключа и поддерживающий расширения для нескольких ключей?

Возможно, вы думаете о неправильной структуре данных, вместо этого попробуйте KD-Tree. Неизменяемое KD-дерево удовлетворяет требованиям безопасности потока.

KD-деревья имеют некоторые основные преимущества перед наивным подходом Dictionary{Key1, Dictionary{Key2, Value}}, а именно, что вы можете искать все поля на основе Key2 без знания Key1. Кроме того, KD-деревья позволяют вам искать ключи, которые находятся рядом с другим ключом. Например, сайты знакомств классифицируют людей на десятки групп (курильщик/некурящий, пол, религия, образ жизни, возраст, высота), а затем возвращают ближайших соседей по вашему запросу.

Здесь реализация С# и Java:

http://home.wlu.edu/~levys/software/kd/

Ответ 3

Я собираюсь выйти на конечность и выглядеть глупым, но вы можете просто свернуть свой собственный словарь на основе двух словарей. Сложно было бы писать (даже с запирающими механизмами для обеспечения безопасности потока). Я имею в виду, есть много примеров, где вы можете использовать индекс или ключ для доступа к коллекции. (Например, сеанс)

И наоборот, если ваши несколько индексов имеют один и тот же тип, вы можете просто добавить один и тот же элемент несколько раз.

Словарь будет поддерживать что-то с индексом GUID, а также простой индекс имени "Joe" - вы должны помнить, что нужно добавить элемент дважды.

Ответ 4

Вы можете просто использовать обычный словарь для этого и вставить значение дважды, один раз для каждого ключа. Для удаления вы удалите обе клавиши.

расквитаться:

  • Можно искать обе клавиши с одним поиском.
  • Новый код не нужен.
  • Масштабирует любое количество клавиш.

Downsides:

  • Защита от потери типа, если ключи имеют разные типы.
  • Невозможно перебрать (key1, key2, value) кортежи.
  • Значения появляются дважды, поэтому size() удваивается.

Ответ 5

Возможно, вариант:

Сделайте, как предлагает Джон Кугельман, просто добавьте элемент дважды в тот же словарь. Затем вы сохраняете второй словарь, который сопоставляет значения наборам ключей.

Когда вы добавляете ключ, значение par, вы просто добавляете его как обычно в первый словарь, а затем извлекаете набор ключей, принадлежащий этому значению, из второго словаря и добавляете ключ.

Dictionary<TKey, TValue> dict1;
Dictionary<TValue, ICollection<TKey>> dict2;

Удаление значения выполняется путем извлечения набора ключей из dict2 и удаления их один за другим из dict1.

Количество ключей - dict1.Count, а число значений - dict2.Count

Ответ 6

Рассматривали ли вы наличие двух словарей, по одному для каждого ключа? Добавление элемента добавит его в оба.

Удаление означает удаление из обоих словарей и требует наличия обоих ключей. Чтобы удалить только одним ключом, элемент должен будет сохранить оба ключа. Если он еще не удерживает обе клавиши, вы можете обернуть его в контейнерный объект, который содержит оба ключа и элемент.

Ответ 7

Два словаря, но не дублируйте элементы в каждом.

У вас будет словарь значений и ключевой словарь.

Когда вы вызываете свой метод add, вы создадите GUID и добавите его и ключ в словарь ключей.

Затем используйте GUID в качестве ключа к словарю значений.

Если вы хотите добавить два ключа, вы добавите еще один элемент в словарь ключей с тем же идентификатором GUID.

Конечно, это означает, что для каждого поиска требуется две проверки данных, но не более того, даже если у вас есть 50 ключей для одного и того же значения.

Найдите руководство на основе ключа из таблицы ключей, затем найдите данные на основе этого указателя в таблице значений.

Ответ 8

Я написал такой словарь и разместил его на мой блог. Это даст вам хороший API, как это:

DoubleKeyDictionary<int, string, string> books = new DoubleKeyDictionary<string, string, string>();
bookListEx.Add(1, "21/12/2009″, "Lord of the Rings - Fellowship of the Ring");

Вы также можете сделать "Равно" на двух словарях и для каждого из них.

Обратите внимание, что в коде есть хотя бы одна ошибка (как это было обнаружено в комментариях), и нет модульных тестов и т.д. Когда (да!) я получаю некоторое время, я обновляю код с помощью модульных тестов...

Ответ 10

Создайте простой класс для хранения Tkey1, TKey2, TValue, сделайте список из них и используйте LINQ для запроса такой структуры, будет вариант.