代码之家 › 专栏 › 技术社区 › Matt H

多重映射实现

collections data-structures performance .net

1

Matt H · 技术社区 · 17 年前

我正在用C语言编写一个简单的IDictionary抽象,它将字典<K、 i收集<V>>。基本上,它将多个值映射到一个键。当值列表中的最后一项被删除时,我无法决定是删除键及其空列表,还是保留它(以避免在重用键时实例化新集合),并在确定键是否存在时检查键的值计数。

4 回复 | 直到 17 年前

1

4

ARKBAN 17 年前

我将删除集合,以便您的多重映射具有一致的行为。如果我使用了你的多重映射,我会非常惊讶(也不高兴)地发现一个丢失的键的行为会有所不同,这取决于一个键之前是否在多重映射中。

Clear()是否删除集合?

如果不删除集合,还可能造成意外内存泄漏。开发人员可以添加许多项,然后删除它们。内存使用(GC后)应恢复到添加这些项之前的数量。

我不会担心创建集合的成本。我会担心你为多重地图创建的合同。如果在分析应用程序之后,您发现这是一个问题,那么您可以为该行为修改或创建一个特殊的多重映射。不要落入过早优化的陷阱。

2

Marc Gravell 17 年前

在.NET3.5中,有 ILookup<TKey,TValue> Lookup<TKey,TValue> 查找<TKey,TValue> )是不变的,但我写了一个 EditableLookup<TKey,TValue> 在里面 miscutil .

在该版本中;是-如果最后一项(带钥匙)被移除,我将移除钥匙。这样可以更容易地查看存在哪些键(即。 .Keys 等等)。

3

0

ykaganovich Mike Samuel 17 年前

4

0

Don Kirkby 17 年前

这取决于你的使用模式。如果要添加和删除很多项,那么这些空集合将耗尽内存。我的猜测是,你不会通过保留这些收藏品来节省那么多时间。和往常一样,如果这对你的表现如此重要,你应该衡量而不是猜测哪种方式更好。

如果您真的认为创建这些集合非常昂贵,那么不要一直创建新的集合,而是将未使用的集合放入列表中,并在向hashmap添加新键时重用它们。我想这可能是轻量级的模式。您可能应该将未使用的集合列表保持在主hashmap大小的一半以下(再次测量,以查看比率如何影响性能)。