El direccionamiento abierto , o hash cerrado , es un método de resolución de colisiones en tablas hash . Con este método, una colisión hash se resuelve sondeando o buscando en ubicaciones alternativas en la matriz (la secuencia de sonda ) hasta que se encuentra el registro objetivo o se encuentra una ranura de matriz no utilizada, lo que indica que no existe dicha clave en el mesa. [1] Las secuencias de sondas bien conocidas incluyen:
Las principales ventajas y desventajas entre estos métodos son que el sondeo lineal tiene el mejor rendimiento de caché pero es más sensible a la agrupación, mientras que el hash doble tiene un rendimiento de caché deficiente pero prácticamente no muestra agrupación; El sondeo cuadrático se encuentra en el medio en ambas áreas. El doble hash también puede requerir más cálculo que otras formas de sondeo.
Algunos métodos de direccionamiento abiertos, como el hash Rayuela , el hashing Robin Hood , el hash por orden de llegada y el hash cuco mueven las claves existentes en la matriz para dejar espacio para la nueva clave. Esto proporciona tiempos máximos de búsqueda mejores que los métodos basados en sondeo. [2] [3] [4] [5] [6]
Una influencia crítica en el rendimiento de una tabla hash de direccionamiento abierta es el factor de carga ; es decir, la proporción de ranuras de la matriz que se utilizan. A medida que el factor de carga aumenta hacia el 100%, el número de sondas que pueden ser necesarias para encontrar o insertar una clave determinada aumenta drásticamente. Una vez que la tabla se llena, los algoritmos de sondeo pueden incluso no terminar. Incluso con buenas funciones hash, los factores de carga normalmente se limitan al 80%. Una función hash deficiente puede presentar un rendimiento deficiente incluso con factores de carga muy bajos al generar una agrupación significativa, especialmente con el método de direccionamiento lineal más simple. Generalmente, los factores de carga típicos con la mayoría de los métodos de direccionamiento abiertos son del 50 %, mientras que el encadenamiento separado normalmente puede utilizar hasta el 100 %.
El siguiente pseudocódigo es una implementación de una tabla hash de direccionamiento abierta con sondeo lineal y paso a paso de una sola ranura, un enfoque común que es efectivo si la función hash es buena. Cada una de las funciones de búsqueda , configuración y eliminación utiliza una función interna común find_slot para localizar la ranura de la matriz que contiene o debería contener una clave determinada.
par de registros {clave, valor, bandera ocupada (inicialmente no configurada)} par var slot[0], slot[1], ..., slot[num_slots - 1]función find_slot(clave) i := hash(clave) módulo num_slots // buscamos hasta que encontremos la clave o encontremos un espacio vacío. mientras (ranura[i] está ocupada) y (ranura[i].clave ≠ clave) i := (i + 1) módulo num_slots volver yo
búsqueda de función (clave) yo: = buscar_ranura (clave) si el slot[i] está ocupado // la clave está en la tabla return slot[i].value else // la clave no está en la tabla return not found
conjunto de funciones (clave, valor) yo: = buscar_ranura (clave) si la ranura [i] está ocupada // encontramos nuestra clave ranura[i].valor:= valor volver si la mesa está casi llena reconstruir la tabla más grande (nota 1) yo: = buscar_ranura (clave) marcar la ranura [i] como ocupada ranura[i].clave:= clave ranura[i].valor:= valor
función eliminar (tecla) yo: = buscar_ranura (clave) si la ranura [i] está desocupada, devuelve // la clave no está en la tabla marcar la ranura [i] como desocupada j := yo bucle (nota 2) j := (j + 1) módulo num_slots si la ranura [j] está desocupada, salga del bucle k := hash(ranura[j].clave) módulo num_slots // determina si k se encuentra cíclicamente en (i,j] // i ≤ j: | i..k..j | // i > j: |.k..j i....| o |.. ..j i..k.| si i ≤ j si (i < k) y (k ≤ j) continuar el bucle si no (k ≤ j) o (i < k) continuar el bucle marcar la ranura [i] como ocupada ranura[i].clave:= ranura[j].clave ranura[i].valor:= ranura[j].valor marcar la ranura [j] como desocupada yo := j
Otra técnica de eliminación es simplemente marcar la ranura como eliminada. Sin embargo, esto eventualmente requiere reconstruir la tabla simplemente para eliminar los registros eliminados. Los métodos anteriores proporcionan O (1) actualización y eliminación de registros existentes, con reconstrucción ocasional si la marca máxima del tamaño de la tabla crece.
El método de eliminación O (1) anterior solo es posible en tablas hash probadas linealmente con pasos de una sola ranura. En el caso de que se deban eliminar muchos registros en una sola operación, puede ser más eficiente marcar las ranuras para su eliminación y posterior reconstrucción.