Hash

Tabelas de hash
Diego de Freitas Aranha – IC/UNICAMP

4 de setembro de 2007

Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash

Tabelas de hash

Tabelas de hash s˜ao u
´teis para implementar a funcionalidade de um dicion´ario T .
Dicion´ario T
Inserir(T , x): inserir elemento x no conjunto T ;
Remover(T , x): remover elemento x do conjunto T ;
Buscar(T , x): retornar elemento x no conjunto T , quando x ∈ T.
Exemplo: tabela de s´ımbolos de um compilador;
Objetivo: realizar opera¸c˜ oes em tempo constante!(tempo esperado)

Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash

Tabelas de endere¸camento direto
Cada elemento ´e identificado por uma chave em N;
Quando o universo de chaves U = {0, 1, . . . , m − 1} ´e pequeno, a tabela pode ser implementada como um vetor.
Cada posi¸c˜ao representa uma chave de U e armazena um elemento x ou um ponteiro para x.

Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash

Tabelas de endere¸camento direto - Algoritmos

Inserir-Enderec
¸ amento-Direto(T , x)
T [key [x]] ← x
Remover-Enderec
¸ amento-Direto(T , x)
T [key [x]] ← NIL
Buscar-Enderec
¸ amento-Direto(T , k) return T [k]
Complexidade: as opera¸c˜ oes tomam tempo constante no pior caso.
Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash

Tabelas de hash

Problema
O universo de chaves pode ser muito grande ou esparso.

Solu¸c˜ao: Utilizar uma fun¸c˜ ao de hash h para mapear um elemento x `a sua chave k = h(x).

Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash

Tabelas de hash
A tabela ´e implementada como um vetor de m posi¸c˜oes em que cada posi¸c˜ao armazena um subconjunto de U.

Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash

Tabelas de hash

Vantagem
Se K ´e o conjunto das chaves armazenadas, a tabela requer espa¸co
Θ(|K |) ao inv´es de Θ(|U|).
Desvantagens
Colis˜ ao: duas chaves podem ser mapeadas para a mesma posi¸c˜ao! A busca na tabela requer O(1) no caso m´edio, mas O(n) no pior caso.

Diego de Freitas Aranha – IC/UNICAMP

Tabelas de hash