Era: E quando um inteiro é pequeno demais para um hashCode()? Agora: Teoria dos números

Pessoal,

Criei um HashMap da seguinte maneira:

private HashMap<Long,Circuito> circuitos = new HashMap<Long,Circuito>();

E um “hashCode” na classe Circuito que retorna um long invés de um int:

[code] public long longHashCode(){
int num_de = this.barraDe.getNumero();
int num_para = this.barraPara.getNumero();
int num_circ = this.getNumero();

    return (long) (num_circ + num_de * 1e3 + num_para * 1e7);
}[/code]

E estou inserindo os dados no HashMap da seguinte maneira:

circuitos.put(val.longHashCode(),val);

Como eu tenho dezenas de milhares de objetos da classe Circuito, eu tentei fazer isso para otimizar a busca de Circuitos efetuada em um método com a seguinte assinatura:

public Circuito getCircuitoEntreBarras(Barra De, Barra Para, int num_circuito)

Ou seja, um Circuito é procurado a partir de três inteiros e um hashCode que retorna apenas um int irá gerar colisões sobrescevendo chaves no HashMap.

Gostaria da opinião de vocês: a gambiarra foi muito forte? Peguei pesado demais ou não?

PS> Estou querendo não usar SQL no momento…

Obrigado,

Mas, dessa forma, o hashCode não corre o risco de se repetir? Então vc teria objetos sendo descartados do seu mapa.

Ao invés de um hashCode, crie um campo de ID. Você pode inicializa-lo assim:

public class Circuito 
{
   private static long nextId = Long.MIN_VALUE;

   private long id = nextId++;

   public long getId() 
   {
       return id;
   }
}

Isso garante que cada objeto seu receba um ID diferente (que mudará a cada execução do programa, não sei se isso é um problema para vc). E você tem bilhões de possibilidades, antes que o long acabe.

Não seria porque esses inteiros que compõem o longHashCode não assumem um valor inteiro arbitrário. Os dois primeiros assumem de 1 a 25.000 e o num_circ, até 100, no máximo mesmo. Esses limites são especificados pela classe Barra.

PS. O projeto se trata de uma GUI para um aplicativo antigo. Esse é o motivo dessa estrutura de dados estranha: eu acabo tendo que fazê-las da maneira que o outro software legado os faz para reduzir meu trabalho…

Essa solução com um membro estático não se aplica no meu caso. Como eu preciso encontrar um Circuito a partir de seus componentes (número da barra De, número da barra Para e int num_circuito) dentro de uma estrutura de dados, ela não atenderia aos meus propósitos.

Quando é o momento para se partir para SQL? :slight_smile:
Seria desaconselhável usar SQL em um aplicativo comum?

Obrigado!

[quote=phph]Pessoal,

Criei um HashMap da seguinte maneira:

private HashMap<Long,Circuito> circuitos = new HashMap<Long,Circuito>();

E um “hashCode” na classe Circuito que retorna um long invés de um int:

[code] public long longHashCode(){
int num_de = this.barraDe.getNumero();
int num_para = this.barraPara.getNumero();
int num_circ = this.getNumero();

    return (long) (num_circ + num_de * 1e3 + num_para * 1e7);
}[/code]

E estou inserindo os dados no HashMap da seguinte maneira:

circuitos.put(val.longHashCode(),val);

Como eu tenho dezenas de milhares de objetos da classe Circuito, eu tentei fazer isso para otimizar a busca de Circuitos efetuada em um método com a seguinte assinatura:

public Circuito getCircuitoEntreBarras(Barra De, Barra Para, int num_circuito)

Ou seja, um Circuito é procurado a partir de três inteiros e um hashCode que retorna apenas um int irá gerar colisões sobrescevendo chaves no HashMap.

Gostaria da opinião de vocês: a gambiarra foi muito forte? Peguei pesado demais ou não?
[/quote]

não tenho palavras para descreve o enorme tamanho da gambiarra.
Primeiro o hahcode é um int. long é uma má ideia para hashcode
o hash code um um long é calculado assim

(int)(valor ^ valor >>>32 )

depois, o que vc quer é dado um conjunto de parametros encontrar o circuito.
Isso significa que esses parametros compoem a chave primária para encontrar o circuito. Então, ele têm que compor a chave do mapa.

[code]
class Chave {

Barra de;
Barra para; 
int numCircuito 


// implemente equals

public int hashCode(){
// só um exemplo
return numCircuito ^ de.hashCode() ^ para.hashCode();
}
}

// uso

map.put ( new Chave (de, para, num) , circuito );

public Circuito getCircuitoEntreBarras(Barra De, Barra Para, int num_circuito){

return map.get(new Chave (de, para, num));
}[/code]

Não há problema nenhum em ter um hashCode long. Não é o padrão do Java e não será o default nas collections. Mas nada impede que vc tenha um hashcode num intervalor maior que o de um int, exceto talvez a falta de praticidade.

Agora, eu também concordo com o Sérgio de que, se vc quer fazer buscas por esse campo, deve procurar algo mais determinístico. Como usar os próprios campos, ou criar um novo identificador.

E, no seu caso, bancos de dados e SQL seriam realmente uma ótima opção. Além de serem uma tecnologia consolidada, rápida e de boa performance, vai te poupar muita reimplementação da roda.

[quote=sergiotaborda]
não tenho palavras para descreve o enorme tamanho da gambiarra.
Primeiro o hahcode é um int. long é uma má ideia para hashcode
o hash code um um long é calculado assim

(int)(valor ^ valor >>>32 )

depois, o que vc quer é dado um conjunto de parametros encontrar o circuito.
Isso significa que esses parametros compoem a chave primária para encontrar o circuito. Então, ele têm que compor a chave do mapa.

[code]
class Chave {

Barra de;
Barra para; 
int numCircuito 


// implemente equals

public int hashCode(){
// só um exemplo
return numCircuito ^ de.hashCode() ^ para.hashCode();
}
}

// uso

map.put ( new Chave (de, para, num) , circuito );

public Circuito getCircuitoEntreBarras(Barra De, Barra Para, int num_circuito){

return map.get(new Chave (de, para, num));
}[/code][/quote]

kkkkk. Isso é apenas um projeto de gambiarra. Eu só quero que essa parte do código funcione neste momento para testar outras partes do código. Depois disso, irei voltar nessa parte e utilizar SQL mesmo não só para fazer isso, mas para agilizar outras partes.

Eu postei o código mais para colocar a questão: e quando um inteiro não é suficiente grande para um hashCode?

Perceba que eu não usei o “int hashCode()”, mas um método não herdado do Object: “long longHashCode()”.

Outra questão: o meu longHashCode em si é determinístico, não? Ele é a soma ponderada das “minhas chaves”. Ou não?

obrigado!!

Sim, vc tem absoluta certeza de que essa sua fórmula não gera colisões de hash?

Se só é uma gambi temporária, então tudo bem, poderia ter feito algo até pior. :slight_smile:
Não precisava nem ter trazido o assunto pro fórum. A menos que vc quisesse socializar um pouco e entender melhor as implicações gambiarrísticas da solução, assim como trocar experiências sobre outras tenebrosidades que fasemos “fora do ambiente de produção”.

Perceba que sim usou o int hashCode porque a sua chave do mapa é um Long e o hashcode de um Long é aquele que eu mostrei antes. Ou seja, vc faz um long, mas no fim tudo vira int. Um inteiro sempre é suficiente para o hashCode.

O problema não está no long ou no int e sim no seu objeto chave. O objetivo chave deve ser construido pelos identificadores.
Repare que o map usa o hash mas tb usa o equals. Logo, o seu objeto chave tem que - deterministicamente - identificar o circuito.
A colisão de hash propria das funções irá destruir o seu mapa: vc vai incluir dois circuitos que geram o mesmo hash do long e ai ( como só o numero está sendo a chave) um dos circuitos vai ao ar.

o ponto é fazer o uso correto da funcionalidade do map.

A única forma do long servir é se vc garante que circuitos diferentes sempre tem long diferente.

O código é uma gambiarra temporária, sim, mas eu trouxe para o fórum para discussão do hashCode().

Valeu, sergiotaborda. Reli a sua mensagem e agora eu entendi as conseqüências de um

Long longHashCode e sua conversão para int hashCode()

[EDIT] Mas ainda não enxerguei como eu vou fazer um int hashCode (32 bits) a partir de três inteiros:

  • um inteiro entre 0 a 40.000
  • outro inteiro entre 0 a 40.000
  • outro inteiro entre 1 a 50 (aprox.) [/EDIT]

obrigado,

[quote=phph]

[EDIT] Mas ainda não enxerguei como eu vou fazer um int hashCode (32 bits) a partir de três inteiros:

  • um inteiro entre 0 a 40.000
  • outro inteiro entre 0 a 40.000
  • outro inteiro entre 1 a 50 (aprox.) [/EDIT]

obrigado,[/quote]

Acho que de certa forma vc está confundindo hashcode com codigo de circuito.
Mesmo assim veja o seguinte : 1 a 50 precisa de 6 bits 0 a 40000 precisa de 16 bits.
Portanto para ter um hashcode completamente unit vc precisa de 16 + 16 + 6 = 38 bits que é maior que um inteiro. Mas ai é que está o ponto. O hashcode não precisa ser único se vc criar um objeto chave, ele só precisa ser unico se vc usar o Long (ou o Integer).
Entao assumindo que vc não precisa de um hash unico porque irá ter o objeto chave o que vc precisa é minimizar a colisão

Acho que no seu caso vc poderia usar uma função como esta

de.hashCode() >>> 16 ^ para.hashCode() >>> 16  | num.hashCode() << 16

Mas isso no objeto chave, claro.
O equals seria mais ou menos assim

public boolean equals (Object other){
      return other instanceof Chave && equals((Chave)other);
}
public boolean equals (Chave other){
return this.num == other.num && this.de == other.de && this.para == other.para
}

Justamente após essas contas, eu tentei usar inutilmente um long, 64 bits. Você tem toda a razão em relação às colisões.

Terei de estudar um pouco de teoria dos números para fazer isso, mas eu me sinto um pouco de limitação nessa questão do Java/API Collections. Eu queria trocar os 32 bits adicionais de um long por um hashCode mais fácil de se implementar para impedir completamente as colisões. Em um sistema crítico, isso não poderia se tornar uma questão séria devido a possibilidade de perder objetos devido à colisão de chaves?

Obrigado pela discussão.

A colisão de chaves é inevitável. Contudo o objetivo é minimizá-la. Lembre-se que o hashcode é usa pela api de collections como um acelerador , no fim ele sempre usa equals para ter a certeza e resolver colisões. Não é o hashcode sozinho que define a chave e sim o hashcode + equals ( é por isso que a sua ideia de Long não funciona)

Vc tem conhecimento daquilo que forma o codigo e qual a probabilidade de existirem repetidos. É pelo equilibro desses numeros que vc obtem um bom hashcode. Contudo, eu se fosse vc não preocupava tanto com isso. desde que vc crie uma chave que compare com equals e deterministicamente identifique o circuito não importa muito a sua implementação de hashcode que acompanha o equals.