Está buscando una tabla hash para un valor que no está allí O (n)? (sondeo lineal)

Question

Solo intento comprender la lógica de sondeo lineal.

Con hashtable usando direccionamiento abierto, ¿cómo se puede confirmar que un elemento no está en la tabla.

Por ejemplo, supongamos que tiene un hashmap de 10 depósitos. Supongamos que hashe una tecla e insértala. Ahora, si los elementos A y B se van a insertar y hash y se reducen al mismo cubo, entonces los elementos A y B si usan una sonda lineal probablemente estarán uno al lado del otro.

Ahora, simplemente porque un cubo está vacío, no parece significar que un elemento no existe en el mapa. p.ej. Busca el elemento B después de que el elemento A se elimina por primera vez. Primero obtienes un cubo vacío donde esperas que sea B, pero necesitas sondear uno más y encontrarás B. Realmente está allí. Si esa lógica es correcta, ¿no tendrá que buscar en toda la tabla para confirmar si una clave no está allí? es decir, O (n) rendimiento cada vez.

Lo que estoy diciendo es, ¿no necesitas revisar todo el mapa para confirmar que no está allí?

Con un enfoque de encadenamiento separado para hashmap's ese problema no existe.

Editar: Lo que quiero decir es mirar esta imagen http://upload.wikimedia.org/wikipedia/commons/b/bf/Hash_table_5_0_1_1_1_1_0_SP.svg

Si se elimina John Smith, y tratamos de localizar a Sandra Dee.

O con el direccionamiento lineal se supone que debe mover los elementos para que no haya agujeros como tales. es decir, si se elimina a John Smith, ¿los elementos del 152 al 154 deberían desplazarse un lugar hacia atrás? Realmente no se ve eso en la descripción, pero eso podría tener algún sentido. Excepto si ted baker hashed a 154 y no 153 como se describe. Requiere un poco más de trabajo de lo que pensaba.

Podría ir simplemente con una simple lista vinculada en cada segmento.

Answer 1

En el peor de los casos, sí, el algoritmo para determinar si un elemento está o no en la tabla es O (n). Sin embargo, esto nunca sucederá en una tabla hash correctamente administrada.

Cuando se elimina un elemento, debe colocarse una lápida en la ranura de la mesa de la que se extrajo.La lápida es simplemente algunos datos para indicar que solía haber un elemento allí, pero se ha eliminado. De esta forma, cada vez que busca un elemento, debe seguir la secuencia de la sonda que esté utilizando hasta que encuentre una ranura que esté vacía. Si una ranura está vacía, ha completado la secuencia de sondeo para ese valor hash y sabe que no estará en ningún otro lugar de la tabla.

La única forma en que tendría que buscar en cada ranura de la secuencia de la sonda es si no hay ranuras vacías en la secuencia de la sonda. Como siempre debes apuntar a que una tabla hash esté medio vacía, esto no debería suceder.

Answer 2

El uso de una tabla hash que resuelve los conflictos con una estrategia de sondeo establece requisitos estrictos sobre las capacidades de eliminación de la estructura de datos. Cuando elimina un elemento, debe compensar el hashtable para que aún cumpla con los requisitos necesarios para la búsqueda (que es el punto principal de una tabla hash).

Al utilizar el sondeo lineal, si elimina un elemento, pasa a la siguiente ranura. Si coincide con el hash de la ranura que acabamos de eliminar, muévelo. Enjuague y repita hasta que llegue a un espacio vacío. También hay estrategias de eliminación diferida, donde los elementos se marcan para su eliminación y luego se eliminan/compensan en la siguiente búsqueda.

Supongamos que hay tres elementos {A0, A1, A2} que tienen el mismo valor de Hash. Deje {A0, A1} en la tabla Hashtable y {A2} no. Si eliminamos A0, lo marcamos para eliminarlo. Cuando hacemos una búsqueda de A2 (no en la Hashtable) encontramos A0 (eliminado), luego nos movemos a A1, que nos trasladamos a la ranura de A0, finalizando la eliminación. Pasamos a la siguiente ranura (que podría ser A2, o un candidato para la ranura que A1 estaba ocupando) pero la encontramos vacía, así que limpiamos la ranura que A1 acaba de desocupar y nuestra tabla hash vuelve a un estado prístino.

Answer 3

Creo que esto es tarde, pero hay una mención a la secuencia de la sonda y la secuencia de sonda máxima para una tabla hash.

Cada vez que inserta un elemento, realmente mantiene una pista que es la cantidad máxima de sondeos que ya hizo en el pasado, y es que 'maxProb' es más pequeño que el número de sondeos que realizó para insertar el elemento actual .

Finalmente, cuando está buscando un elemento en la tabla hash, solo realizará un máximo de búsquedas de maxProb.

Ahora, considerando que no permite infinitas sondas N, donde N es la capacidad de la tabla hash, el tiempo de ejecución sería O (x) donde x es la sonda máxima permitida en el peor de los casos.

Supongamos que su algoritmo de generación de clave hash es tal que le obliga a sondear muchas veces, luego puede implementar la estructura de datos de tal manera que si una inserción lleva x sondas, debería reconsiderarse .