使用HashMap支持的contains()方法的Set的准确性？

Question

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

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

但是当使用contains来检查边缘是否在集合中时,这有多可靠？我不能假设得到误报吗？无论如何要克服这个？

引起我关注的确切陈述是:

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

谢谢!

哦顺便说一句,我正在使用Java.

编辑:

我应该在这个问题上明确这一点.在我的图形中没有边缘对象,有顶点对象,每个顶点对象包含更多顶点对象的列表,即边缘.因此,我认为结合您的回答后面的问题是:

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

EDIT2:

我确实使用Java库作为我的hashmap,我将其声明如下:

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

Answer 1

注意:从你的问题我无法分辨你是否正在使用HashSet,或者你自己的家庭滚动实现.请注意,Java HashSet只是HashMap忽略值的包装器.HashSet.contains只需调用containsKey内部地图.

HashMap.containsKey使用相同的查找get.这将计算哈希值并使用它来查找正确的桶.从那里它将走在水桶并使用,equals直到它找到完全匹配.假设元素类型实现了两者hashCode并且equals正确,则不会出现使用误报的可能性,containsKey因为equals最终用于确认.

的相关源代码是在数据包私有方法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覆盖.

Answer 2

根据定义,散列码会发生冲突.将它们添加在一起无济于事

您应该使图形的边缘支持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);