Коллекция предметов с двумя ключами

Question

Представьте себе такой сценарий: мне нужно манипулировать (добавлять, искать и удалять) элементы из списка объектов типа Book.

class Book{
 int Id {get; set;}
 string Title {get; set;}
 string Author {get; set;}
 int Year {get; set;}
 // more properties
}

Константы:

• Id должен быть уникальным в коллекции Books
• Title должен быть уникальным в коллекции Books

То, что у меня есть, Dictionary<int, Book>, в котором ключ Id и значение Book. Но в этом случае, если я хочу добавить новую книгу в словарь, я должен просмотреть все значения, чтобы проверить, является ли Title дублированным или нет.

Я начинаю думать о создании HashSet только для заголовков или о наличии второго словаря Dictionary<string, Book> с ключом Title.

Любое предложение Как справиться с этим сценарием?

Edit:

Как упомянул @David, я забыл сказать, что моя главная проблема здесь - это производительность. Я хочу быстрее найти объекты по Id и Title (O (1)).

Answer 1

Похоже, что и ID, и Name будут уникальными, то есть нельзя использовать один и тот же идентификатор дважды, независимо от того, использовалось ли уже имя. В противном случае мы получили бы dict[3], ссылаясь на два разных значения.

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

public class TwoKeyDictionary<TKey1, TKey2, TValue>
{
    public readonly List<TKey1> firstKeys  = new List<TKey1>();
    public readonly List<TKey2> secondKeys = new List<TKey2>();
    public readonly List<TValue> values    = new List<TValue>();


    public void Add(TKey1 key1, TKey2 key2, TValue value)
    {
        if (firstKeys.Contains(key1))  throw new ArgumentException();
        if (secondKeys.Contains(key2)) throw new ArgumentException();

        firstKeys.Add(key1);
        secondKeys.Add(key2);
        values.Add(value);
    }

    public void Remove(TKey1 key) => RemoveAll(firstKeys.IndexOf(key));
    public void Remove(TKey2 key) => RemoveAll(secondKeys.IndexOf(key));
    private void RemoveAll(int index)
    {
        if (index < 1) return;

        firstKeys.RemoveAt(index);
        secondKeys.RemoveAt(index);
        values.RemoveAt(index);
    }


    public TValue this[TKey1 key1]
    {
        get
        {
            int index = firstKeys.IndexOf(key1);
            if (index < 0) throw new IndexOutOfRangeException();

            return values[firstKeys.IndexOf(key1)];
        }
    }

    public TValue this[TKey2 key2]
    {
        get
        {
            int index = secondKeys.IndexOf(key2);
            if (index < 0) throw new IndexOutOfRangeException();

            return values[secondKeys.IndexOf(key2)];
        }
    }
}

И тогда вы можете использовать это так:

var twoDict = new TwoKeyDictionary<int, string, float>();
twoDict.Add(0, "a", 0.5f);
twoDict.Add(2, "b", 0.25f);

Console.WriteLine(twoDict[0]);     // Prints "0.5"
Console.WriteLine(twoDict[2]);     // Prints "0.25"
Console.WriteLine(twoDict["a"]);   // Prints "0.5"
Console.WriteLine(twoDict["b"]);   // Prints "0.25"

twoDict.Add(0, "d", 2);            // Throws exception: 0 has already been added, even though "d" hasn't
twoDict.Add(1, "a", 5);            // Throws exception: "a" has already been added, even though "1" hasn't

TwoKeyDictionary потребуется реализовать ICollection, IEnumerable и т. Д., Чтобы выполнить всю работу по поведению

Answer 2

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

public struct CompositeKey<T1, T2> : IEquatable<CompositeKey<T1, T2>>
{
    private static readonly EqualityComparer<T1> t1Comparer = EqualityComparer<T1>.Default;
    private static readonly EqualityComparer<T2> t2Comparer = EqualityComparer<T2>.Default;

    public T1 Key1;
    public T2 Key2;

    public CompositeKey(T1 key1, T2 key2)
    {
        Key1 = key1;
        Key2 = key2;
    }

    public override bool Equals(object obj) => obj is CompositeKey<T1, T2> && Equals((CompositeKey<T1, T2>)obj);

    public bool Equals(CompositeKey<T1, T2> other)
    {
        return t1Comparer.Equals(Key1, other.Key1)
            && t2Comparer.Equals(Key2, other.Key2);
    }

    public override int GetHashCode() => Key1.GetHashCode();
}

Таким образом, словарь работает на ведрах. Он помещает все ключи в сегменты на основе хеш-кода, сгенерированного GetHashCode(). Затем он ищет этот сегмент, используя цикл for Equals(). Идея состоит в том, что ведра должны быть как можно меньше (в идеале один предмет).

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

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

Если вы хотите использовать ValueTuple в качестве типа ключа, вы можете передать пользовательский компаратор в словарь для достижения того же эффекта.

public class CompositeValueTupleComparer<T1, T2> : IEqualityComparer<(T1, T2)>
{
    private static readonly EqualityComparer<T1> t1Comparer = EqualityComparer<T1>.Default;
    private static readonly EqualityComparer<T2> t2Comparer = EqualityComparer<T2>.Default;

    public bool Equals((T1, T2) x, (T1, T2) y) => 
        t1Comparer.Equals(x.Item1, y.Item1) && t2Comparer.Equals(x.Item2, y.Item2);

    public int GetHashCode((T1, T2) obj) => obj.Item1.GetHashCode();
}

new Dictionary<(int, string), Book>(new CompositeValueTupleComparer<int, string>());

Answer 3

Вы можете использовать Tuple в качестве ключа:

var collection = new Dictionary<Tuple<int, string>, Book> (...);
var key = new Tuple<int, string>(1, "David");  // <<-----------
if(!collection.ContainsKey(key))
    collection [key] = new Book(...);

Обратите внимание, что в Tuple встроены Equals () , чтобы сделать вашу жизнь проще.

---

Обновление:

@ AustinWBryan упомянул использование ValueTuples (функция C # 7.0) для замены Tuple, настоятельно рекомендуется. Для получения дополнительной информации о ValueTuples обратитесь к этой ссылке .