Tomemos un ejemplo práctico. Digamos que tiene un libro de contactos, nombres, números de teléfono, direcciones. Las acabas de escribir cuando conociste a esas personas, no ordenadas alfabéticamente.
Ahora desea almacenarlos en una computadora para poder escribir más rápidamente el nombre del tipo y su información aparecerá:
Primero crea una estructura de registro para agrupar toda esa información en un elemento que puede usar más fácilmente. El registro tiene tipos de campos como cadena para nombre, tel y addr.
- ¿Qué es binario y por qué lo usan las computadoras?
- ¿Qué algoritmos de clasificación tienen la mejor complejidad de tiempo de caso?
- ¿Cuáles son algunos ejemplos de problemas para los cuales una cola prioritaria resulta útil?
- ¿Qué es el algoritmo SURF en el procesamiento de imágenes?
- ¿Cuál es el algoritmo de clasificación menos eficiente?
Así que ahora elige la estructura de datos que desea recopilar todos estos registros de contacto:
Formación
Cada registro se coloca uno al lado del otro en la RAM. Entonces sabe que su registro tiene una longitud de X bytes, por lo tanto, el 3er registro comienza en la posición “inicio de matriz + 2 longitudes de registro”.
Lista enlazada
Cada registro se asigna a donde el administrador de memoria considere más aplicable en este momento. Obtiene la ubicación donde se asignó y la guarda en el campo “siguiente” del registro anterior. Solo tiene un valor en su estructura de datos … la cabeza con la ubicación del primer elemento.
Tabla de picadillo
Haces una matriz que es más larga de lo que necesitas. Se calcula un valor numérico a partir del nombre utilizando una fórmula hash. Que luego usa para definir una posición dentro de esa matriz. En el que almacena ese nombre en particular y su información. Haz lo mismo para el resto. Si encuentra que la posición ya está ocupada, vuelva a crear un nuevo hash hasta obtener un lugar vacío.
…
…
Ahora, ingrese el nombre Jhon. ¿Qué pasa en cada uno?
Formación
Establezca una variable de índice en 0. Haga un bucle hasta que se encuentre o el índice pase el final de la matriz. Dentro del bucle, verifique esa posición en la matriz contra Jhon. ¿El nombre del registro actual es el mismo? Si es así, detente, lo has encontrado. De lo contrario, incremente el índice y regrese al inicio del ciclo.
Lista enlazada
Obtenga el primer registro señalado por la variable head. Haga un bucle hasta que no sea nulo, o si su campo de nombre es igual a Jhon. De lo contrario, dentro del bucle, establezca el registro actual a lo que apunte el siguiente campo del registro actual.
Tabla de picadillo
Calcule el valor hash de Jhon. Úselo como índice en la matriz. Si esa posición contiene un registro con el nombre Jhon, lo has encontrado. Si no, vuelva a llamar el hash e intente nuevamente.
…
…
¿Qué significa esto practicamente? Tanto en la matriz como en la lista vinculada, tendría que recorrer (en promedio) la mitad de los elementos para encontrar cualquiera con un nombre Jhon, es decir, la cantidad de búsquedas realizadas está relacionada linealmente con el número de elementos almacenados O (N ) En la tabla hash, lo más probable es que solo necesite calcular el hash una vez, y tenga Jhon, es decir, O (1). Incluso si no es el primer cálculo, es probable que solo sea un puñado en una lista de 1000, depende de la calidad de la fórmula hash.
Estrictamente hablando, realmente no se puede comparar una matriz (o LL para el caso) con una tabla hash. Los dos primeros son colecciones genéricas. La última es una colección de búsqueda, destinada a la búsqueda. Sin mencionar que una tabla hash se implementa (generalmente) encima de una matriz, la matriz forma parte de ella.
Una mejor comparación podría ser una matriz ordenada o un árbol de búsqueda binario. Los dos están relacionados con la matriz y la lista vinculada, respectivamente. Sin embargo, en ambos casos son más lentos que una tabla hash: solo reducirían las posibilidades de búsqueda a la mitad para cada elemento verificado, mientras que un hash llega allí en un movimiento casi siempre. Lo mismo ocurre al insertar, en la matriz ordenada, necesitaría mover todos los elementos después de la posición donde desea insertar uno por uno, es decir, después de encontrar la posición, una O (N) después de una O (log N ) En el BST, ubicaría la última hoja después de intentar encontrar el elemento con el mismo nombre que desea insertar. Luego configure el nuevo elemento como su puntero izquierdo o derecho. De nuevo … una operación O (log N). En la tabla hash, es solo una operación O (1).
