Hash Tables

Olá, sejam bem-vindos a mais uma aula do curso de Estruturas de Dados. Nessa aula, vamos falar sobre hash tables.

Mas eu gostaria de seguir uma outra abordagem. Vamos começar com um problema e, a partir dele, vamos entender o que são hash tables e como elas funcionam.

Problema

O problema é bem simples. Queremos implementar um algoritmo que encontra, em uma string, o primeiro caractere que se repete. Por exemplo, na string “abacabad”, o primeiro caractere que se repete é o caractere “a”.

NOTA: Para esse problema, vamos considerar apenas caracteres ASCII, com letras minúsculas e sem acentos.

Podemos resolver esse problema com as estruturas que já vimos até aqui, com certeza.

Usando arrays podemos fazer:

def first_repeated_char(string)
  chars = Array.new(26, 0)
  string.each_char do |char|
    index = char.ord

    return char if chars[index] == 1

    chars[index] += 1
  end
end

A implementação acima resolve o problema, mas não é muito eficiente em termos de espaço. Veja para um exemplo de uma string pequena o que acontece:

# TODO: Implementar

Perceba que usar o código do ascii como índice, parece, mas não é uma boa ideia. Sabemos que nosso alfabeto tem 26 letrar mas nosso array já tem mais de 6 posições. Isso é um desperdício de espaço.

Além do que, isso só é possível em linguagens como Ruby que permitem arrays de tamanho variável - e essas realocações têm seu custo como bem sabemos da aula de arrays. Em linguagens como C, por exemplo, isso não seria possível.

Bom, alocamos um Array de 26 posições e não precisamos de mais do que isso. Nosso problema agora é achar uma forma de mapear os códigos ASCII das letras para índices de 0 a 25.

Vamos criar uma função que recebe um caracter e retorna um índice de 0 a 25. Chamaremos essa função de hash.

def hash(char)
  char.ord % 97 # 'a'.ord == 97
end

Assim, substituímos o index = char.ord por index = hash(char) temos:

def first_repeated_char(string)
  chars = Array.new(26, 0)
  string.each_char do |char|
    index = hash(char)

    return char if chars[index] == 1

    chars[index] = 1
  end
  nil
end

Função de Hash

Em nosso caso: A função de hash é uma função que recebe uma chave e retorna um índice na tabela. No nosso caso, a chave é um caractere e o índice é um número de 0 a 25.

Em geral: A função hash é uma função que recebe um input arbitrário e retorna uma sequência fixa de bytes dentro de um espaço determinado.

Propriedades de uma Função de Hash

  • Determinística: A mesma entrada sempre produz a mesma saída.
  • Rápida: A função de hash deve ser rápida de calcular.
  • Uniforme: A função de hash deve distribuir as chaves uniformemente pelo espaço de índices.
  • Eficiente: A função de hash deve ser eficiente em termos de espaço.
  • Resistente a Colisões: A função de hash deve minimizar colisões.

Hash Tables

Uma hash table é uma estrutura de dados que mapeia chaves a valores. É uma estrutura de dados que permite a busca, inserção e remoção de elementos em tempo constante*. As hash tables recebem esse nome por utilizarem uma função de hash para mapear chaves a valores.

* No pior caso, a busca, inserção e remoção em uma hash table é O(n), mas, em média, é O(1).

Em nosso exemplo fizemos bem isso. Mapeamos chave (código ASCII de um caractere) a valor (1 ou 0 para indicar se aquele caractere já existia).

O Hash vem da Função de Hash, mas o Table vem de onde?

Naturalmente espera-se que tenhamos uma tabela em algum momento. E temos. A tabela é um array. Cada índice do array é um bucket. Cada bucket é uma lista encadeada de pares chave-valor.

Em nosso exemplo anterior é como se tívemos uma tabela com uma única coluna apenas.

[mostrar no excel como uma hash table é fazendo as clunas serem os buckets e as linhas serem os elementos]

ADT Hash Table

  • build(X): Cria uma nova hash table.
  • insert(key, value): Insere um novo par chave-valor na hash table.
  • delete(key): Remove um par chave-valor da hash table.
  • search(key): Busca um valor a partir de uma chave.

Implementando uma Hash Table

class HashTable
  def initialize
    @table = Array.new(1000)
  end

  def insert(key, value)
    index = hash(key)
    @table[index] = value
  end

  def delete(key)
    index = hash(key)
    @table[index] = nil
  end

  def search(key)
    index = hash(key)
    @table[index]
  end

  private

  def hash(key)
    key.hash % 1000
  end
end

Casos de Uso

  • Dicionários: Hash tables são muito utilizadas para implementar dicionários.
  • Cache: Hash tables são muito utilizadas para implementar caches.
  • Conjuntos: Hash tables são muito utilizadas para implementar conjuntos.
  • Contagem de Elementos: Hash tables são muito utilizadas para contar elementos.
  • Indexação: Hash tables são muito utilizadas para indexar elementos.
  • …

Implementando Set com Hash Table

class Set
  def initialize
    @table = HashTable.new
  end

  def add(value)
    @table.insert(value, true)
  end

  def delete(value)
    @table.delete(value)
  end

  def include?(value)
    @table.search(value) != nil
  end
end

Tempos de execução:

  • add: O(1)
  • delete: O(1)
  • include?: O(1)