hash es una estructura de datos fundamental que almacena y recupera datos de manera eficiente de una manera que permite un acceso rápido. Implica asignar datos a un índice específico en una tabla hash utilizando un función hash que permite una rápida recuperación de información basada en su clave. Este método se usa comúnmente en bases de datos, C sistemas de dolor y diversas aplicaciones de programación para optimizar las operaciones de búsqueda y recuperación.

Estructuras de datos: hash

Tabla de contenidos

• Función hash
• ¿Qué es una colisión de hash?
• Técnicas de resolución de colisiones
• Aplicaciones de hash
• Problema fácil con hash
• Problema medio en hash
• Problema difícil con el hash

Cómo funciona:

1. Función hash: Usted proporciona sus elementos de datos en la función hash.
2. Código hash: La función hash procesa los datos y proporciona un código hash único.
3. Tabla de picadillo: Luego, el código hash le dirige a una ubicación específica dentro de la tabla hash.

Función hash

El función hash es una función que toma un llave y devuelve un índice en el tabla de picadillo . El objetivo de una función hash es distribuir claves de manera uniforme en la tabla hash, minimizando las colisiones (cuando dos claves se asignan al mismo índice).

Las funciones hash comunes incluyen:

• Método de división: Tamaño de la tabla hash % clave
• Método de multiplicación: (Clave * Constante) % Tamaño de la tabla hash
• Hashing universal: Una familia de funciones hash diseñadas para minimizar colisiones.

¿Qué es una colisión de hash?

Una colisión hash ocurre cuando dos claves diferentes se asignan al mismo índice en una tabla hash. Esto puede suceder incluso con una buena función hash, especialmente si la tabla hash está llena o las claves son similares.

Causas de las colisiones de hash:

• Función hash deficiente: Una función hash que no distribuye las claves de manera uniforme en la tabla hash puede provocar más colisiones.
• Alto factor de carga: Un factor de carga alto (relación entre claves y tamaño de la tabla hash) aumenta la probabilidad de colisiones.
• Claves similares: Las claves que son similares en valor o estructura tienen más probabilidades de colisionar.

Técnicas de resolución de colisiones

Hay dos tipos de técnicas de resolución de colisiones:

1. Direccionamiento abierto:
   • Sondeo lineal: Busque una ranura vacía secuencialmente
   • Sondeo cuadrático: Busque una ranura vacía usando una función cuadrática
2. Direccionamiento cerrado:
   • Encadenamiento: Almacene claves en colisión en una lista vinculada o árbol de búsqueda binaria en cada índice
   • Hashing de cuco: Utilice múltiples funciones hash para distribuir claves

Aplicaciones de hash

Las tablas hash se utilizan en una amplia variedad de aplicaciones, que incluyen:

• Bases de datos: Almacenamiento y recuperación de datos basados ​​en claves únicas
• Almacenamiento en caché: Almacenamiento de datos a los que se accede con frecuencia para una recuperación más rápida
• Tablas de símbolos: Mapeo de identificadores a sus valores en lenguajes de programación
• Enrutamiento de red: Determinar la mejor ruta para los paquetes de datos

¿Qué es el hash?

Mapeo de índices (o hash trivial)

Encadenamiento separado para manejo de colisiones

Direccionamiento abierto para manejo de colisiones

Doble hash

Factor de carga y refrito

Problema fácil con hash

• Encuentre si una matriz es un subconjunto de otra matriz
• Unión e intersección de dos listas enlazadas.
• Dada una matriz A[] y un número x, verifique el par en A[] con suma como x
• Distancia máxima entre dos apariciones del mismo elemento en una matriz
• Cuente el máximo de puntos en la misma línea
• Elemento más frecuente en una matriz.
• Encuentra el único elemento repetitivo entre 1 y n-1
• ¿Cómo comprobar si dos conjuntos dados son disjuntos?
• Suma no superpuesta de dos conjuntos
• Compruebe si dos matrices son iguales o no
• Encuentra elementos faltantes de un rango
• Número mínimo de subconjuntos con elementos distintos.
• Elimine el número mínimo de elementos de modo que no exista ningún elemento común en ambas matrices
• Encuentre pares con una suma dada de modo que los elementos del par estén en filas diferentes
• Contar pares con suma dada
• Cuente cuádruples de cuatro matrices ordenadas cuya suma es igual a un valor dado x
• Ordenar elementos por frecuencia
• Encuentre todos los pares (a, b) en una matriz tal que a % b = k
• Agrupar palabras con el mismo conjunto de caracteres.
• k-ésimo elemento distinto (o no repetitivo) en una matriz.

Problema medio en hash

• Buscar itinerario de una lista determinada de boletos
• Encuentre el número de empleados debajo de cada empleado
• Subarreglo más largo con suma divisible por k
• Encuentra el subarreglo más grande con suma 0
• Subsecuencia consecutiva creciente más larga
• Cuente elementos distintos en cada ventana de tamaño k
• Encuentra un subarreglo con la suma dada | Conjunto 2 (maneja números negativos)
• Implementando nuestra propia tabla hash con encadenamiento separado en Java
• Implementación de su propia tabla hash con sondeo lineal de direccionamiento abierto en C++
• Inserciones mínimas para formar un palíndromo con permutaciones permitidas
• Máxima diferencia posible de dos subconjuntos de una matriz
• Ordenar usando la función hash trivial
• Subarreglo más pequeño con k números distintos

Problema difícil con el hash

• Clonar un árbol binario con punteros aleatorios
• Subarreglo más grande con igual número de ceros y unos
• Todos los tripletes únicos que suman un valor determinado.
• Consultas de subcadenas palíndromo
• Consultas de rango para frecuencias de elementos de matriz
• Elementos que se agregarán para que todos los elementos de un rango estén presentes en la matriz
• Cuckoo Hashing - ¡Búsqueda O (1) en el peor de los casos!
• Cuente los subarreglos que tienen un total de elementos distintos iguales a los del arreglo original
• Matriz máxima de dos matrices dadas manteniendo el mismo orden
• Encuentre la suma de toda la suma de subarreglos únicos para un arreglo dado.
• La secuencia de Recaman
• Longitud de la subsecuencia bitónica estricta más larga
• Buscar todos los subárboles duplicados
• Encuentre si hay un rectángulo en una matriz binaria con esquinas como 1

Enlaces rápidos :

• 'Problemas de práctica' sobre hash
• Las 20 preguntas principales de la entrevista basadas en la técnica Hashing
• 'Vídeos' sobre Hashing