java 哈希对象

Question

我希望能够确定我之前是否遇到过一个对象 - 我有一个图形实现，我想看看我是否创建了一个循环，可能是通过使用乌龟迭代 Node 对象/野兔弗洛伊德算法。

但我想避免每次都对“已看到”节点列表进行线性搜索。如果我有一个仅包含键的哈希表，那就太好了。我可以以某种方式散列一个对象吗？ java对象不就是对内存中位置的引用吗？我想知道如果是这样的话，碰撞问题会有多大……

Answer 1

简单的答案是创建一个 HashSet 并在第一次遇到每个节点时将其添加到该集合中。

唯一不起作用的情况是，如果您为节点类重载了 hashCode() 和 equals(Object) 以实现基于节点的相等性内容(或其他)。然后你需要:

• 使用 IdentityHashMap 类，该类使用 == 和 System.identityHashcode 而不是 equals(Object) 并且hashCode()，或
• 使用您自己风格的对象标识自行构建哈希表。

<小时/>

Aren't java objects just references to places in memory anyway?

是和否。是的，引用由内存地址表示(在大多数 JVM 上)。问题是 1) 你无法获取地址，2) 当 GC 重新定位对象时它可能会改变。这意味着您不能使用对象地址作为哈希码。

identityHashCode 方法通过返回一个最初基于内存地址的值来处理此问题。如果您随后对同一个对象再次调用 identityHashCode，您一定会获得与之前相同的值...即使该对象已被重新定位。

I wonder how much of a problem collisions would be if so..

identityHashCode 方法生成的哈希值可能会发生冲突。 (也就是说，两个不同的对象可以具有相同的身份哈希码值。)任何使用这些值的东西都必须处理这个问题。 (标准 HashSet 和 IdentityHashMap 类会处理这些冲突......如果您选择使用它们。)