我一直在研究一个项目，该项目需要遍历数据集合并删除重复了"主键"的条目。我尝试使用

List<int>

和

Dictionary<int, bool>

使用字典，我发现性能稍好，即使我永远不需要每个条目都标记有布尔值。我的期望是，这是因为列表允许索引访问，而字典不允许。我想知道的是，是否有更好的解决方案来解决这个问题。我不需要再次访问条目，只需要跟踪看到的"主键"，并确保仅对具有新主键的条目执行加法工作。我正在使用Cand .NET 2.0。而且我无法控制固定输入数据以从源中删除重复项(不幸的是！)。这样我们就可以进行扩展了，总体而言，我正在检查应用程序中大约1,000,000次的重复项，但是在不超过大约64,000次的子集中需要唯一。

解决方案

他们在.NET 3.5中添加了HashSet类。但是我想它将与字典相提并论。如果我们说的少于100个元素，则列表的效果可能会更好。

我真的不明白你的要求。

首先，与我们所说的相反。字典对索引进行了访问(是一个哈希表)，而de List却没有。

如果我们已经在字典中保存了数据，那么所有键都是唯一的，那么就不可能有重复项。

我怀疑我们将数据存储在另一种数据类型中，并且正在将其存储到字典中。如果是这种情况，则插入数据将适用于两个字典。

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

编辑：没关系我的评论。我以为我们在谈论C ++。我不知道我的帖子是否与Cworld有关。

哈希表可能会快一点。由于访问内存的方式，二叉树(在字典中使用的树)往往相对较慢。如果树变得很大，则尤其如此。

但是，在更改数据结构之前，我们是否尝试过为字典使用自定义池分配器？我敢打赌，时间不是花在遍历树本身上，而是在字典为我们完成的数百万个分配和释放中。

我们可能会发现将简单的池分配器插入字典模板中就会获得10倍的速度提升。 Afaik boost具有可以直接使用的组件。

另一个选择：如果我们知道整数中仅存在64.000个条目，则可以将它们写入文件并为其创建完美的哈希函数。这样，我们就可以使用哈希函数将整数映射到0到64.000范围内，并为位数组建立索引。

可能是最快的方法，但灵活性较差。每次整数集更改时，都必须重做完美的哈希函数(可以自动完成)。

如果要检查整数的唯一性，并且整数的范围受到足够的限制，则可以只使用数组。

为了更好地打包，我们可以实现位图数据结构(基本上是一个数组，但是数组中的每个int通过每个键使用1位表示键空间中的32个int)。这样，如果最大数量为1,000,000，则仅需要〜30.5KB的内存用于数据结构。

位图的执行将是O(1)(每次检查)，这很难被击败。

关于从数组中删除重复项有一段时间了。出于问题的目的，性能并不是一个要考虑的问题，但是我们可能想看看答案，因为它们可能会给我们一些想法。另外，我可能不在这里，但是如果我们尝试从数组中删除重复项，那么像Enumerable.Distinct这样的LINQ命令可能会比编写自己的东西提供更好的性能。事实证明，有一种方法可以使LINQ在.NET 2.0上运行，因此这可能是值得研究的途径。

如果要使用列表，请使用BinarySearch：

// initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
}

我们还可以将其用于可以通过使用重载为其定义IComparer的任何类型：BinarySearch(T item，IComparer <T>);