用于唯一标识节点的最佳集合是什么？

Question

目前我正在使用 Dictionary 来存储大约 10,000 个节点。键用作稍后查找的 ID 号，“节点”是包含一些数据的类。程序中的其他类使用 ID 号作为指向节点的指针。 （这听起来可能效率低下。但是，解释我使用字典的原因超出了我的问题范围。）

但是，20% 的节点是重复的。 我想要做的是当我添加一个节点时检查它是否全部准备好存在。如果确实如此，则使用该 ID 号。如果没有创建一个新的。

这是我当前对该问题的解决方案：

public class nodeDictionary 
{

    Dictionary<int, node> dict = new Dictionary<int, node>( );
    public int addNewNode( latLng ll )
    {
        node n = new node( ll );
        if ( dict.ContainsValue( n ) )
        {
            foreach ( KeyValuePair<int, node> kv in dict )
            {
                if ( kv.Value == n )
                {
                    return kv.Key;
                }
            }
        }
        else
        {
            if ( dict.Count != 0 )
            {
                dict.Add( dict.Last( ).Key + 1, n );
                return dict.Last( ).Key + 1;
            }
            else
            {
                dict.Add( 0, n );
                return 0;
            }
        }
        throw new Exception( );
    }//end add new node
}

问题是当尝试将新节点添加到 100,000 个节点的列表中时，添加该节点需要 78 毫秒。这是不可接受的，因为我可能在任何给定时间添加额外的 1,000 个节点。

那么，有更好的方法吗？我不是在寻找有人为我编写代码，我只是在寻找指导。

Answer 1

听起来您想

• 确保 LatLng 覆盖 Equals/GetHashCode （最好实现 IEquatable接口）
• 将所有项目直接填充到 HashSet

中实现 GetHashCode，请参见此处：为什么是当覆盖 Equals 方法时覆盖 GetHashCode 很重要吗？

如果您需要以某种方式生成“人工”唯一 ID，我建议您使用再次使用字典方法，但“相反”：

// uses the same hash function for speedy lookup/insertion
IDictionary<LatLng, int> idMap = new Dictionary<LatLng, int>(); 

foreach (LatLng latLng in LatLngCoords)
{
    if (!idMap.ContainsKey(latLng))
        idMap.Add(latLng, idMap.Count+1); // to start with 1
}

您可以使用 idMap 替换 HashSet；实现（和性能特征）本质上是相同的，但作为关联容器。

这是从 LatLng 到 Id 的查找函数：

int IdLookup(LatLng latLng)
{
     int id;
     if (idMap.TryGetValue(latLng, id))
         return id;
     throw new InvalidArgumentException("Coordinate not in idMap");
}

您可以及时添加它：

int IdFor(LatLng latLng)
{
     int id;
     if (idMap.TryGetValue(latLng, id))
         return id;

     id = idMap.Count+1;
     idMap.Add(latLng, id);
     return id;
}

Answer 2

我会为相反方向添加第二个字典。 ie Dictionary

那么你要么

• 满足于引用相等并且什么也不做。
• 创建一个 IEqualityComparer 并将其提供给
• Node 上的字典 Override Equals 和 GetHashCode

在这两种情况下哈希码的良好实现对于获得良好的性能至关重要。

Answer 3

你的解决方案不仅慢，而且是错误的。 Dictionary 中项目的顺序未定义，因此 dict.Last() 不能保证返回最后添加的项目。 （尽管通常看起来是这样。）

使用 id 来标识应用程序中的对象似乎也是错误的。您应该考虑直接使用对该对象的引用。

但是，如果您想使用当前的设计并假设您根据 latLng 比较节点，则可以创建两个字典：您已有的一个和第二个字典，Dictionary，可以用来有效地找出某个节点是否已经存在。如果是的话，它会给你它的 id。

Answer 4

这段代码的目的究竟是什么？

if ( dict.ContainsValue( n ) )
{
    foreach ( KeyValuePair kv in dict )
    {
        if ( kv.Value == n )
        {
            return kv.Key;
        }
    }
}

ContainsValue 搜索值（而不是键）并且效率非常低 (O(n))。 foreach 也是如此。更不用说当只需要一个时您就同时执行这两项操作（您可以通过稍微重新安排您的 if 来完全删除 ContainsValue）！

您可能应该维护与原始字典“相反”的附加字典（即旧字典中的值是新字典中的键，反之亦然），以“覆盖”您的搜索模式（类似于数据库如何维护表中的多个索引）以涵盖查询表的多种方式）。

Answer 5

您可以尝试使用 HashSet

Answer 6

您可能需要考虑将其重组为仅使用列表（其中“键”只是列表中的索引）而不是字典。一些优点：

1. 通过整数键查找元素现在是 O(1)（并且非常快的 O(1)，因为它只是内部的数组取消引用）。

2. 当插入一个新元素时，您将执行 O(n) 搜索来查看它是否已存在于列表中。如果没有，您也已经遍历了该列表，并且可以记录您是否遇到了具有空记录的条目。如果有，该索引就是新键。如果不是，则新键是当前列表计数。您只需枚举一次集合而不是多次，并且枚举本身比枚举字典要快得多。