Dirección abierta

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 de hash se resuelve mediante sondeo , o búsqueda a través de ubicaciones alternativas en el array (la secuencia de sondeo ) hasta que se encuentra el registro objetivo o se encuentra una ranura del array sin usar, lo que indica que no existe dicha clave en la tabla. ^{[ 1 ]} Las secuencias de sondeo más conocidas incluyen:

Sondeo lineal

en el que el intervalo entre sondas es fijo, a menudo establecido en 1.

Sondeo cuadrático

en el que el intervalo entre sondas aumenta linealmente (por lo tanto, los índices se describen mediante una función cuadrática ).

Doble hash

en el que el intervalo entre sondas es fijo para cada registro, pero se calcula mediante otra función hash .

Las principales diferencias entre estos métodos radican en que el sondeo lineal ofrece el mejor rendimiento de caché , pero es más sensible a la agrupación , mientras que el doble hash tiene un rendimiento de caché deficiente, pero prácticamente no presenta agrupación; el sondeo cuadrático se sitúa en un punto intermedio en ambos aspectos. El doble hash también puede requerir mayor capacidad de cálculo que otras formas de sondeo.

Algunos métodos de direccionamiento abierto, como el hash Hopscotch , el hash Robin Hood , el hash last-come-first-served y el hash cuckoo, mueven las claves existentes en el array para dejar espacio para la nueva clave. Esto proporciona mejores tiempos máximos de búsqueda que los métodos basados ​​en sondeo. ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]}

Un factor crítico que influye en el rendimiento de una tabla hash de direccionamiento abierto es el factor de carga ; es decir, la proporción de ranuras en la matriz que se utilizan. A medida que el factor de carga se acerca al 100%, la cantidad de sondeos necesarios para encontrar o insertar una clave determinada aumenta drásticamente. Una vez que la tabla se llena, los algoritmos de sondeo pueden incluso fallar. Incluso con buenas funciones hash, los factores de carga suelen estar limitados al 80%. Una función hash deficiente puede presentar un rendimiento bajo 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 abierto son del 50%, mientras que el encadenamiento separado puede llegar hasta el 100%.

El siguiente pseudocódigo implementa una tabla hash de direccionamiento abierto con sondeo lineal y paso a paso de una sola ranura, un enfoque común que resulta eficaz si la función hash es adecuada. Cada una de las funciones de búsqueda , establecimiento y eliminación utiliza una función interna común, find_lot, para localizar la ranura del array que contiene o debería contener una clave determinada.

par de registros { clave, valor, indicador de ocupación (inicialmente no establecido) } par de variables ranura[0], ranura[1], ..., ranura[num_ranuras - 1]

función find_slot(clave) i := hash(clave) módulo num_ranuras // Buscar hasta que encontremos la clave o una ranura vacía. Mientras (slot[i] esté ocupada) y (slot[i].key ≠ key) i := (i + 1) módulo num_slots regreso i

función buscar(clave) i := find_slot(clave) Si slot[i] está ocupado // la clave está en la tabla , devolver slot[i].value; de ​​lo contrario // la clave no está en la tabla, devolver no encontrado.

función establecer(clave, valor) i := find_slot(clave) Si slot[i] está ocupado // hemos encontrado nuestra clave slot[i].valor := valor Devolver si la tabla está casi llena. Reconstruir la tabla más grande (nota 1) i := find_slot(clave) marcar slot[i] como ocupado ranura[i].clave := clave slot[i].valor := valor

nota 1

Reconstruir la tabla requiere asignar un array más grande y usar recursivamente la operación de conjunto para insertar todos los elementos del array antiguo en el nuevo array. Es común aumentar el tamaño del array exponencialmente , por ejemplo, duplicando el tamaño del array anterior.

función remove(clave) i := find_slot(clave) Si slot[i] no está ocupado, devuelve // ​​la clave no está en la tabla marcar slot[i] como desocupado j := i bucle (nota 2) j := (j + 1) módulo num_slots Si slot[j] no está ocupado, salir del bucle. k := hash(slot[j].key) módulo num_slots // determinar 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 sino si (k ≤ j) o (i < k) continuar el bucle marcar slot[i] como ocupado ranura[i].clave := ranura[j].clave slot[i].valor := slot[j].valor marcar slot[j] como desocupado yo := j

nota 2

Para todos los registros de un clúster, no debe haber espacios vacíos entre su posición hash natural y su posición actual (de lo contrario, las búsquedas terminarán antes de encontrar el registro). En este punto del pseudocódigo, i es un espacio vacío que podría estar invalidando esta propiedad para los registros subsiguientes del clúster. j es uno de esos registros subsiguientes. k es el hash sin procesar donde el registro en j se ubicaría naturalmente en la tabla hash si no hubiera colisiones. Esta prueba determina si el registro en j está posicionado incorrectamente con respecto a las propiedades requeridas de un clúster ahora que i está vacío.

Otra técnica para eliminar registros consiste simplemente en marcar la ranura como borrada. Sin embargo, esto eventualmente requiere reconstruir la tabla para eliminar los registros borrados. Los métodos anteriores proporcionan una actualización y eliminación de registros existentes con complejidad O (1), con reconstrucciones ocasionales si el tamaño máximo de la tabla aumenta.

El método de eliminación O (1) descrito anteriormente solo es posible en tablas hash con sondeo lineal y paso a paso de una sola ranura. En el caso de que se deban eliminar muchos registros en una sola operación, marcar las ranuras para su eliminación y reconstruirlas posteriormente puede resultar más eficiente.

Suponiendo una función hash ideal (una que distribuye uniformemente todos los elementos del universo) y una selección aleatoria de elementos del universo, el rendimiento del método de sondeo lineal es:

${\displaystyle EU_{n}={\frac {1}{2}}\left(1+{\frac {1}{1-\alpha }}\right)+\Theta ({\frac {1}{m}})}$

${\displaystyle ES_{n}={\frac {1}{2}}\left(1+{\frac {1}{(1-\alpha )^{2}}}\right)+\Theta ({\frac {1}{m}})}$

Aquí n es el número de elementos en la tabla, m el tamaño de la tabla,${\displaystyle \alpha =n/m}$el factor de carga,${\displaystyle U_{n}}$el número de sondeos en una búsqueda infructuosa y${\displaystyle S_{n}}$el número de sondas en una búsqueda exitosa. ^{[ 7 ]} Nótese que la expectativa se deteriora hasta el infinito cuando el factor de carga se aproxima a 1.

• Eliminación diferida : un método para eliminar elementos de una tabla hash utilizando direccionamiento abierto.