Hash Tables

Hash Tables

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. A função de hash é uma função que recebe uma chave e retorna um índice na tabela.

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