Estrutura de dados e algoritmos - Tabela de hash

Hash Table é uma estrutura de dados que armazena dados de forma associativa. Em uma tabela hash, os dados são armazenados em um formato de matriz, em que cada valor de dados tem seu próprio valor de índice exclusivo. 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 busca são muito rápidas, independentemente do tamanho dos dados. A tabela de hash usa uma matriz como meio de armazenamento e usa a técnica de hash para gerar um índice onde um elemento deve ser inserido ou localizado.

Hashing

Hashing é uma técnica para converter um intervalo de valores-chave em um intervalo de índices de uma matriz. Vamos usar o operador de módulo para obter uma gama de valores-chave. Considere um exemplo de tabela 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)

Sr. Não.	Chave	Cerquilha	Índice Array
1	1	1% 20 = 1	1
2	2	2% 20 = 2	2
3	42	42% 20 = 2	2
4	4	4% 20 = 4	4
5	12	12% 20 = 12	12
6	14	14% 20 = 14	14
7	17	17% 20 = 17	17
8	13	13% 20 = 13	13
9	37	37% 20 = 17	17

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 na matriz olhando para a próxima célula até encontrar uma célula vazia. Essa técnica é chamada de sondagem linear.

Sr. Não.	Chave	Cerquilha	Índice Array	Após a análise linear, índice de matriz
1	1	1% 20 = 1	1	1
2	2	2% 20 = 2	2	2
3	42	42% 20 = 2	2	3
4	4	4% 20 = 4	4	4
5	12	12% 20 = 12	12	12
6	14	14% 20 = 14	14	14
7	17	17% 20 = 17	17	17
8	13	13% 20 = 13	13	13
9	37	37% 20 = 17	17	18

Operações básicas

A seguir estão as operações primárias básicas de uma tabela hash.

Search - Pesquisa um elemento em uma tabela hash.
Insert - insere um elemento em uma tabela hash.
delete - Exclui um elemento de uma tabela hash.

Item de dados

Defina um item de dados com alguns dados e chave, com base nos quais a pesquisa deve ser conduzida em uma tabela hash.

struct DataItem {
   int data;
   int key;
};

Método Hash

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

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

Operação de Pesquisa

Sempre que um elemento deve ser pesquisado, calcule o código hash da chave passada e localize o elemento usando esse código hash como índice na matriz. Use a análise linear para obter o elemento à frente se o elemento não for encontrado no código hash calculado.

Exemplo

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

   return NULL;        
}

Operação de inserção

Sempre que 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 na matriz. Use sondagem linear para localização vazia, se um elemento for encontrado no código hash calculado.

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[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

Excluir operação

Sempre que um elemento deve ser excluído, calcule o código hash da chave passada e localize o índice usando esse código hash como um índice na matriz. Use a análise linear para obter o elemento à frente se um elemento não for encontrado no código hash calculado. Quando encontrado, armazene um item fictício lá para manter o desempenho da tabela de hash intacto.

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[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

Para saber sobre a implementação de hash na linguagem de programação C, clique aqui .

↰ Previous page Next page ↱