hashing | Serie 1 (Introducción)

Supongamos que queremos diseñar un sistema para almacenar registros de empleados con números de teléfono (como claves ). Y queremos que las siguientes consultas se realicen de manera eficiente: 

1. Inserte un número de teléfono y la información correspondiente.
2. Busque un número de teléfono y obtenga la información.
3. Eliminar un número de teléfono y la información relacionada.

Podemos pensar en usar las siguientes estructuras de datos para mantener información sobre diferentes números de teléfono. 

1. Array de números de teléfono y registros.
2. Lista enlazada de números de teléfono y registros.
3. Árbol de búsqueda binario equilibrado con números de teléfono como claves.
4. Tabla de acceso directo.

Para arreglos y listas enlazadas , necesitamos buscar de forma lineal, lo que puede ser costoso en la práctica. Si usamos arrays y mantenemos los datos ordenados, entonces se puede buscar un número de teléfono en el tiempo O (Iniciar sesión) usando la búsqueda binaria, pero las operaciones de inserción y eliminación se vuelven costosas ya que tenemos que mantener el orden ordenado. 

Con el árbol de búsqueda binario equilibrado , obtenemos tiempos moderados de búsqueda, inserción y eliminación. Se puede garantizar que todas estas operaciones se realizarán en tiempo O (Inicio de sesión). 

Otra solución en la que se puede pensar es usar una tabla de acceso directo donde hacemos una gran array y usamos números de teléfono como índice en la array. Una entrada en la array es NIL si el número de teléfono no está presente; de ​​lo contrario, la entrada de la array almacena el puntero a los registros correspondientes al número de teléfono. En cuanto a la complejidad del tiempo, esta solución es la mejor entre todas, podemos hacer todas las operaciones en tiempo O (1). Por ejemplo, para insertar un número de teléfono, creamos un registro con los detalles del número de teléfono dado, usamos el número de teléfono como índice y almacenamos el puntero al registro creado en la tabla. 
Esta solución tiene muchas limitaciones prácticas. El primer problema con esta solución es que el espacio adicional requerido es enorme. Por ejemplo, si el número de teléfono tiene n dígitos, necesitamos O (m * 10 ⁿ) espacio para la tabla donde m es el tamaño de un puntero para registrar. Otro problema es que un número entero en un lenguaje de programación no puede almacenar n dígitos. 

Debido a las limitaciones anteriores, no siempre se puede utilizar la tabla de acceso directo. Hashing es la solución que se puede usar en casi todas estas situaciones y funciona extremadamente bien en comparación con las estructuras de datos anteriores como Array, Linked List, Balanced BST en la práctica. Con hashing obtenemos un tiempo de búsqueda O(1) en promedio (bajo supuestos razonables) y O(n) en el peor de los casos. Ahora entendamos qué es hash.

Hashing: Hashing es una técnica popular para almacenar y recuperar datos lo más rápido posible. La razón principal detrás del uso de hashing es que brinda resultados óptimos ya que realiza búsquedas óptimas.

¿Por qué usar Hashing? 

Si observa cuidadosamente, en un árbol de búsqueda binario equilibrado, si intentamos buscar, insertar o eliminar cualquier elemento, entonces la complejidad de tiempo para el mismo es O (logn). Ahora puede haber una situación en la que nuestras aplicaciones quieran hacer las mismas operaciones de una manera más rápida, es decir, de una manera más optimizada y aquí entra en juego el hashing. En hashing, todas las operaciones anteriores se pueden realizar en O(1), es decir, en tiempo constante. Es importante comprender que la complejidad de tiempo del peor de los casos para el hashing sigue siendo O(n), pero la complejidad de tiempo del caso promedio es O(1).
Ahora comprendamos algunas operaciones básicas de hashing.

Operaciones básicas:

• HashTable: esta operación se utiliza para crear una nueva tabla hash.
• Eliminar: esta operación se utiliza para eliminar un par clave-valor en particular de la tabla hash.
• Obtener: esta operación se utiliza para buscar una clave dentro de la tabla hash y devolver el valor asociado con esa clave.
• Put: esta operación se utiliza para insertar un nuevo par clave-valor dentro de la tabla hash.
• DeleteHashTable: esta operación se utiliza para eliminar la tabla hash

Componentes hash:

1) Tabla hash : una array que almacena punteros a registros correspondientes a un número de teléfono determinado. Una entrada en la tabla hash es NIL si ningún número de teléfono existente tiene un valor de función hash igual al índice de la entrada. En términos simples, podemos decir que la tabla hash es una generalización de array. La tabla hash brinda la funcionalidad en la que se almacena una colección de datos de tal manera que es fácil encontrar esos elementos más adelante si es necesario. Esto hace que la búsqueda de un elemento sea muy eficiente.

2) Función hash : una función que convierte un número de teléfono grande dado en un pequeño valor entero práctico. El valor entero asignado se utiliza como índice en la tabla hash. Entonces, en términos simples, podemos decir que una función hash se usa para transformar una clave dada en un índice de ranura específico. Su trabajo principal es mapear todas y cada una de las claves posibles en un índice de ranura único. Si cada clave se asigna a un índice de ranura único, la función hash se conoce como función hash perfecta. Es muy difícil crear una función hash perfecta, pero nuestro trabajo como programadores es crear dicha función hash con la ayuda de la cual el número de colisiones sea el menor posible. La colisión se discute más adelante.

Una buena función hash debe tener las siguientes propiedades:

1. Eficientemente computable. 
2.  Debe distribuir uniformemente las llaves (Cada posición de la mesa tiene la misma probabilidad para cada uno.
3. Debe minimizar las colisiones.
4. Debe tener un factor de carga bajo (número de elementos en la tabla dividido por el tamaño de la tabla).                                                  

Por ejemplo, para los números de teléfono, una función hash incorrecta es tomar los primeros tres dígitos. Una mejor función es considerar los últimos tres dígitos. Tenga en cuenta que esta puede no ser la mejor función hash. Puede haber mejores maneras. 

3) Manejo de colisiones : dado que una función hash nos da un número pequeño para una clave grande, existe la posibilidad de que dos claves den como resultado el mismo valor. La situación en la que una clave recién insertada se asigna a una ranura ya ocupada en la tabla hash se denomina colisión y debe manejarse utilizando alguna técnica de manejo de colisiones. Las siguientes son las formas de manejar las colisiones: 

• Enstringmiento: la idea es hacer que cada celda de la tabla hash apunte a una lista vinculada de registros que tienen el mismo valor de función hash. El enstringmiento es simple, pero requiere memoria adicional fuera de la tabla.
• Direccionamiento abierto: en el direccionamiento abierto, todos los elementos se almacenan en la propia tabla hash. Cada entrada de la tabla contiene un registro o NIL. Al buscar un elemento, examinamos las ranuras de la tabla una por una hasta que se encuentra el elemento deseado o está claro que el elemento no está en la tabla.

Publicaciones siguientes:  
Enstringmiento separado para manejo de colisiones 
Direccionamiento abierto para manejo de colisiones