Java: obter uma propriedade única de um objeto (como hashcode, mas a prova de colisão)
https://stackoverflow.com/questions/1843565
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho uma tarefa para a qual é necessário para gerar um valor exclusivo para cada objeto em um conjunto. usando o hashcode seria perfeito, se colisões não foram autorizados no contrato hashcode.
Uma idéia: Record hashcode de cada objeto em um multiset. Em seguida, use hashcodes como o identificador único, mas se isso hashcode está no conjunto mais de uma vez, use um valor diferente que também não está no conjunto. Mas este se sente volumoso e desajeitado.
idéias melhores?
Aqui está o que eu já tenho:
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;
}
}
EDIT: Eu acho que isso não era originalmente clara, mas o número de identificação que de alguma forma precisa ser uma função do objeto, porque getVertexName(V) será chamado várias vezes, e ele espera que para o mesmos valores de V, vai obter os mesmos resultados.
Além disso, o tipo Vertex é genérico. Então eu não posso fazer quaisquer modificações a uma classe específica de corrigir isso.
Solução
O que é o tempo de vida deste número único? Apenas o tempo de vida do programa? Caso em que porque não apenas um contador estático simples na classe, acessado com a sincronização adequado? Incrementá-lo para cada novo objeto. Não há necessidade de manter uma lista dos valores que você usou, apenas o maior valor que você usou.
Se exclusivos em muitas execuções (e talvez muitos casos simultâneos), então talvez você pode apenas usar um banco de dados que gera IDs de registro unqiue.
EDITADO em resposta a esclarecimentos
A peça que eu perdi antes foi que não podemos modificar a classe para a qual deseja gerar o "Hash" único.
Eu acho que o trabalho do código hash da classe, que terá colisões é tornar a vida difícil. Assumindo que podemos contar com as classes Vertex em questão tendo iguais corretamente implementadas (), então podemos usar o próprio objeto como uma chave para o conjunto de hashcodes temos utilizado.
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;
}
};
}
}
Outras dicas
Você poderia considerar o uso de um UUID , dependendo do que você está tentando realizar ...
Para encontrar um valor único para um objeto, você tem que saber uma combinação de propriedades que fazem o objeto único.
Para executar ".Contains ()", você precisa ter um método de determinação ".equals ()", o que significa que você já deve saber como identificar um Vertex, então talvez você pode vir até com uma expressão de as propriedades únicas?
por exemplo., "(X, y, z, RGB)"
A menos que eu estou mal-entendido a pergunta, eu não recomendaria mucking com hashCode de um objeto para esta finalidade.
Por que não usar um número de série?
static private int serial=0;
static public synchronized nextSerialNumber() { return ++serial; }
Ou uma combinação / híbrido, digamos, um longo de ((hash de << 32) | getNextSerial ()).
Para resolver a EDIT esclarecimentos
Quando você construir o objeto, alocar o número de série para uma variável de membro privado e devolvê-lo para hashCode (). Você deve então substituir iguais com uma chamada para super.equals () (uma vez que um número de série gerado é consistente com os iguais Default () implementação) porque vendo uma substituição de hashCode () sem uma iguais correspondentes () override vai bandeira vermelha do código de ferramentas (e outros programadores).
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++; }
}
Eu acho que você entendeu mal Hashcode. Com base no contrato a hascode deve ser o mesmo quando iguais (..) é verdadeira e vice-versa. Assim, no seu caso, apenas um vértice com as mesmas propriedades devem ter o mesmo hascode, caso contrário, a sua auto escrito método de cálculo hascode deve ser corrigido. Tanto quanto eu entendi a sua pergunta um vértice para si é única, então você não deve ter um problema, certo?
Eu provavelmente não entendem o que você está fazendo, mas considerar a criação de uma referência para cada objecto. Como a referência contém o endereço do objeto que será exclusivo para cada objeto.
Não é tão difícil, não é? Basta usar um algoritmo de hash diferente, se aquele em Java não garante nenhuma colisão. Enviar o objecto para o algoritmo de mistura, por exemplo Sha-256, e usar isso como a chave. Se você precisa manter cópias diferentes de exatamente o mesmo objeto, com diferentes valores de hash, use uma semente quando você executar o hash e armazenar esta relacionada com o objeto com o hash.
