performance - resolucion - tablas hash c++

¿Por qué utilizamos el sondeo lineal en las tablas Hash cuando hay un encadenamiento separado vinculado con listas?

Question

Recientemente aprendí sobre diferentes métodos para lidiar con las colisiones en tablas hash. Y vio que el encadenamiento separado con las listas vinculadas siempre es más eficiente en el tiempo, y para la eficiencia del espacio asignamos una memoria predefinida para el sondeo lineal que luego no podríamos usar, para el encadenamiento separado utilizamos la memoria de forma dinámica, por lo que es un encadenamiento separado con lista enlazada ¿No es más eficiente que el sondeo lineal? En caso afirmativo, ¿por qué utilizamos el sondeo lineal?

Answer 1

El sondeo lineal es en realidad más eficiente en memoria cuando la tabla hash está casi llena.

Históricamente, uno tenía muy poca memoria, por lo que importaba cada byte (y todavía hay algunos casos en los que la memoria es muy limitada).

¿Por qué usa menos memoria?

Considere cómo se ven las tablas: (variaciones de encadenamiento separadas según Wikipedia - también hay otras variaciones, pero generalmente usan más memoria)

Linear             Separate chaining #1    Separate chaining #2
probing            List head in table      Pointer in table
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
| NULL |           | NULL |Ptr|            |Ptr|
|------|           |------|---|            |---|
 .                  .                       .
 .                  .                       .
 .                  .                       .

( Ptr significa "puntero" - cualquier puntero que no apunte a algo puede considerarse NULL )

El encadenamiento separado # 1 claramente usa más memoria que el sondeo lineal (siempre), ya que cada elemento de la tabla es más grande por el tamaño del puntero.

El encadenamiento separado # 2 podría tener una ventaja cuando no hay mucho en la tabla, pero cuando se llene, tendrá aproximadamente 2 punteros adicionales flotando alrededor de cada elemento.

templatetypedef probablemente tenga razón acerca de que el sondeo lineal suele ser más rápido (rara vez se equivoca), pero por lo general se enseña que el encadenamiento separado es más rápido, y lo ves en las principales API (como las implementaciones de Java , por ejemplo), tal vez debido a esta creencia, para evitar los casos en los que el sondeo lineal es mucho más lento (con unos pocos valores bien seleccionados, puede obtener rápidamente el rendimiento de O(n) con el sondeo lineal mientras que el encadenamiento separado aún sería O(1) ), o quizás por alguna otra razón.

Answer 2

Me sorprende que haya visto el hashing encadenado para ser más rápido que el sondeo lineal. En la práctica, el sondeo lineal suele ser significativamente más rápido que el encadenamiento. Esto se debe principalmente a la localidad de referencia , ya que los accesos realizados en el sondeo lineal tienden a estar más cerca en la memoria que los accesos realizados en el hashing encadenado.

Hay otras victorias en el sondeo lineal. Por ejemplo, las inserciones en una tabla hash de sondeo lineal no requieren nuevas asignaciones (a menos que estés recargando la tabla), por lo que en aplicaciones como enrutadores de red donde la memoria es escasa, es bueno saber que una vez que se configura la tabla, Los elementos pueden colocarse en él sin riesgo de falla de malloc .

Una debilidad del sondeo lineal es que, con una mala elección de la función hash, el agrupamiento primario puede hacer que el rendimiento de la tabla se degrade significativamente. Si bien el hash encadenado puede sufrir funciones de hash incorrectas, es menos sensible a los elementos con códigos hash cercanos, que no afectan negativamente al tiempo de ejecución. Teóricamente, el sondeo lineal solo proporciona búsquedas esperadas de O (1) si las funciones hash son 5-independent o si hay suficiente entropía en las teclas . Hay muchas maneras de abordar esto, ya que, al utilizar la técnica de hash de Robin Hood o el hash de hopscotch , ambos tienen peores casos significativamente mejores que el sondeo lineal de vainilla.

La otra debilidad del sondeo lineal es que su rendimiento se degrada significativamente a medida que se aproxima el factor de carga 1. Puede abordar esto mediante un nuevo lavado periódico o utilizando la técnica de hash de Robin Hood descrita anteriormente.

¡Espero que esto ayude!