1

嗨，我正在使用由 HashMap 支持的 Set 来跟踪我已经在图中遍历了哪些边。我计划通过添加存储在每个边缘中的数据的哈希码的结果来键入集合。

v.getData().hashCode() + wordV.getData().hashCode()

但是，当使用 contains 检查边缘是否在集合中时，这有多可靠？难道我不能假设得到误报吗？有没有办法克服这个？

让我担心的确切说法是：

edgeSet.contains(v.getData().hashCode() + wordV.getData().hashCode())

谢谢！

哦，顺便说一句，我正在使用 Java。

编辑：

我应该在问题中说明这一点。在我的图中，没有边对象，有顶点对象，每个顶点对象都包含更多顶点对象的列表，即边。因此，我想结合您的回答得出的问题是：

我可以使用 Set 来存储对信息的引用而不是对象......吗？即我可以存储为顶点的数据对象添加两个哈希码的结果吗？

编辑2：

我确实在为我的 hashmap 使用 Java 库，我将其声明如下：

Set<Integer> edgeSet = Collections.newSetFromMap(new ConcurrentHashMap<Integer, Boolean>());
4

3 回答 3

6

注意：根据您的问题，我无法判断您使用的是HashSet，还是您自己的家庭滚动实现。请注意，Java只是忽略值HashSet的包装器。只需调用内部地图。HashMapHashSet.containscontainsKey

HashMap.containsKey使用与 相同的查找get。这将计算哈希并使用它来找到正确的存储桶。从那里它会走桶并使用equals，直到找到完全匹配。假设元素类型既正确地实现了hashCode，则使用因为最终用于确认而equals没有机会获得误报。containsKeyequals

相关的源代码在 package-private 方法getEntry中，它被containsKey和使用get：

final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

编辑：

我可以使用 Set 来存储对信息的引用而不是对象......吗？即我可以存储为顶点的数据对象添加两个哈希码的结果吗？

不，您需要实现一个表示此信息的新类并将其实例存储在Set. 这可能是一个简单的 POJO，每个信息都有一个字段，并且正确地覆盖hashCode和覆盖。equals

于 2012-09-08T02:47:54.053 回答
5

根据定义，哈希码会发生冲突。将它们加在一起没有任何帮助。

你应该让你的图的边缘支持 hashCode 和 equals，然后简单地将边缘放在一个哈希集中。

class Edge { ... equals and hashCode ... }

HashSet<Edge> traversed = new HashSet<Edge>();
traversed.add(edge);
...
if(traversed.contains(edge)) ...

如果您要对边进行编号，则 Integer 已经具有良好的哈希码和等于，因此请使用它：

HashSet<Integer> traversed = new HashSet<Integer>();
if(traversed.contains(edgeNumber)) ...
traversed.add(3);
于 2012-09-08T02:49:26.930 回答
1

只要你同时覆盖hashCode()and equals()，你会没事的。哈希码永远不能保证是唯一的。也就是说，您有点滥用 Set。通过存储具有正确实现的类hashCode()和equals()方法，例如contains()' 将具有完美的准确性。但是，这不是您在这里使用它的方式。听起来您几乎正在构建自己的数据结构/集合，因此您需要考虑以与“哈希”集合相同的方式执行此操作-使用 HashMap 存储哈希的存储桶-哈希值作为键，然后是要比较的值的集合。这将允许您快速查看父映射是否甚至具有您正在寻找的哈希值。如果没有，你就完成了（假）。如果是这样，那么您需要确认其“存储桶”具有您正在寻找的特定值（真）。

于 2012-09-08T02:43:16.547 回答