Estructura de datos y algoritmos: tabla hash

Hash Table es una estructura de datos que almacena datos de forma asociativa. En una tabla hash, los datos se almacenan en un formato de matriz, donde cada valor de datos tiene su propio valor de índice único. El acceso a los datos se vuelve muy rápido si conocemos el índice de los datos deseados.

Así, se convierte en una estructura de datos en la que las operaciones de inserción y búsqueda son muy rápidas independientemente del tamaño de los datos. Hash Table utiliza una matriz como medio de almacenamiento y utiliza la técnica hash para generar un índice donde se debe insertar o ubicar un elemento.

Hashing

El hash es una técnica para convertir un rango de valores clave en un rango de índices de una matriz. Usaremos el operador de módulo para obtener un rango de valores clave. Considere un ejemplo de tabla hash de tamaño 20, y se almacenarán los siguientes elementos. Los elementos están en formato (clave, valor).

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

No Señor.	Llave	Picadillo	Índice de matriz
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

Palpado lineal

Como podemos ver, puede suceder que se utilice la técnica de hash para crear un índice ya utilizado de la matriz. En tal caso, podemos buscar la siguiente ubicación vacía en la matriz mirando en la siguiente celda hasta que encontremos una celda vacía. Esta técnica se llama sondeo lineal.

No Señor.	Llave	Picadillo	Índice de matriz	Después del palpado lineal, í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

Operaciones básicas

A continuación se muestran las operaciones primarias básicas de una tabla hash.

Search - Busca un elemento en una tabla hash.
Insert : Inserta un elemento en una tabla hash.
delete - Elimina un elemento de una tabla hash.

DataItem

Defina un elemento de datos que tenga algunos datos y una clave, en función del cual se realizará la búsqueda en una tabla hash.

struct DataItem {
   int data;
   int key;
};

Método hash

Defina un método hash para calcular el código hash de la clave del elemento de datos.

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

Operación de búsqueda

Siempre que se busque un elemento, calcule el código hash de la clave pasada y ubique el elemento utilizando ese código hash como índice en la matriz. Utilice el sondeo lineal para adelantar el elemento si el elemento no se encuentra en el código hash calculado.

Ejemplo

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;        
}

Insertar operación

Siempre que se inserte un elemento, calcule el código hash de la clave pasada y ubique el índice usando ese código hash como índice en la matriz. Utilice el sondeo lineal para la ubicación vacía, si se encuentra un elemento en el código hash calculado.

Ejemplo

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;        
}

Eliminar operación

Siempre que se deba eliminar un elemento, calcule el código hash de la clave pasada y ubique el índice usando ese código hash como índice en la matriz. Utilice el sondeo lineal para adelantar el elemento si no se encuentra un elemento en el código hash calculado. Cuando lo encuentre, almacene un elemento ficticio allí para mantener intacto el rendimiento de la tabla hash.

Ejemplo

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 conocer la implementación de hash en el lenguaje de programación C, haga clic aquí .

↰ Previous page Next page ↱