Tabla de picadillo

En este tutorial, aprenderá qué es la tabla hash. Además, encontrará ejemplos prácticos de operaciones de tablas hash en C, C ++, Java y Python.

La tabla hash es una estructura de datos que representa datos en forma de pares clave-valor . Cada clave se asigna a un valor en la tabla hash. Las claves se utilizan para indexar los valores / datos. Se aplica un enfoque similar mediante una matriz asociativa.

Los datos se representan en un par clave-valor con la ayuda de claves, como se muestra en la siguiente figura. Cada dato está asociado con una clave. La clave es un número entero que apunta a los datos.

1. Tabla de direcciones directas

La tabla de direcciones directas se utiliza cuando la cantidad de espacio utilizado por la tabla no es un problema para el programa. Aquí, asumimos que

  • las claves son pequeños enteros
  • el número de llaves no es demasiado grande, y
  • no hay dos datos que tengan la misma clave

Se toma un conjunto de números enteros llamado universo U = (0, 1,… ., n-1).
Cada ranura de una tabla de direcciones directas T(0… n-1)contiene un puntero al elemento que corresponde a los datos.
El índice de la matriz Tes la clave en sí y el contenido de Tes un puntero al conjunto (key, element). Si no hay ningún elemento para una clave, se deja como NULL.

A veces, la clave en sí misma son los datos.

Pseudocódigo para operaciones

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Limitaciones de una tabla de direcciones directas

  • El valor de la clave debe ser pequeño.
  • La cantidad de claves debe ser lo suficientemente pequeña para que no cruce el límite de tamaño de una matriz.

2. Tabla hash

En una tabla hash, las claves se procesan para producir un nuevo índice que se asigna al elemento requerido. Este proceso se llama hash.

Sea h(x)una función hash y ksea ​​una clave.
h(k)se calcula y se utiliza como índice del elemento.

Limitaciones de una tabla hash

  • Si la función hash produce el mismo índice para varias claves, entonces surge un conflicto. Esta situación se llama colisión.
    Para evitar esto, se elige una función hash adecuada. Pero es imposible producir todas las claves únicas porque |U|>m. Por lo tanto, es posible que una buena función hash no evite las colisiones por completo, pero puede reducir el número de colisiones.

Sin embargo, tenemos otras técnicas para resolver colisiones.

Ventajas de la tabla hash sobre la tabla de direcciones directas:

Los principales problemas con la tabla de direcciones directas son el tamaño de la matriz y el valor posiblemente grande de una clave. La función hash reduce el rango de índice y, por lo tanto, también se reduce el tamaño de la matriz.
Por ejemplo, If k = 9845648451321, then h(k) = 11(usando alguna función hash). Esto ayuda a ahorrar la memoria desperdiciada mientras proporciona el índice de 9845648451321la matriz

Resolución de colisiones por encadenamiento

En esta técnica, si una función hash produce el mismo índice para varios elementos, estos elementos se almacenan en el mismo índice usando una lista doblemente enlazada.

Si jes el espacio para varios elementos, contiene un puntero al encabezado de la lista de elementos. Si no hay ningún elemento presente, jcontiene NIL.

Pseudocódigo para operaciones

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Implementación de Python, Java, C y C ++

Python Java C C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

Buenas funciones hash

Una buena función hash tiene las siguientes características.

  1. No debe generar claves que sean demasiado grandes y el espacio del depósito es pequeño. Se desperdicia espacio.
  2. Las claves generadas no deben estar ni muy cerca ni muy lejos en el rango.
  3. La colisión debe minimizarse tanto como sea posible.

Algunos de los métodos utilizados para el hash son:

Método de división

Si kes una clave y mtiene el tamaño de la tabla hash, la función hash h()se calcula como:

h(k) = k mod m

Por ejemplo, si el tamaño de una tabla hash es 10y k = 112luego h(k) = 112mod 10 = 2. El valor de mno debe ser el poder de 2. Esto se debe a que las potencias de 2en formato binario son 10, 100, 1000,… . Cuando encontremos k mod m, siempre obtendremos los p-bits de menor orden.

 if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where,

  • kA mod 1 gives the fractional part kA,
  • ⌊ ⌋ gives the floor value
  • A is any constant. The value of A lies between 0 and 1. But, an optimal choice will be ≈ (√5-1)/2 suggested by Knuth.

Universal Hashing

In Universal hashing, the hash function is chosen at random independent of keys.

Open Addressing

Multiple values can be stored in a single slot in a normal hash table.

By using open addressing, each slot is either filled with a single key or left NIL. All the elements are stored in the hash table itself.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1y son constantes auxiliares positivas,c2
  • i = (0, 1,… .)

Hash doble

Si se produce una colisión después de aplicar una función hash h(k), se calcula otra función hash para encontrar la siguiente ranura.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplicaciones de tabla hash

Las tablas hash se implementan donde

  • Se requiere búsqueda e inserción de tiempo constante
  • aplicaciones criptográficas
  • se requieren datos de indexación

Articulos interesantes...