Hash tables em JavaScript – array associativo de hashing em JS

Artigo original: JavaScript Hash Table – Associative Array Hashing in JS

Hash tables são estruturas de dados que vão permitir que você crie uma lista de valores pareados. Você pode, então, recuperar determinado valor usando a respectiva chave para aquele valor, que você coloca na tabela de antemão.

Uma hash table transforma uma chave em um número inteiro, que serve como índice, usando uma função hash. Esse índice decidirá onde armazenar na memória o par chave/valor:

Você normalmente usará uma hash table por suas rápidas operações de busca, inserção e remoção:

Retirado da Wikipédia

Esse tutorial ajudará você a entender implementações de hash tables no JavaScript e também mostrará como você pode construir suas próprias classes de hash table.

Primeiramente, vamos dar uma olhada nas classes do JavaScript Object e Map.

Como usar hash tables com as classes Object e Map em JavaScript

O exemplo mais comum de uma hash table em JavaScript é a estrutura de dados Object, onde você pode parear duas propriedades de chave e valor.

No exemplo a seguir, a chave Nathan está pareada com o numero de telefone de valor "555-0182" e a chave Jane está pareada com o valor "315-0322":

let obj = {
  Nathan: "555-0182",
  Jane: "315-0322"
}

Porém, a estrutura de dados do tipo Object em JavaScript é um tipo especial de implementação de uma hash table por duas razões:

• Ela tem propriedades adicionadas pela classe Object. Chaves que você insere podem entrar em conflito e sobrescrever propriedades padrão já herdadas da classe.
• O tamanho de uma hash table não é monitorado. Você precisa contar manualmente quantas propriedades são definidas pelo programador ao invés de herdar do prototype.

Por exemplo, o prototype de Object  tem o método hasOwnProperty(), que sempre permitirá a você checar se uma propriedade não é herdada:

const obj = {};
obj.name = "Nathan";

console.log(obj.hasOwnProperty("name")); // true

O JavaScript não impede você de tentar sobrescrever o método hasOwnProperty(), o que pode causar um erro deste tipo:

const obj = {};
obj.name = "Nathan";
obj.hasOwnProperty = true;

console.log(obj.hasOwnProperty("name")); 
// Error: obj.hasOwnProperty is not a function

Para lidar com essas deficiências, o JavaScript criou uma outra implementação de estrutura de dados hash table chamada Map

Assim como Object, Map permite a você guardar pares chave/valor dentro de uma estrutura de dados. Aqui está um exemplo de Map em ação:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection.set("Jane", "555-0182");

console.log(collection.get("Nathan")); // 555-0182
console.log(collection.size); // 2

Ao contrário do tipo Object, Map requer que você use os métodos set() e get() para definir e buscar quaisquer valores de chave/valor que desejar adicionar à estrutura de dados.

Você também não consegue sobrescrever, em  Map, propriedades herdadas. Por exemplo, o código a seguir tentou sobrescrever o valor da propriedade size para  false:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection["size"] = false;

console.log(collection.get("size")); // undefined
console.log(collection.size); // 1

Como você pode ver no código acima, você não pode adicionar uma nova entrada para o objeto Map sem usar o método set().

A estrutura de dados Map é iterável também, o que significa que você pode fazer um loop para percorrer os dados como no código a seguir:

const myMap = new Map();

myMap.set("Nathan", "555-0182");
myMap.set("Jane", "315-0322");

for (let [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}

Agora que você aprendeu como JavaScript implementa hash tables nas estruturas de dados Object e Map, vamos ver como você pode criar sua própria implementação de uma hash table a seguir.

Como implementar uma estrutura de dados de hash table em JavaScript

Embora o JavaScript já tenha duas implementações de hash table, escrever sua própria implementação é uma dos exercícios mais comuns de entrevistas de  emprego que envolvem JavaScript.

Você pode implementar uma hash table em JavaScript em três passos:

• Criar uma classe HashTable com table e size como propriedades iniciais
• Adicionar uma função hash() para transformar chaves em índices, index em inglês
• Adicionar métodos set() e get() para inserir e obter pares de chave/valor da tabela.

Dito isso, começaremos  criando uma classe HashTable. O código abaixo criará uma table com 127 espaços para armazenamento:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }
}

Todos seus pares de chave/valor serão armazenados dentro da propriedade table.

Como escrever o método hash()

A seguir, você precisa criar o método hash() que aceitará um valor key e transformá-lo em um index.

Um jeito simples de criar a hash seria somar o código ASCII dos caracteres na chave usando o método charCodeAt() como é feito abaixo. Note que o método é nomeado usando _  para indicar que essa é uma classe privada:

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash;
}

Considerando, no entanto, que a classe HashTable tem apenas 127 espaços, o método _hash() deve retornar um número entre 0 e 127.

Para assegurar que o valor do hash não excederá o tamanho permitido, você precisa usar o operador módulo como é mostrado a seguir:

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.table.length;
}

Agora que você tem o método _hash() completo, é hora de escrever os métodos set() e get().

Como criar o método set()

Para inserir os pares de chave/valor na sua hash table, você precisa escrever um método set() que aceita como parâmetros (chave, valor):

• O método set() chamará o método _hash() para obter o valor do index
• O par [chave, valor]  será atribuído na tabela noindex especificado
• Então, a propriedade size será incrementada uma vez

set(key, value) {
  const index = this._hash(key);
  this.table[index] = [key, value];
  this.size++;
}

Agora que o método set() está completo, vamos escrever o método get() para obter o valor por sua chave.

Como escrever o método get()

Para obter um certo valor da hash table, você precisa escrever um método get() que aceita um valor key como parâmetro:

• O método chamará o método _hash() novamente para obter na tabela o index
• Retorne o valor guardado em table[index]

get(key) {
  const index = this._hash(key);
  return this.table[index];
}

Desse modo, o método get() retornará o par chave/valor ou undefined quando não tiver nenhum par de chave/valor guardado no index especificado.

Tudo certo por enquanto. Vamos, a seguir, adicionar outro método para excluir um par de chave/valor da hash table.

Como escrever o método remove()

Para excluir um par de chave/valor da hash table, você precisa escrever um método remove(), que aceita um valor key como parâmetro:

• Obtenha o index certo usando o método _hash()
• Confira se table[index] tem um valor verdadeiro (truthy, em inglês) e se a propriedade length é maior que zero. Atribua o valor undefined para index e decremente a propriedade size se possível.
• Caso contrário, simplesmente retorne false

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    this.table[index] = undefined;
    this.size--;
    return true;
  } else {
    return false;
  }
}

Com isso, você agora tem um método remove() funcionando. Vamos ver se a classe HashTable funciona corretamente.

Como testar a implementação da hash table

É hora de testar a implementação da hash table. Aqui está, novamente, o código completo para a implementação da hash table:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this._hash(key);
    this.table[index] = [key, value];
    this.size++;
  }

  get(key) {
    const target = this._hash(key);
    return this.table[target];
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      this.table[index] = [];
      this.size--;
      return true;
    } else {
      return false;
    }
  }
}

Para testar a classe HashTable, eu vou criar uma nova instância da classe e configurar alguns pares de chave e valor como mostrado abaixo. Os pares de chave/valor abaixo contém apenas valores arbitrários combinados sem nenhum significado especial:

const ht = new HashTable();
ht.set("Canada", 300);
ht.set("France", 100);
ht.set("Spain", 110);

Então, vamos tentar obtê-los usando o método get():

console.log(ht.get("Canada")); // [ 'Canada', 300 ]
console.log(ht.get("France")); // [ 'France', 100 ]
console.log(ht.get("Spain")); // [ 'Spain', 110 ]

Finalmente, vamos tentar excluir um desses valores com o método remove():

console.log(ht.remove("Spain")); // true
console.log(ht.get("Spain")); // undefined

Tudo bem, todos os métodos estão funcionando como esperado. Vamos tentar outra inserção com uma nova instância de HashTable e obter esses valores:

const ht = new HashTable();

ht.set("Spain", 110);
ht.set("ǻ", 192);

console.log(ht.get("Spain")); // [ 'ǻ', 192 ]
console.log(ht.get("ǻ")); // [ 'ǻ', 192 ]

Opa! Parece que nós temos um problema aqui. 😨

Como resolver os conflitos de index

Algumas vezes, a função hash em uma hash table pode retornar o mesmo index. No caso de teste acima, a string "Spain" e "ǻ" retornam o mesmo valor de hash, pois o número 507 é a soma de ambos os códigos ASCII.

O mesmo valor hash fará com que os índices entrem em conflito, sobrescrevendo o anterior com o novo valor configurado.

Até agora, o dado guardado em nossa implementação de hash table tem essa aparência:

[
    [ "Spain", 110],
    [ "France", 100]
]

Para resolver o conflito de index, você precisa guardar o par de chave/valor em um array secundário de modo que o resultado final seja algo assim:

[
    [
        [ "Spain", 110 ],
        [ "ǻ", 192 ]
    ],
    [
        ["France", 100]
    ],
]

Para criar o segundo array, você precisa atualizar o método set() para que ele:

• Procure o table[index] e itere sobre seus valores.
• Se a chave em um dos arrays for igual ao parâmetro key passado ao método, repita o valor no index 1 e pare quaisquer execuções futuras declarando um return.
• Se não encontrar nenhuma key igual, crie um novo array de chave e valor para o segundo array.
• Então, inicialize um novo array e coloque o par de chave/valor no index especificado.
• Sempre que um método push() for chamado, incremente a propriedade size em uma unidade.

O código do método set() completo está abaixo:

set(key, value) {
  const index = this._hash(key);
  if (this.table[index]) {
    for (let i = 0; i < this.table[index].length; i++) {
      //Encontre o par chave/valor na cadeia
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    //Se não for encontrado, crie um novo par de chave/valor
    this.table[index].push([key, value]);
  } else {
    this.table[index] = [];
    this.table[index].push([key, value]);
  }
  this.size++;
}

A seguir, atualize o método get() de maneira que ele também confira o array de segundo nível com um laço for e retorne o par correto de chave/valor:

get(key) {
  const target = this._hash(key);
  if (this.table[target]) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[target][i][0] === key) {
        return this.table[target][i][1];
      }
    }
  }
  return undefined;
}

Finalmente, você precisa atualizar o método remove() para que ele faça um laço para iterar sobre o array de segundo nível e remova o array com o valor da key correta usando o método splice():

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        this.size--;
        return true;
      }
    }
  } else {
    return false;
  }
}

Com isso, sua classe HashTable será capaz de evitar quaisquer conflitos de index eventuais e guardará o par de chave/valor dentro do array de segundo nível.

Como bônus, vamos adicionar um método display() que mostrará todos os pares de chave/valor guardados na Hash Table. Você só precisa usar o método forEach() para iterar sobre a tabela e usar map() para mapear os valores para uma string assim como no exemplo a seguir:

display() {
  this.table.forEach((values, index) => {
    const chainedValues = values.map(
      ([key, value]) => `[ ${key}: ${value} ]`
    );
    console.log(`${index}: ${chainedValues}`);
  });
}

Aqui está o código da classe HashTable completo novamente com a aplicação correta para a resolução do conflito de índices, para sua referência:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index][i][1] = value;
          return;
        }
      }
      this.table[index].push([key, value]);
    } else {
      this.table[index] = [];
      this.table[index].push([key, value]);
    }
    this.size++;
  }

  get(key) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          return this.table[index][i][1];
        }
      }
    }
    return undefined;
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index].splice(i, 1);
          this.size--;
          return true;
        }
      }
    } else {
      return false;
    }
  }

  display() {
    this.table.forEach((values, index) => {
      const chainedValues = values.map(
        ([key, value]) => `[ ${key}: ${value} ]`
      );
      console.log(`${index}: ${chainedValues}`);
    });
  }
}

Você pode testar a implementação criando uma nova instância de HashTable e fazer algumas inserções e remoções:

const ht = new HashTable();

ht.set("France", 111);
ht.set("Spain", 150);
ht.set("ǻ", 192);

ht.display();
// 83: [ France: 111 ]
// 126: [ Spain: 150 ],[ ǻ: 192 ]

console.log(ht.size); // 3
ht.remove("Spain");
ht.display();
// 83: [ France: 111 ]
// 126: [ ǻ: 192 ]

Aqui, não houve conflitos dentro da instância da HashTable. Ótimo trabalho!

Conclusão

Nesse tutorial, você aprendeu o que é uma hash table e como o JavaScript a usa para criar as estruturas de dados Object e Map.

Você também aprendeu como implementar sua própria classe HashTable e como evitar o conflito de índices na hash table usando a técnica de encadeamento.

Ao usar a estrutura de dados hash table, você será capaz de criar um array associativo com operações rápidas de busca, inserção e remoção. 😉

Obrigado por ler esse tutorial

Se você quiser ler mais sobre JavaScript, pode dar uma olhada no meu site pessoal, sebhastian.com, onde eu tenho publicados mais de 100 tutoriais sobre programação em JavaScript, todos eles usando explicações bem fáceis de entender e exemplos de código.

Os tutoriais incluem manipulação de strings, manipulação de datas, métodos de arrays e de objetos, soluções de algoritmos em JavaScript e muito mais.