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

Question

目前我正在使用 Dictionary<int,node>存储大约 10,000 个节点。该 key 用作以后查找的 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 毫秒。这是 Not Acceptable ，因为我可以在任何给定时间添加额外的 1,000 个节点。

那么，有没有更好的方法来做到这一点？我不是在找人为我写代码，我只是在寻找指导。

Answer 1

听起来你想要

• 确保 LatLng 覆盖 Equals/GetHashCode(最好实现 IEquatable<LatLng> 接口(interface))
• 将所有项目直接填入 HashSet<LatLng>

要实现 GetHashCode，请参见此处:Why is it important to override GetHashCode when Equals method is overridden?

如果您需要以某种方式生成“人工”唯一 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;
}