Estrutura de Dados e Algoritmos – Tabela de Hash

A Tabela de Hash é uma estrutura de dados que armazena dados de forma associativa. Em uma tabela hash, os dados são armazenados em um formato de array, onde cada valor de dado tem seu próprio valor de índice único. O acesso aos dados torna-se muito rápido se conhecermos o índice dos dados desejados.

Assim, torna-se uma estrutura de dados em que as operações de inserção e pesquisa são muito rápidas, independentemente do tamanho dos dados. Hash Table usa um array como um meio de armazenamento e usa a técnica hash para gerar um índice onde um elemento deve ser inserido ou deve ser localizado de.

Hashing

Hashing é uma técnica para converter um intervalo de valores chave em um intervalo de índices de um array. Vamos usar o operador modulo para obter um intervalo de valores chave. Considere um exemplo de tabela de hash de tamanho 20, e os seguintes itens devem ser armazenados. Os itens estão no formato (chave, valor).

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

Sondagem linear

Como podemos ver, pode acontecer que a técnica de hashing seja usada para criar um índice já usado do array. Nesse caso, podemos pesquisar o próximo local vazio no array procurando na próxima célula até encontrarmos uma célula vazia. Esta técnica é chamada de sondagem linear.

Operações Básicas

Seguir são as operações primárias básicas de uma tabela de hash.

• Procura – Procura um elemento numa tabela hash.

• Inserir – insere um elemento numa tabela hash.

• apagar – Apaga um elemento de uma tabela hash.

DataItem

Definir um item de dados com alguns dados e chave, baseado no qual a pesquisa deve ser conduzida em uma tabela hash.

struct DataItem { int data; int key;};

Hash Method

Definir um método de hash para calcular o código hash da chave do item de dados.

int hashCode(int key){ return key % SIZE;}

Operação de busca

Quando um elemento for pesquisado, calcule o código hash da chave passada e localize o elemento usando esse código hash como índice no array. Use a sondagem linear para obter o elemento à frente se o elemento não for encontrado no código hash computado.

Exemplo

struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray != NULL) { if(hashArray->key == key) return hashArray; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Inserir Operação

Quando um elemento deve ser inserido, calcule o código hash da chave passada e localize o índice usando esse código hash como um índice no array. Use a sondagem linear para localização vazia, se um elemento for encontrado no código hash computado.

Exemplo

void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray != NULL && hashArray->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray = item; }

Excluir Operação

Quando um elemento tiver que ser excluído, calcule o código hash da chave passada e localize o índice usando esse código hash como um índice no array. Use a sondagem linear para obter o elemento à frente se um elemento não for encontrado no código hash computado. Quando encontrado, armazene um item dummy lá para manter a performance da tabela de hash intacta.

Exemplo

struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray !=NULL) { if(hashArray->key == key) { struct DataItem* temp = hashArray; //assign a dummy item at deleted position hashArray = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Para saber sobre implementação de hash em linguagem de programação C, por favor clique aqui.