1

我有一项任务，需要为集合中的每个对象生成唯一值。如果哈希码合约中不允许冲突，那么使用哈希码将是完美的。

一个想法：将每个对象的哈希码记录到一个多重集中。然后，使用哈希码作为唯一标识符，但如果该哈希码不止一次在集合中，则使用也不在集合中的不同值。但这感觉笨重和尴尬。

更好的想法？

这是我已经拥有的：

public static <V> void toGraphViz(final Graph<V, DefaultWeightedEdge> g, String filename) {

    // to avoid hashcode collisions
    final Set<Integer> hashcodes = new HashSet<Integer>(g.vertexSet().size());

    DOTExporter<V, DefaultWeightedEdge> dot = new DOTExporter<V, DefaultWeightedEdge>(new VertexNameProvider<V> () {

    // vertex name must be unqiue
    @Override
    public String getVertexName(V arg0) {
        int hash = arg0.hashCode();
        while (hashcodes.contains((hash))) {
            hash += 1;
        }
        return "" + hash;
    }
}

编辑：我想这最初并不清楚，但是 id 编号确实需要成为对象的函数，因为getVertexName(V)会被多次调用，并且它期望对于相同的值V，它会得到相同的结果。

此外，Vertex 类型是通用的。所以我不能对特定的类进行任何修改来解决这个问题。

4

7 回答 7

4

这个唯一号码的寿命是多少？只是程序的生命周期？在这种情况下，为什么不只是一个简单的类中的静态计数器，通过适当的同步访问？为每个新对象增加它。无需保留您使用过的值的列表，只需保留您使用过的最高值即可。

如果在许多执行（并且可能是许多同时的实例）中是唯一的，那么也许您可以只使用生成 unqiue 记录 ID 的数据库。

编辑以回应澄清

我之前错过的部分是我们无法修改要为其生成唯一“哈希”的类。

我认为使用会发生冲突的类的哈希码使生活变得艰难。假设我们可以依靠正确实现 equals() 的 Vertex 类，那么我们可以使用对象本身作为我们使用的哈希码集的键。

public class Hasher {

    public  <V> void toGraphViz(final Graph<V, DefaultWeightedEdge> g, String filename) {
         final Map<V, Integer> hashcodes = new HashMap< V, Integer>();
         final int latestHashHolder[] = { 0 }; // array to allow access from inner class

         DOTExporter<V, DefaultWeightedEdge> dot 
                 = new DOTExporter<V, DefaultWeightedEdge>(new VertexNameProvider<V> ()) {

         // vertex name must be unqiue
            @Override
            public synchronized String getVertexName(V vertex) {
                int hashcode;
                if ( hashcodes.containsKey(vertex)){
                    hashcode = hashcodes.get(vertex);
                } else {                
                    hashcode = latestHashHolder[0];
                    latestHashHolder[0]++;
                    hashcodes.put(vertex, (Integer)latestHashHolder[0]);
                }
                return "Vertex-" + hashcode;
            }
        };
    }
}
于 2009-12-03T22:54:52.470 回答
2

为什么不直接使用序列号？

static private int serial=0;
static public synchronized nextSerialNumber() { return ++serial; }

或者组合/混合，比如长的 ((hash<<32) | getNextSerial())。

解决编辑澄清

构造对象时，将序列号分配给私有成员变量，并为 hashCode() 返回它。然后，您应该通过调用 super.equals() 来覆盖 equals（因为生成的序列号与默认的 equals() 实现一致），因为看到没有相应 equals() 覆盖的 hashCode() 覆盖将标记代码工具（和其他程序员）。

public class Vertex
{
private final int                   serial;                                 // instance serial number

public Vertex() {
    serial=nextSerialNumber();
    ...
    }

public int hashCode() {
    return serial;
    }

public boolean equals(Object obj) {
    return super.equals(obj);                                               // serial number hash-code consistent with default equals    
    }

...        

static private int nextSerial=0;
static public synchronized nextSerialNumber() { return nextSerial++; }
}
于 2009-12-03T22:54:41.073 回答
2

您可以考虑使用UUID，具体取决于您要完成的工作...

于 2009-12-03T22:57:30.687 回答
2

要找到对象的唯一值，您必须知道使对象唯一的属性组合。

要运行“.contains()”，你需要有一个确定“.equals()”的方法，这意味着你应该已经知道如何唯一标识一个顶点，所以也许你可以想出一个唯一属性的表达式?

例如，“（x，y，z，rgb）”

除非我误解了这个问题，否则我不建议为此目的使用对象的 hashCode。

于 2009-12-03T23:02:40.063 回答
1

I think you misunderstood hashcode. Based on the contract the hascode should be the same when equals(..) is true and vice versa. So in your case only a vertex with the same properties should have the same hascode, otherwise your self written hascode calculation method should be fixed. As far as I have understood your question a vertex for itself is unique, so you shouldn't have a problem, right?

于 2009-12-04T09:49:58.997 回答
0

我可能不明白你在做什么，但考虑为每个对象创建一个引用。由于引用包含对象的地址，因此每个对象都是唯一的。

于 2009-12-04T09:21:37.337 回答
0

这并不难，不是吗？如果 Java 中的哈希算法不能保证没有冲突，请使用不同的哈希算法。将对象发送到哈希算法，例如 Sha-256，并将其用作密钥。如果您需要保留具有不同哈希值的完全相同对象的不同副本，请在执行哈希时使用种子，并将其与具有哈希的对象相关联。

于 2009-12-04T09:43:31.603 回答