No olvides que en la informática un problema casi siempre tiene diferentes resoluciones, así que te enseñaremos lo más óptimo y mejor.
Solución:
Me sorprende que haya visto que el hashing encadenado es 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 sondeo lineal tienden a estar más cerca en la memoria que los accesos realizados en hash encadenado.
Hay otras ventajas en el sondeo lineal. Por ejemplo, las inserciones en una tabla hash de sondeo lineal no requieren nuevas asignaciones (a menos que esté rehaciendo la tabla), por lo que en aplicaciones como enrutadores de red donde la memoria es escasa, es bueno saber que una vez que la tabla está configurada, los elementos se pueden colocar en él sin riesgo de una malloc fallar.
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 aún puede sufrir malas funciones hash, es menos sensible a los elementos con códigos hash cercanos, que no afectan negativamente el tiempo de ejecución. Teóricamente, el sondeo lineal solo da las búsquedas O(1) esperadas si las funciones hash son independientes de 5 o si hay suficiente entropía en el keys. Hay muchas maneras de abordar esto, ya que se utiliza la técnica de hash de Robin Hood o el hash de rayuela, que tienen peores casos significativamente mejores que el sondeo lineal estándar.
La otra debilidad del sondeo lineal es que su rendimiento se degrada significativamente a medida que el factor de carga se acerca a 1. Puede abordar esto rehaciendo periódicamente o usando la técnica de hash de Robin Hood descrita anteriormente.
¡Espero que esto ayude!
El sondeo lineal es en realidad más eficiente en memoria cuando la tabla hash está casi llena.
Históricamente, uno tenía muy, muy poca memoria, por lo que cada byte importaba (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”: se puede considerar cualquier puntero que no apunte a algo NULL)
El encadenamiento separado #1 claramente usa más memoria que el sondeo lineal (siempre), ya que cada elemento en la tabla es más grande por el tamaño del puntero.
El encadenamiento separado #2 puede tener una ventaja cuando no hay mucho en la tabla, pero cuando se llena, tendrá aproximadamente 2 punteros adicionales flotando para cada elemento.
templatetypedef probablemente tenga razón acerca de que el sondeo lineal suele ser más rápido (rara vez se equivoca), pero generalmente se enseña que el encadenamiento separado es más rápido, y lo ve en las principales API (como las implementaciones de Java, por ejemplo), tal vez debido a esta creencia, para evitar casos en los que el sondeo lineal es mucho más lento (con unos pocos valores bien seleccionados, puede llegar rápidamente a O(n) rendimiento con sondeo lineal mientras que el encadenamiento por separado aún habría sido O(1)), o tal vez por alguna otra razón.