1

我正在尝试改进一些不久前编写的代码。该功能对系统的核心功能非常重要，因此我对大修持谨慎态度。

我正在使用字典来保存对象

Dictionary<Node, int> dConnections

该对象Node本身就是一个包含许多属性和一些列表的复杂对象。这本词典可以容纳大约 100 个或更多条目。

目前正在检查字典是否包含类似的节点

dConnections.ContainsKey(Node)

所以我假设（检查此节点是否在字典中）字典将必须检查整个节点及其属性是否与字典中的节点匹配（它将继续遍历字典直到找到匹配项）这会对性能产生重大影响吗？

我最好不要在字典中使用对象而是使用对象ID。

4

2 回答 2

5

.NET 字典是 Inside 中的哈希表。这意味着如果 Node 不覆盖 GetHashCode 和 Equals 方法，当您调用 ContainsKey 时，它将匹配：

免责声明：这是一个摘要。事情有点复杂。请不要叫我名字，因为我过于简单化了。

  1. Node对象的ref地址的hashcode的一个分区。分区数取决于哈希表的桶数（取决于字典中的键总数）
  2. 如果多个节点在同一个存储桶中，则为确切的参考地址。

这个算法非常有效。当您说字典中有 100 个或更多条目时，这不是“很多”。这是几个。

这也意味着 Node 对象的内容与 ContainsKey 的匹配方式无关。它将与完全相同的参考匹配，并且仅与该参考匹配。

如果您自己实现 GetHashCode 和 Equals，请注意，当实例属性更改（不可变）时，这些方法返回值不应更改。否则，您很可能会在错误的存储桶中获取密钥，因此完全无法访问（无需枚举整个字典）。

于 2012-10-15T10:20:40.033 回答
3

它将继续遍历字典，直到找到匹配项

不，字典不会通过迭代所有节点来找到匹配项；首先获得哈希码，用于将候选者限制为一个，可能是几个（取决于您的哈希方法有多好，以及存储桶大小）

所以我假设（检查该节点是否在字典中）字典将必须检查整个节点及其属性是否与字典中的节点匹配

不，对于每个候选人，它首先检查哈希码，这是一种快捷方式，可以快速检测非平等与可能的平等

所以这里的关键是：你Node的散列方法，又名GetHashCode. 如果这很复杂，那么另一个技巧是在您第一次需要它时缓存它，即

int cachedHashCode;
public override int GetHashCode() {
    if(cachedHashCode == 0) {
       cachedHashCode = /* some complex code here */
       if(cachedHashCode == 0) {
           cachedHashCode = -45; // why not... just something non-zero
       }
    }
    return cachedHashCode;
}

请注意，它仍然使用Equals，因为最后的“它们是否相同”，所以您显然也希望Equals尽可能快 - 但Equals相对很少被调用。

于 2012-10-15T10:22:25.633 回答