STL multimap和.NET Dictionary<key, List<values>>有何不同？

Question

我有一个问题，需要一个支持一个键对应多个值的.NET字典。过去我在C++程序中使用了STL multimap。一个multimap的设计与一个列表字典有何不同，例如性能、大小等（不包括泛型与模板）？

- Dan

Answer 1

multimap.count: O(log n + m)，其中n是键的数量，m是与给定键关联的项数。

对于Dictionary<TKey, List<TValue>>，相应的功能为：

int count = dictionary[key].Count;

而更安全的说法是：

int count;
List<TValue> list;
if(dictionary.TryGetValue(key, out list)) {
    int count = list.Count;
}

这是一个O(1)操作，因为查找是O(1)¹，而List<T>.Count是O(1)。

multimap.find： O(log n)，其中n是键的数量。

对于Dictionary<TKey, List<TValue>>，等效的功能将是：

List<TValue> elements = dictionary[key];

更安全的说法是：

List<TValue> list;
if(dictionary.TryGetValue(key, out list)) {
    // safe to iterate list
}

这是O(1)。请参见之前在Dictionary<TKey, TValue>中按键查找的注释。

multimap.insert： O(log n)，其中n是键的数量。

对于Dictionary<TKey，List<TValue>>，相应的功能将是：

// value is TValue to insert
List<TValue> list;
if(!dictionary.TryGetValue(key, out list)) {
    list = new List<TValue>();
    dictionary.Add(key, list);
}
list.Add(value);

这通常是O(1)，但当字典的容量必须增加以容纳新元素时，可以是O(n)。

multimap.remove：此方法有三个重载；我只考虑接受键并从multimap中删除该键的所有出现的那个。这是一个O(log n + m)操作，其中n个键和m个对象与给定键相关联。

对于Dictionary<TKey，List<TValue>>，等效的功能将是：

 dictionary.Remove(key);

从文档中可以看到："该方法的时间复杂度接近于O(1)"。同样的评论也适用于此。 ¹: 从文档中可以看到："通过键检索值非常快，接近于O(1)。"为什么文档在这一点上含糊不清让我感到困惑。要么一个操作是O(1)，要么就不是。不存在所谓的“接近于O(1)”。

- jason

Answer 2

multimap（多重映射）： 插入/删除操作的时间复杂度是对数级别 Big-O(log n)， 查找操作的时间复杂度是常数级别 Big-O(1)。

每个元素都使用一个键值访问，与map不同，multimap的键值不需要唯一，相关联的值也不需要唯一。map使用存储函数key_compare按照其键值对元素进行排序，该函数简单地执行小于比较。

这里有一篇关于IDictionary性能的文章，没有提及任何Big-O性能指标，但是给出了一些使用字典实际运行的经验。

- Andy

---

当然，IDictionary 的文档没有提到任何渐近指南；接口不能要求所有实现者满足某些渐近性能要求。此外，从 Dictionary<TKey, TValue> 的文档中可以看出：“如果 Count 小于容量，则 [Add] 方法是一个接近 O(1) 的操作。如果必须增加容量以容纳新元素，则此方法成为一个 O(n) 操作，其中 n 是 Count。”此外，“使用键检索值非常快，接近 O(1)。” 为什么他们在最后一点上含糊不清我不明白。 - jason

可能是因为GetHashCode()没有被正确实现，当有大量冲突时，它就不再是O(1)了。 - Dan Berindei