hash = picadinho
to hash = picar,
fazer picadinho, misturar, confundir
Este é um resumo de parte do capítulo 14 do livro de Sedgewick e da seção 11.2 do livro de Roberts.
Uma tabela de dispersão (= hash table) é uma maneira muito popular de organizar uma tabela de símbolos. Tabelas de dispersão são uma generalização do ideia de endereçamento direto. Elas foram concebidas para funcionar bem em média, ou seja, na maioria dos casos; seu desempenho no pior caso é lamentável.
A implementação de uma tabela de dispersão envolve muitas sutilezas que afetam sua eficiência, ainda que não afetem sua correção. O objetivo desta página é apenas chamar a atenção para essas sutilezas; não pretendemos entrar em detalhes sobre os truques e heurísticas usados para enfrentar as dificuldades.
Toda tabela de símbolos armazena objetos de algum tipo. Nesta página, esse tipo será chamado Item. Cada Item tem uma chave, usualmente um número inteiro positivo. As chaves não são necessariamente todas diferentes: dois Items diferentes podem ter chaves iguais.
O universo de chaves é o conjunto de todas as possíveis chaves. Em geral, uma aplicação usa apenas uma pequena parte do universo de chaves. Assim, o tamanho da tabela de símbolos é em geral bem menor que o tamanho do universo de chaves.
Denotaremos o tamanho de nossa tabela por M. A tabela terá a forma tab[0 .. M-1]. É preciso inventar agora uma maneira de mapear o universo de chaves no conjunto de índices da tabela. Esse é o papel da função de espalhamento (= hash function). Ao receber uma chave v, a função de espalhamento devolve
um número inteiro h no intervalo 0..M-1.
O número h é o código de espalhamento (= hash code) da chave v.
O número de Items que queremos armazenar na tabela é, em geral, maior que M. Assim, a função de espalhamento pode levar várias chaves para o mesmo código. Quando duas chaves diferentes são levadas no mesmo código, dizemos que há uma colisão.
Exemplo: Digamos que o universo de chaves é o conjunto dos números inteiros entre 100001 e 9999999 (veja o exemplo no capítulo de tabelas de símbolos). Suponha que M = 100. Podemos adotar os dois últimos dígitos da chave como código de espalhamento. Nesse caso, o código de v é o resto da divisão de v por 100:
chave código 123456 56 7531 31 3677756 56 (Poderíamos igualmente bem ter adotado os dois primeiros dígitos da chave, ou talvez o dígito dos milhares junto com o dígito das dezenas.)
O exemplo ilustra uma função de espalhamento modular: a função leva cada inteiro positivo v no resto da divisão de v por M. Essa função pode ser apresentada assim:
#define hash(v, M) (v % M)
Resta saber o que fazer com as colisões. Há várias maneiras de lidar com essa questão, como veremos adiante.
Qualquer função que leva chaves para o intervalo
0..M-1 de índices serve como função de espalhamento.
Mas uma tal função só é eficiente
se espalha
as chaves pelo
intervalo de índices
de maneira razoavelmente uniforme.
Por exemplo, se as chaves de nossa aplicação são números inteiros
e todas são múltiplos de 100
(ou seja, todas terminam com 00
)
então v % 100
é uma péssima função de espalhamento.
Mesmo que as chaves não sejam múltiplas de 100,
a função v % 100
não é muito boa:
basta imaginar o que acontece
se o penúltimo dígito decimal de toda chave é inferior a 5, por exemplo.
Há casos mais sutis de espalhamento inadequado. Suponha que nossas chaves são números inteiros pares, ou seja, que todas são divisíveis por 2. Suponha que M também é par. É fácil verificar então que todos os índices produzidos pela função modular v % M serão pares. Assim, as posições 1, 3, 5, . . . , M-1 da tabela jamais serão usadas. Um fenômeno semelhante ocorre se há muito mais chaves pares que chaves ímpares.
De maneira mais geral, se M for divisível por k então o número v % M será divisível por k sempre que v for divisível por k. Em vista dessa observação, é recomendável que
M seja um número primo.
Sedgewick sugere escolher M da seguinte maneira. Comece por escolher uma potência de 2 que esteja próxima do tamanho desejado da tabela. Depois, adote para M o número primo que esteja logo abaixo da potência escolhida.
| k | 2k | M |
| 7 | 128 | 127 |
| 8 | 256 | 251 |
| 9 | 512 | 509 |
| 10 | 1024 | 1021 |
| 11 | 2048 | 2039 |
| 12 | 4096 | 4093 |
| 13 | 8192 | 8191 |
| 14 | 16384 | 16381 |
| 15 | 32768 | 32749 |
| 16 | 65536 | 65521 |
| 17 | 131072 | 131071 |
| 18 | 262144 | 262139 |
Uma solução popular para resolver colisões
é conhecida como separate chaining:
para cada índice h da tabela há uma lista encadeada
que armazena todos os Items cuja chave
é levada em h
pela função de espalhamento.
Essa solução é muito boa se cada uma das listas de colisão
resultar curta.
Se o número total de Items
for N,
o comprimento de cada lista deveria, idealmente, estar
próximo de
N/M .
De acordo com Sedgewick, uma boa regra prática é escolher M de modo que o valor de N/M fique entre 5 e 10.
Exemplo: Suponha que nossa tabela deve estar preparada para armazenar até 50000 Items e que as chaves são números inteiros positivos. Parece razoável, então, adotar um número primo entre 5000 e 10000 como valor de M. Podemos adotar 8191, por exemplo. A implementação a seguir (compare com o programa 14.3 de Sedgewick), usa uma função de espalhamento modular e resolve as colisões por separate chaining:
// Tamanho da tabela. #define M 8191 // Função de espalhamento: transforma uma // chave v em um índice no intervalo 0..M-1. #define hash(v, M) (v % M) // Cada Item consiste em uma cadeia de // caracteres e uma chave. typedef struct { int chave; char* informacao; } Item; // Nós das listas de colisão. typedef struct STnode* link; struct STnode { Item item; link next; } ; // Tabela que aponta para as M listas de // colisão. link* tab;
// Inicializa uma tabela de símbolos que, // espera-se, armazenará cerca de 50000 // Items. A espinha dorsal da tabela será // um vetor tab[0..M-1]. // void STinit () { tab = malloc(M * sizeof (link)); for (int h = 0; h < M; h++) tab[h] = NULL; } // Insere item na tabela de símbolos. // void STinsert (Item item) { int v = item.chave; int h = hash(v, M); link novo = malloc(sizeof (struct STnode)); novo->item = item; novo->next = tab[h]; tab[h] = novo; } // Para sinalizar o fracasso de uma busca, // usamos um Item especial cuja chave é 0. // (Todas as chaves "válidas" são positivas.) // Item itemnulo; itemnulo.chave = 0; // Devolve um Item cuja chave é v. Se tal // Item não existe, devolve itemnulo. // Item STsearch (int v) { link t; int h = hash(v, M); for (t = tab[h]; t != NULL; t = t->next) if (t->item.chave == v) break; if (t != NULL) return t->item; return itemnulo; }
(O prefixo ST
é derivado da expressão symbol table.)
STdelete(int v);
Um outro método de resolução de colisões é conhecido como linear probing. Todos os Items são armazenados em um vetor tab[0..M-1] . Quando ocorre uma colisão, procuramos a próxima posição vaga no vetor. O seguinte exemplo (versão modificada do programa 14.4 de Sedgewick) ilustra o conceito:
// Estrutura de cada Item. typedef struct { int chave; char* informacao; } Item; // Tamanho da tabela (a ser definido durante // a inicialização). int M; // Transforma uma chave v em um índice no // intervalo 0..M-1. #define hash(v, M) (v % M) // Item especial que tem chave // nula. (Todas as chaves "válidas" são // positivas.) Item itemnulo; itemnulo.chave = 0; // A tabela tab[0..M-1] conterá todos os // Items. Item* tab;
// Inicializa uma tabela de símbolos que // deverá armazenar no máximo max Items. // A tabela residirá no vetor tab[0..M-1]. // void STinit (int max) { M = 2 * max; tab = malloc(M * sizeof (Item)); for (int h = 0; h < M; h++) tab[h] = itemnulo; } // A função insere item na tabela de símbolos. // Ela supõe que o número N de Items na // tabela de símbolos não é maior que M // (ou seja, que N <= M). // void STinsert (Item item) { int v = item.chave; int h = hash(v, M); while (tab[h].chave != itemnulo.chave) h = (h + 1) % M; tab[h] = item; } // Devolve um Item cuja chave é v. Se tal // Item não existe, a função devolve // itemnulo. A função supõe que o número de // Items na tabela de símbolos não é maior // que M. // Item STsearch (int v) { int h = hash(v, M); while (tab[h].chave != itemnulo.chave) if (tab[h].chave == v) return tab[h]; else h = (h + 1) % M; return itemnulo; }
Digamos que a tabela tem M posições e contém N Items num dado instante. O número
N/M
é o fator de carga (= load factor) da tabela naquele instante. É claro que esse número é menor ou igual a 1. Quanto maior o fator de carga, mais tempo as funções de busca e inserção vão consumir.
Até aqui, as chaves de todos os exemplos eram inteiros positivos. O que fazer se a chave é uma string, ou seja, uma cadeia de caracteres? Como calcular uma função de espalhamento nesse caso?
Suporemos que todos os caracteres pertencem ao conjunto ASCII. Podemos até trabalhar com um conjunto maior: o de todos os caracteres da tabela ISO-LATIN-1. Portanto, cada caracter é um número inteiro entre 0 e 255 e ocupa apenas 1 byte.
Uma cadeia não vazia é a representação de um número inteiro não negativo em base 256. Por exemplo, se s é uma cadeia de comprimento 2 então o número correspondente é
s[0] * 256 + s[1].
Se s é a cadeia "AB" então o número é 65 * 256 + 66, ou seja, 16706.
Para calcular o hash code de uma chave de maneira eficiente, basta usar o método de Horner:
typedef char* string;
int hash (string v, int M) {
int h = v[0];
for (int i = 1; v[i] != '\0'; i++)
h = h * 256 + v[i];
return h % M;
}
A base da representação não precisa ser 256 (que é o número de possíveis valores de um byte). Para que o espalhamento seja melhor, recomenda-se (veja o programa 14.1 de Sedgewick) usar um número primo, digamos 251, como base:
int hash (string v, int M) {
int h = v[0];
for (int i = 1; v[i] != '\0'; i++)
h = h * 251 + v[i];
return h % M;
}
Um último detalhe: para evitar overflow aritmético, convém tomar o resto da divisão por M a cada passo:
int hash (string v, int M) {
int h = v[0];
for (int i = 1; v[i] != '\0'; i++)
h = (h * 251 + v[i]) % M;
return h;
}
(Estamos supondo que M não é muito grande. Caso contrário, h pode se aproximar de INT_MAX e o valor da expressão h*251 + v[i] pode ser negativo em virtude do overflow, o que seria desastroso.)
Digamos que meus objetos são as palavras de um livro. Para cada palavra, quero saber quantas vezes ela aparece no livro. Para esse problema, podemos definir os Items da tabela de símbolos assim:
typedef char* palavra;
typedef struct {
palavra chave;
int ocorrencias;
} Item;
Cada chave é uma palavra do livro e Items diferentes têm chaves diferentes. A função de inserção é um pouco diferente da usual: se a palavra a ser inserida já está na tabela de símbolos, não é necessário inseri-la novamente mas é preciso incrementar o seu contador de ocorrências.
Suponha que o livro tem cerca de 10000 palavras. Se usarmos um valor de M próximo de 1000 as listas de colisão terão comprimento 10 em média. Adotemos pois o número primo 1021 como valor de M. As funções de inserção e busca podem ser implementadas assim:
// Definição de um nó das listas de colisão. typedef struct STnode* link; struct STnode { Item item; link next; } ; // Tamanho da tabela. #define M 1021 // A tabela tab[0..M-1] apontará para as M // listas de colisão. link tab[M]; // Função de espalhamento: transforma uma // chave não vazia v em um número no // intervalo 0..M-1. int hash (palavra v, int M) { int h = v[0]; for (int i = 1; v[i] != '\0'; i++) h = (h * 251 + v[i]) % M; return h; }
// Inicializa uma tabela que apontará as M // listas de colisão. // void STinit () { for (int h = 0; h < M; h++) tab[h] = NULL; } // Se item já está na tabela de símbolos, // a função incrementa o campo ocorrencias // de item. Senão, item é inserido e seu // contador é inicializado com 1. // void STinsert (Item item) { palavra v = item.chave; int h = hash(v, M); link t; for (t = tab[h]; t != NULL; t = t->next) if (strcmp(t->item.chave, v) == 0) break; if (t != NULL) t->item.ocorrencias++; else { item.ocorrencias = 1; link novo = malloc(sizeof (struct STnode)); novo->item = item; novo->next = tab[h]; tab[h] = novo; } } // Para sinalizar o fracasso de uma busca, // usamos um Item especial cuja chave é uma // palavra vazia. // char palavravazia[1]; palavravazia[0] = '\0'; Item itemnulo; itemnulo.chave = palavravazia; // A função STsearch devolve um Item que tem // chave v. Se tal Item não existe, a função // devolve itemnulo. // Item STsearch (palavra v) { link t; int h = hash(v, M); for (t = tab[h]; t != NULL; t = t->next) if (strcmp(t->item.chave, v) == 0) break; if (t != NULL) return t->item; return itemnulo; }