O Que São Hash Tables em TypeScript: Conceitos, Exemplos e Uso com Redis

Introdução

As hash tables (ou tabelas de dispersão) são uma estrutura de dados fundamental utilizada para armazenar pares de chave-valor de maneira eficiente. Elas são especialmente úteis quando precisamos acessar dados rapidamente sem precisar percorrer toda uma lista. Neste post, vamos explorar como funcionam, como implementá-las em TypeScript, e como o Redis aplica esse conceito.

O Que é uma Hash Table?

Uma hash table é uma estrutura que associa chaves a valores utilizando uma função hash para converter uma chave em um índice de um array onde o valor é armazenado. Esse processo permite operações rápidas de busca, inserção e remoção, geralmente com complexidade de tempo O(1).

Funcionamento Básico

1. Função Hash: Converte uma chave em um número inteiro que será utilizado como índice do array.
2. Armazenamento: O valor é armazenado na posição calculada pela função hash.
3. Busca: Para recuperar um valor, aplicamos novamente a função hash na chave e acessamos o índice correspondente.

Tratamento de Colisões

Colisões ocorrem quando duas chaves diferentes resultam no mesmo índice. Métodos comuns para tratar colisões incluem:

• Encadeamento: Armazenar múltiplos valores no mesmo índice usando listas ligadas.
• Endereçamento Aberto: Procurar o próximo índice disponível.

Implementação em TypeScript

Vamos implementar uma versão básica de uma hash table utilizando TypeScript. Este exemplo é inspirado no livro "Entendendo Algoritmos" de Aditya Bhargava.

class HashTable {
  private table: { [key: string]: [string, any][] } = {};

  private hash(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % 37;
  }

  public put(key: string, value: any): void {
    const position = this.hash(key);
    if (!this.table[position]) {
      this.table[position] = [];
    }

    const index = this.table[position].findIndex(([k]) => k === key);
    if (index >= 0) {
      this.table[position][index][1] = value; // Atualiza o valor existente
    } else {
      this.table[position].push([key, value]); // Adiciona um novo par chave-valor
    }
  }

  public get(key: string): any {
    const position = this.hash(key);
    const bucket = this.table[position];

    if (bucket) {
      const found = bucket.find(([k]) => k === key);
      return found ? found[1] : undefined;
    }

    return undefined;
  }

  public remove(key: string): void {
    const position = this.hash(key);
    const bucket = this.table[position];

    if (bucket) {
      const index = bucket.findIndex(([k]) => k === key);
      if (index >= 0) {
        bucket.splice(index, 1);
      }
    }
  }
}

Exemplo de Uso com Arrays

As hash tables podem ser usadas para melhorar buscas em arrays. Por exemplo, se quisermos verificar rapidamente a existência de um número em um array:

function findNumber(arr: number[], target: number): boolean {
  const hashTable = new HashTable();

  for (const num of arr) {
    hashTable.put(num.toString(), true);
  }

  return hashTable.get(target.toString()) !== undefined;
}

const numbers = [1, 2, 3, 4, 5];
console.log(findNumber(numbers, 3)); // true
console.log(findNumber(numbers, 6)); // false

Redis como Implementação de Hash Table

O Redis é um banco de dados em memória que utiliza conceitos de hash tables para armazenar dados de maneira rápida e eficiente. No Redis, podemos usar o tipo de dado HASH para armazenar e acessar pares chave-valor aninhados.

Exemplo de Uso com Redis

import Redis from 'ioredis';

const redis = new Redis();

// Armazenar um hash no Redis
await redis.set('user:1', 'name', 'Lucas', 'age', '30');

// Recuperar um valor específico
const name = await redis.get('user:1', 'name');
console.log(name); // Saída: Lucas

// Recuperar todos os campos de um hash
const user = await redis.getall('user:1');
console.log(user); // Saída: { name: 'Lucas', age: '30' }

Conclusão

As hash tables são uma das estruturas de dados mais importantes na ciência da computação por fornecerem acessos rápidos a dados. O Redis é um exemplo popular de aplicação de hash tables em um banco de dados rápido e eficiente. Ao entender como implementar e utilizar hash tables em TypeScript, você pode criar aplicações mais performáticas e escaláveis.

Referências

• Bhargava, Aditya. Entendendo Algoritmos: Um guia ilustrado para programadores e outros curiosos. Novatec, 2016.
• WebDevTutor - TypeScript HashTable Example
• Ricardo Borges - Data Structures in TypeScript
• Andrei Pfeiffer - TypeScript Hash Maps