Hash é, provavelmente, um dos conceitos mais importantes que um programador deve conhecer. É por meio de hashes que conseguimos criar as tabelas hash, armazenar senhas de forma segura, fazer detecção de erros e também compressão de dados. São hashes que também permitem criar sistemas de cache globais em redes de fornecimento de conteúdo, popularmente conhecidas como CDNs.

Formalmente, uma função hash, traduzida em português como “função de espalhamento”, é uma função que mapeia um conjunto de dados de tamanho arbitrário em um conjunto de dados de tamanho fixo. Veja, por exemplo, a função abaixo:

Essa função pode ser considerada uma função hash. Ela receberá um número inteiro qualquer e irá retornar o resto da divisão por dez. Qualquer resto de divisão por um número $n$, será um número entre $0$ e $(n-1)$, ou seja, um intervalo fixo. Veja outra função abaixo:

function hashStr(str) {
  let hashed = 0;
  let i = 0;
  while (i < str.length) {
    hashed = hashed ^ str.charCodeAt(i);
    i += 1;
  }
  return hashed;
}

A função hashStr acima, escrita em JavaScript, também pode ser considerada uma função hash. Afinal, ela converte uma string de tamanho arbitrário em um número, combinando caractere a caractere. O operador ^, nesse exemplo, está fazendo um “ou-exclusivo binário”, que sempre retorna um número de 32 bits.

Os resultados de uma função hash são chamados de hash codes, digests ou simplesmente hashes. Boas funções hash são rápidas e puras, ou seja, a mesma entrada sempre irá retornar a mesma saída.

Diferenciando objetos 🙝

Outro uso bastante comum é a possibilidade de diferenciar rapidamente objetos com múltiplas propriedades. Suponha que você queira comparar dois objetos por meio das propriedades que compõem cada um deles. Uma solução trivial seria comparar cada propriedade, par-à-par, e, se todas forem equivalentes, os objetos serão considerados iguais. No entanto, caso alguma propriedade for diferente, os objetos serão diferentes. Veja a tabela abaixo, onde comparamos dois objetos, A e B:

Se compararmos A e B, vemos que os objetos não são iguais porque a propriedade nascimento é diferente. Note que, precisamos comparar até o momento em que uma propriedade possua valores diferentes. Por isso, a propriedade email sequer é verificada. Assim, esse algoritmo é linearmente proporcional à quantidade de propriedades que devemos comparar.

Essa solução acima pode ser utilizada para objetos pequenos, com algumas dezenas de propriedades. No entanto, imagine um objeto mais complexo, com centenas de propriedades. Ou ainda que seja aninhado, com objetos internos e precisam ser comparados entre si da mesma forma. Você pode ver que, nesse cenário, comparar propriedade por propriedade pode demorar um pouco…

Para nos ajudar com essa tarefa, podemos utilizar hash que sirva como uma “assinatura” para o objeto. Esse hash pode ser criado por meio das propriedades do próprio objeto. Assim, quando compararmos a igualdade de um objeto com outro, podemos verificar primeiro a assinatura. Se a assinatura for diferente, não precisamos verificar nenhuma outra propriedade, porque alguma delas será diferente.

Veja que agora, quando comparamos a propriedade hash, que foi construída a partir das propriedades do objeto, temos imediatamente um valor diferente, sem precisar consultar as outras propriedades. No entanto, se as assinaturas forem iguais, isso significa que os objetos são iguais?

Colisões 🙝

Como já vimos, uma função hash mapeia um conjunto de tamanho arbitrário em um conjunto de tamanho fixo. Como você está mapeando um conjunto de dados possivelmente maior em um conjunto de dados fixo, pelo princípio da casa dos pombos, alguns valores diferentes na entrada vão ser mapeados para uma mesma saída. Quando isso acontece, temos uma colisão.

Colisões são problemáticas para funções hash. Em tabelas hash, colisões diminuem o desempenho. Em criptografia, colisões diminuem a segurança. Em compressão de dados, colisões diminuem a taxa de compactação. Boas funções hash desejam diminuir a taxa de colisão tentando seguir uma distribuição uniforme. Assim, nenhum intervalo terá mais ou menos chances de sofrer colisão.

Em nosso caso de comparação de objetos, colisões nos obrigam a ter que comparar, inevitavelmente, todas as propriedades. Afinal, mesmo que dois objetos tenham o mesmo hash, eles ainda podem ser diferentes. Só conferindo todas as propriedades que temos a garantia que os objetos são realmente iguais. Agora, se assinatura for diferente, temos a garantia de que o objeto não é igual. Por isso, utilizar hashes é uma forma de agilizar o processo de diferenciar objetos.

Apresentando: CRUXHash 🙝

Para facilitar a criação de hashes de valores primitivos ou objetos em JavaScript, criei uma pequena biblioteca: a CRUXHash. Para instalar, utilize o npm.

npm i cruxhash

A CRUXHash é uma biblioteca que provê um conjunto de funções simples para criar hashes inteiros e sem sinal para valores em JavaScript. Veja o exemplo abaixo:

import { hash, getSeed } from 'cruxhash';

console.log(hash('Smile, my dear!')); // 897319059

console.log(hash(42, getSeed('my seed'))); // 1866919164

console.log(hash('コンニチハ, Hello world, Καλημέρα κόσμε 😀')); // 1149923829

A sua principal função, hash, permite criar um hash de qualquer valor primitivo JavaScript: uma string, um booleano, um número… Além disso, permite que você passe, como segundo parâmetro, um seed, um número que inicializa o processo e que pode trazer resultados diferentes de acordo com sua necessidade.

Para tratar de objetos, a função hash trabalha de uma forma especial. Primeiro ela verifica se o objeto possui um método hashCode e passa, recursivamente, seu resultado para o hash. Esse comportamento é útil para reutilizar objetos com um processo de hash já definido. Veja:

import { hash } from 'cruxhash';

const obj = {
  value: 0,
  hashCode() {
    return this.value;
  },
};

console.log(hash(obj)); // 1858670630

obj.value = 1;

console.log(hash(obj)); // 796438301

Se o objeto possuir o método valueOf sobrescrito, como é o caso de objetos instâncias de Date, Number, Boolean, etc… a função hash irá considerá-lo.

import { hash } from 'cruxhash';

console.log(hash(new Date('2014-07-08'))); // 271363852

console.log(hash(new Date('2014-07-08'))); // 271363852

Todo objeto que herde Object.prototype, terá o valueOf implementado. No entanto, essa implementação sempre retorna o próprio objeto. Para evitar uma recursão infinita, o método obriga que o valueOf seja sobrescrito.

Agora, se o objeto implementar o Protocolo Iterável, um hash será criado a partir de cada elemento do iterável e, ao final, todos serão combinados em um hash só. Veja:

import { hash } from 'cruxhash';

const objA = {
  [Symbol.iterator]: function* () {
    yield 0;
    yield 1;
    yield 2;
  },
};

const objB = {
  [Symbol.iterator]: function* () {
    yield 0;
    yield 1;
    yield 2;
  },
};

const objC = {
  [Symbol.iterator]: function* () {
    yield 1;
    yield 2;
    yield 0;
  },
};

console.log(hash(objA)); // 2974883921

console.log(hash(objB)); // 2974883921

console.log(hash(objC)); // 473105883

Veja que, os iteráveis objA e objB possuem uma sequência com os mesmos elementos na mesma ordem e, por isso, seus hashes são idênticos. Veja, também, que a ordem faz diferença. A mudança de ordem dos elementos nos iteráveis objA e objC resulta em um hash completamente diferente.

No entanto, a função hash vai tratar de forma especial estruturas onde a ordem dos elementos não importa, como é o caso do Set ou Map. Veja:

import { hash } from './index';

console.log(hash(new Set([0, 1, 2]))); // 1421611346

console.log(hash(new Set([0, 2, 1]))); // 1421611346

E por fim, caso você passe um objeto simples, o hash será criado com base no Object.entries, ou seja, objetos que possuírem mesmas propriedades com mesmos valores, terão hashes iguais.

import { hash } from './index';

console.log(hash({ a: 1, b: null })); // 1418113148

console.log(hash({ b: null, a: 1 })); // 1418113148

Conclusões 🙝

Finalizo por aqui a apresentação da CRUXHash. A biblioteca disponibiliza outras funções para usos em casos mais específicos. Por isso, recomendo que você veja no repositório oficial a documentação da API disponível.

Criei essa biblioteca de acordo com minha necessidade em projetos pessoais e profissionais. Caso você queira adicionar algum comportamento, entre em contato comigo. PRs são sempre bem vindos!

Agradecimentos 🙝

Agradeço meu amigo Henrique Neves pela revisão e pelas considerações importantes no texto!