Tabelas HASH

Cap. 11 - Tabelas Hash

11.1 – Tabelas de Endereço Direto

O endereçamento direto é uma técnica simples que funciona bem quando o universo U de chaves é razoavelmente pequeno. Suponha que uma aplicação necessite de um conjunto dinâmico no qual cada elemento tenha uma chave definida a partir do universo U = {0, 1, …, m-1}, onde m não é muito grande. Iremos supor que não há dois elementos com a mesma chave.
Para representar o conjunto dinâmico, usamos um arranjo ou tabela de endereço direto T [0…m-1], na qual cada abertura (slot), ou posição , corresponde a uma chave no universo U. Se o conjunto não contém nenhum elemento com a chave k , então T[k] = NULL.
A implementação das operações de dicionário é trivial:

DIRECT-ADRESS-SEARCH (T, k) return T[k]

DIRECT-ADDRESS-INSERT (T, x) T[chave[x]] ← x

DIRECT-ADDRESS-DELETE (T, x) T[chave[x]] ← NULL

Cada uma dessas operações é rápida: é necessário apenas o tempo O(1).

11.2 – Tabelas Hash

A dificuldade com o endereçamento direto é óbvia: se o universo U é grande, o armazenamento de uma tabela T de tamanho |U| pode ser impraticável, ou mesmo impossível, em virtude da memória disponível em um computador típico. Além disso, o conjunto K de chaves realmente armazenadas pode ser tão pequeno em relação a U que a maior parte do espaço alocado para T seria desperdiçada. Quando o conjunto K de chaves armazenadas em um dicionário é muito menor que o universo U de todas as chaves possíveis, uma tabela hash exige muito menos espaço de armazenamento que uma tabela de endereço direto. Especificamente, os requisitos de armazenamento podem ser reduzidos a Ɵ(|K|), embora a pesquisa de um elemento na tabela hash ainda exija apenas o tempo O(1). A única desvantagem é que esse limite corresponde ao tempo médio, enquanto no caso do endereçamento direto ela se mantém válido para o tempo do pior caso.
Com o endereçamento direto, um elemento com a chave k é armazenado na posição k. No caso do hash, esse elemento é