3

想象一下这样的场景：我需要操作（添加、搜索和删除）类型对象列表中的项目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

到目前为止，我所拥有的 aDictionary<int, Book>作为Id键和Book值。但在这种情况下，如果我想在字典中添加一本新书，我必须遍历所有值以检查是否Title重复。

我开始考虑为 Titles 创建一个HashSetonly for Titles 或拥有第二个Dictionary<string, Book>作为Title键的字典。

任何建议如何处理这种情况？

编辑：

正如@David 提到的，我忘了说我主要关心的是性能。我想以最快的方式 (O(1)) 按 Id 和 Title 查找对象。

4

3 回答 3

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>());
于 2018-05-09T03:33:17.053 回答
2

您可以使用 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 功能）替换元组，强烈推荐。有关 ValueTuples 的更多信息，请参阅此链接。

于 2018-05-09T02:02:22.467 回答
1

看起来ID和Name都将是唯一的，例如，您不应该能够两次使用相同的 ID，无论该名称是否已被使用。否则，我们最终会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等来完成完整的行为

于 2018-05-09T02:51:06.133 回答