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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Вот реализация на C # и Java:

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

Answer 3

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

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

Словарь будет поддерживать что-то с индексом GUID, а также с простым индексом имени «Джо» - вы должны не забыть добавить элемент дважды.

Answer 4

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

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

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

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

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

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

Answer 5

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

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

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

Downsides:

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

Answer 6

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

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

Answer 7

Проверьте эту статью на CodeProject: http://www.codeproject.com/KB/recipes/multikey-dictionary.aspx

Это, безусловно, правильный способ создания многоключевого словаря;)

Answer 8

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

Answer 9

А как насчет мультииндексного контейнера , вдохновленного boost ??

Взгляните на CodeProject .

Answer 10

Я написал такой словарь и разместил его на моем блоге . Это даст вам хороший 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”); 

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

Обратите внимание, что в коде есть как минимум одна ошибка (как обнаружено в комментариях), нет юнит-тестов и т. Д. модульные тесты ...