Uma tabela de dispersão é uma estrutura de dados que permite associar chaves a valores e realizar pesquisas sobre os pares chave valor guardados de forma eficiente, idealmente em tempo constante, i.e., $O(1)$. As tabelas de dispersão consistem em geral numa tabela e numa função de dispersão em que, dada uma chave, a função de dispersão é utilizada para determinar o índice na tabela onde será guardado o par chave valor. É claro que podemos ter colisões, ou seja, pode acontecer que várias chaves sejam mapeadas pela função de dispersão para a mesma posição na tabela, caso em que é necessário resolver as colisões. Este é em particular o problema fundamental na escolha das funções de dispersão, que depende claramente do universo das chaves em cada problema, e na implementação de estratégias para resolver colisões em tabelas de dispersão. Nesta aula vamos ver como resolver colisões através de encadeamento externo.
Motivação
Tendo em conta o que vimos nas aulas anteriores, se as chaves que queremos guardar forem inteiros consecutivos entre $0$ e $N$, podemos utilizar simplesmente uma tabela ou vector para indexar os pares chave valor. Mas o que podemos fazer se $N$ for muito grande e apenas for necessário guardar uma pequena parte das chaves possíveis ($k << N$)? E se tivermos como chaves sequências de caracteres em vez de inteiros? É verdade que poderíamos utilizar por exemplo uma lista ligada, mas nesse caso a procura por uma chave é linear no número de elementos guardados na lista... Será que conseguimos fazer melhor?
As tabelas de dispersão são uma das estruturas de dados úteis para este tipo de problemas em que temos um número elevado $N$ de chaves possíveis, por exemplo todos os nomes possíveis ou todos os NIFs, mas em que apenas precisamos de guardar parte dessas chaves, por exemplo $k << N$. Neste caso, dada uma chave, aplicamos a função de dispersão para obter um índice na tabela e, idealmente, obtemos o elemento em tempo constante tal como acontece numa tabela, mas sem utilizar espaço desnecessariamente.
/* Processo para guardar e procurar elementos: * +---+ * +----> | | * | +---+ * Antonio, Lisboa, 234100898 -+ | | | * \ +---------------+ | +---+ * Jose, Porto, 204511321 -------+--> | Hash function |----+----> | | * / +---------------+ | +---+ * Maria, Lisboa, 130456101 ---+ | | | * +----> +---+ * | | * ... */
Função de dispersão
Uma função de dispersão mapeia valores, não limitados em geral, para valores limitados como os índices de uma tabela. No caso particular das tabelas de dispersão, cada chave é mapeada para um índice da tabela, ou seja um inteiro $i$ tal que $0\leq i \leq M-1$, em que $M$ é a dimensão da tabela.
Diz-se que ocorre uma colisão quando a função de dispersão devolve o mesmo valor, ou seja o mesmo índice no caso das tabelas, para chaves distintas.
A escolha de uma função de dispersão é em geral não trivial e depende do universo de chaves em questão. Idealmente, dado um universo de chaves, a função de dispersão deve ser tal que os elementos são mapeados de forma uniforme, ou seja, a probabilidade da função de dispersão retornar um mesmo índice para duas chaves diferentes deve ser $1/M$ onde $M$ é a dimensão da tabela. Neste caso diz-se que a função de dispersão é universal ou 2-universal. Notar que existem diferentes construções para tabelas de dispersão que implicam diferentes garantias ao nível da independência e universalidade das funções de dispersão, no entanto este assunto sai fora do âmbito desta disciplina e será objecto de estudo na disciplina de Algoritmos Avançados.
No que se segue, uma função de dispersão deverá:
- distribuir as chaves de forma uniforme e quase aleatória;
- ser rápida de calcular;
- envolver todos os bits da chave.
Notar ainda que diferentes funções devem ser usadas para diferentes tipos de dados, e.g., cadeias de caracteres, inteiros, ou reais. Vejamos alguns exemplos de funções de dispersão (existem outras variantes e funções diferentes).
No caso das chaves serem números inteiros podemos utilizar uma função de dispersão do género: $$ h(k) = k \mod M$$ em que o valor $M$ deve ser um número primo por forma a diminuir a probabilidade de colisões (porquê?). Em alternativa podemos utilizar o seguinte esquema: $$ h_a = ((a k) \mod p) \mod M$$ em que $p$ é um número primo tal que $p >> M$. Podemos também não utilizar aritmética modular para sermos mais rápidos, mas perdendo alguma independência.
No caso das chaves serem sequências de caracteres podemos calcular uma soma ponderada dos caracteres, módulo $M$, tendo os mesmo cuidados que no caso anterior:
int hash(char *v, int M)
{
int h = 0, a = 127;
for (; *v != ’\0’; v++)
h = (a*h + *v) % M;
return h;
}Podemos também alterar a base $a$ em cada iteração para evitar anomalias com chaves irregulares (entre outras possibilidades):
int hashU(char *v, int M)
{
int h, a = 31415, b = 27183;
for (h = 0; *v != ’\0’; v++, a = a*b % (M-1))
h = (a*h + *v) % M;
return h;
}NOTA IMPORTANTE: Em resumo, a função de dispersão deve em geral ser escolhida tendo em conta o problema em estudo e o universo de chaves em questão. Caso a informação a respeito destes não exista, deve ser escolhida uma função de dispersão universal e com garantias de independência razoáveis.
Resolução de colisões por encadeamento externo
Ainda que possamos escolher boas funções de dispersão, podem ocorrer colisões ainda que com baixa probabilidade. Portanto, uma vez que não queremos perder elementos e queremos manter eficiência na inserção e na procura, como é que podemos resolver colisões?
Existem diferentes estratégias. Nesta aula vamos estudar como resolver colisões por encadeamento externo. Na próxima aula veremos como utilizar endereçamento aberto.
No caso da resolução por encadeamento externo cada posição da tabela tem um ponteiro para uma lista ligada e, na inserção de novos elementos, as colisões são resolvidas juntando o elemento ao início da lista na posição da tabela respectiva. As remoções de elementos são resolvidas através da remoção do elemento da lista respectiva.
/* * +---+ +----+----+ +----+----+ +-----+----+ * 0 | -+-->| 70 | -+-->| 14 | -+-->| 707 | -+--> NULL * +---+ +----+----+ +----+----+ +-----+----+ * 1 | | * +---+ +----+----+ * 2 | -+-->| 10 | -+--> NULL * +---+ +----+----+ * 3 | | * +---+ * 4 | | * +---+ * 5 | | * +---+ +----+----+ +----+----+ * 6 | -+-->| 20 | -+-->| 76 + -+--> NULL * +---+ +----+----+ +----+----+ * * Ordem de insercao: 707, 72, 14, 70, 76, 20. * Funcao de dispersao: h(k) = k mod 7 */
Implementação
static link *heads;
static int M;
void STinit(int max) {
int i;
M = max;
heads = (link*)malloc(M*sizeof(link));
for (i = 0; i < M; i++) heads[i] = NULL;
}
Item STsearch(Key v) {
return searchList(heads[hash(v, M)], v);
}
void STinsert(Item item) {
int i = hash(key(item), M);
heads[i] = insertBeginList(heads[i], item);
}
void STdelete(Item item) {
int i = hash(key(item), M);
heads[i] = removeItemList(heads[i], item);
}Análise
- O comprimento médio das listas é $N/M$, em que $N$ é o número de elementos e $M$ é o tamanho da tabela.
- A probabilidade de o número de chaves numa lista ser maior do que $t\alpha$ é menor que $(\frac{e}{t})^{t\alpha} e^{-\alpha}$, onde $\alpha = \frac{N}{M}$, utilizando um Chernoff bound.
- Se $\alpha = 20$, a probabilidade de uma lista ter $40$ elementos é no máximo $0.000441$.
Exercício
Considere a seguinte função de dispersão:
int hash(int value, int M) {
return value % M;
}Usando uma tabela de dispersão com resolução por encadeamento externo (external chaining) para guardar elementos com as seguintes chaves
int v[12] = {13, 11, 10, 2, 22, 35, 45, 1, 143, 333, 6, 99998};e a função de dispersão definida em cima, sabendo que M = 10, qual ou quais são as chaves dos elementos guardados na posição de índice igual a 3 da tabela? Indique o número de colisões.
Função hsearch
Existem algumas funções definidas em search.h que nos permitem gerir uma tabela de dispersão. As entradas do tipo ENTRY nessa tabela consistem numa chave e num valor associado. O tipo ENTRY está definido em search.h como:
typedef struct entry {
char *key;
void *data;
} ENTRY;As funções disponíveis para gerir a tabela de dispersão são as seguintes:
int hcreate(size_t nel), que permite criar a tabela de dispersão;ENTRY *hsearch(ENTRY item, ACTION action), que permite procurar um elemento com um chave igual à do elementoiteme, se o encontrar, retorna um ponteiro para o mesmo;void hdestroy(void), que permite libertar a memória alocada para a tabela de dispersão pela funçãohcreate.
O segundo parâmetro do tipo ACTION na função hsearch é uma enumeração com dois valores possíveis, ENTER e FIND, e define o comportamento da função. Se a action for FIND é efectuada uma procura pela chave do elemento item e é retornado um ponteiro para um elemento com a mesma chave se existir, ou NULL no caso contrário. Se a action for ENTER ocorre a substituição de um dos elementos com a mesma chave que o elemento item, ou é inserido o elemento item se não existir nenhum elemento com a mesma chave.
Notar que estas funções apenas permitem que exista uma instância da tabela de dispersão. Para utilizarmos múltiplas instâncias podemos utilizar em alternativa as funções int hcreate_r, int hsearch_r, e int hdestroy_r, extensões da GNU (#define _GNU_SOURCE). Estas funções funcionam de forma equivalente às anteriores, mas recebem como parâmetro a tabela de dispersão sobre a qual deverá ser realizada a operações.
Exemplo de utilização destas funções:
/**
* @file hsearch.c
* @brief Experiencias com tabelas de dispersao.
*
* Experiencias com as funcoes hcreate, hsearch, e hdestroy, sobre
* uma tabela de dispersao.
*/
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#define NELEM 16
#define BUFFSIZE 128
int
main(int argc, char *argv[])
{
ENTRY e, *ep, v[NELEM];
char c, buffer[BUFFSIZE];
size_t i = 0, k;
hcreate(NELEM);
while ((c = getchar()) != 'x') {
getchar();
scanf("%s", buffer);
getchar();
if (c == 'e' && i < NELEM) {
v[i].key = strdup(buffer);
v[i].data = (void *) i;
ep = hsearch(v[i], ENTER);
i++;
} else if (c == 'e') {
printf("No more space!\n");
} else if (c == 'f') {
e.key = buffer;
ep = hsearch(e, FIND);
if (ep != NULL) {
printf("Found: %s %lu\n", ep->key, (size_t) ep->data);
} else {
printf("Not found!\n");
}
}
}
hdestroy();
for (k = 0; k < i; k++)
free(v[k].key);
return EXIT_SUCCESS;
}Compilar e executar:
[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic -o hsearch hsearch.c [aplf@darkstar ~]$ ./hsearch e ab34 e ac23 e ci12 f di12 Not found! f ac23 Found: ac23 1 x [aplf@darkstar ~]$