4

Atualmente estou usando

Object.prototype.GetHashCode = function () {
    var s = this instanceof Object ? JSON.stringify(this) : this.toString();

    var hash = 0;
    if (s.length === 0) return hash;
    for (var i = 0; i < s.length; ++i) {
        hash = ((hash << 5) - hash) + s.charCodeAt(i);
    }
    return hash;
};
Number.prototype.GetHashCode = function () { return this.valueOf(); };

Para números é bem rápido, mas para objetos complexos é muito ineficiente principalmente devido a conversão para JSON.

Existe alguma forma de calcular o hashcode de uma forma mais eficiente?

2 Respostas 2

4

Os requisitos principais de um hashCode são:

  1. Se A == B, então hashCode(A) == hashCode(B);

    (A recíproca não é verdadeira: dois objetos podem ter o mesmo hashCode e entretanto serem diferentes. Isso é chamado de colisão, e na prática costuma ser inevitável.)

  2. Os hashes devem ser distribuídos de forma homogênea para todos os objetos do domínio (para diminuir a chance de colisão);

  3. Ele deve ser rápido de computar, caso contrário o ganho de performance em se usar uma tabela hash é negado pelo custo de se computar os hashes.

Para assegurar a eficiência, em geral é necessário se criar um hashCode específico para cada situação (o seu código de exemplo corresponde a um bom hash para strings em geral - desde que não muito longas). Inclusive, quando se usa um critério específico de igualdade, é importante que o hashCode utilizado seja coerente com esse critério (ver requisito 1 acima).

Na ausência de mais especificidade, alguns métodos para se calcular o hashCode seriam (em ordem crescente de homogeneidade, mas decrescente de performance):

// constante (rápido, mas inútil)
function hashCode1(obj) { return 0; }

// conta o número de propriedades
function hashCode2(obj) {
    var contagem = 0;
    for ( var p in obj )
        contagem++;
    return contagem;
}

// leva somente as chaves das propriedades em consideração
function hashCode3(obj) {
    var hash = 0;
    for ( var p in obj )
        hash += hashString(p);
    return hash;
}

// leva as chaves e os valores em consideração
function hashCode4(obj, profundidade) {
    if ( !profundidade) profundidade= 0;
    var hash = 0;
    for ( var p in obj )
        hash += hashString(p) + 
                (profundidade> 0 ? hashCode4(obj[p], profundidade-1) : 0);
    return hash;
}

E por aí vai... Quando mais "fundo" se for no objeto, menor a chance de ocorrerem colisões (i.e. objetos diferentes com o mesmo hash), mas maior o tempo de cálculo do hash (i.e. menor a performance). Cabe a você determinar para seu conjunto de dados em particular qual é o melhor equilíbrio entre precisão e rapidez de cálculo que assegure que o algoritmo utilizador do hash tenha a melhor performance.

(Nota: o hashCode4 foi simplificado - na prática, a chamada recursiva precisaria verificar também o tipo do objeto para chamar o método mais apropriado de hash para aquele tipo)


Atualização: em um comentário na sua resposta à pergunta relacionada eu afirmei que fazer um hash a partir do JSON de um objeto era "terrivelmente ineficiente". Gostaria de esclarecer essa afirmação, com base na análise acima:

Na prática, raramente é possível utilizar um hash com 100% de precisão (i.e. que leve em consideração a estrutura completa do objeto em sua composição) e ainda atingir uma performance aceitável ao colocar esse hash em prática. Se os objetos forem muito grandes - seja por ter muitas propriedades, aninhadas ou não, seja por conterem um grande volume de dados - a performance "global" vai ser ruim, independentemente do método escolhido.

O que torna "serializar um objeto em JSON e fazer o hash da string" ineficiente não é a serialização, e sim o fato de você estar almejando 100% de precisão. E se isso for mesmo necessário, fique com sua implementação, pois ela de fato (como seus testes mostraram) é mais eficiente que meus métodos 3 e 4 acima.

Vou deixar apenas mais um exemplo, caso ainda não tenha sido claro. Como você faria para colocar as seguintes strings numa tabela hash:

"123blábláblábláblá...10Mb depois...bláblá"
"345blábláblábláblá...10Mb depois...bláblá"
"678blábláblábláblá...10Mb depois...bláblá"
  1. Usando o conteúdo completo da string no hash?
  2. Usando só os primeiros 256 bytes e ignorando o resto?

(e, se suas opções fossem usar o conteúdo completo, ou não usar hash nenhum e em vez disso usar um dicionário/mapeamento baseado em árvore, qual você escolheria?)

6
  • O que seria a função hashString?
    – BrunoLM
    Commented 17/12/2013 às 17:03
  • @BrunoLM Apenas um exemplo... Você precisaria de um método diferente para calcular o hash de cada tipo de dados. Naquela outra pergunta você comentou que pegou o código hash de alguma outra pergunta no SO, certo? Esse código [tirando a primeira linha] seria um bom candidato para hashString - ainda que ele seja inadequado para objetos complexos IMHO.
    – mgibsonbr
    Commented 17/12/2013 às 17:07
  • Entendi, obrigado :)
    – BrunoLM
    Commented 17/12/2013 às 17:07
  • P.S. Alguém poderia me sugerir uma palavra melhor que homogeneidade? O que quero dizer é que os objetos (domínio) devem estar igualmente distribuídos sobre os hashes (contra-domínio ou imagem). "Homogeneidade" sugere que os hashes seriam parecidos para todo objeto, o que é justamente o contrário do que estou tentando dizer... Não sei se fui claro :P
    – mgibsonbr
    Commented 17/12/2013 às 17:16
  • Olha, não sei se fiz algo errado, mas segundo meus testes aquele meu método ali parece ser mais rapido jsperf.com/js-hashcode-custom
    – BrunoLM
    Commented 17/12/2013 às 18:28
0

Se o propósito for comparar dois objetos, você pode tentar uma implementação semelhante a isEqual() do underscore.js

http://documentcloud.github.io/underscore/docs/underscore.html#section-88

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .