Estructuras de datos

Array / Matriz

Una array o matriz es una colección de elementos que se almacenan consecutivamente en la memoria.

Carácteristicas:

• Todos los elementos deben tener el mismo tipo de dato
• La matriz tiene un tamaño fijo desde el inicio.

Matrices en go:

var numbers [3]int = [3]int{10, 59, 11}
var cars [3]string = [3]string{"BMW", "Volvo", "Ford"}
var char [3]rune = [3]rune{'A', 'G', 'U'}

Con el caso de cars, si usamos var cuartoAuto = cars[3] obtendríamos un error de índice fuera de rango.

¿Por qué no podemos tener un tamaño dinámico?

El espacio al ser contiguo no nos asegura que cuando reservemos los 3 espacios en memoria, cuando querramos el 4to espacio, esté disponible. Por otro lado, si reservamos 1000 elementos esperando que cumpla nuestras espectativas, esto usemoslos o no, hace que esos espacios se bloqueen para el resto de los sistemas, probocando un memory leak.

¿Por qué no podemos tener un tamaño dinámico?

Esto se debe a la diferencia en los tamaños de los diferentes tipos. Por ejemplo:

• int ocupa 2 bytes
• bool ocupa 1 byte
• string ocupa 16 bytes

Si cada representación en la memoria ocupa 1 byte, para la siguiente matriz:

var numbers [3]int = [3]int{4, 9, 6}

En la memoria se vería así:

Como se puede ver, cada elemento ocupa 2 espacios, esto también lo sabe nuestro sistema, si un array es de números, entonces cada índice ocupa 2 espacios, esto hace que si le pasamos el índice 0, lea los primeros 2 bytes, si le pasamos el índice 1, salte los primeros 2 bytes y lea el 3er y 4to byte. Con tipos mixtos, es imposible calcular la posición exacta de cada elemento debido a su diferencia de tamaños en bytes, lo que hace que el acceso no sea tan directo y requiera cálculos adicionales para encontrar el elemento correcto.

Manipulación

Obtener por índice

Los elementos de un array se obtienen por índice y los índices empiezan por 0 hasta el tamaño de la matriz menos 1.

var cars [3]string = [3]string{"BMW", "Volvo", "Ford"}

var bmw = cars[0]
var volvo = cars[1]
var ford = cars[2]

El acceso tiene complejidad constante O(1).

Modificación

Se puede modificar el valor de un elemento directamente usando su índice.

var cars [3]string = [3]string{"BMW", "Volvo", "Ford"}

cars[0] = "Toyota"

La modificación tiene complejidad constante O(1).

Recorrido

Para recorrer todos los elementos de un array, debemos hacerlo a través de un bucle for con el rango de índices.

for i := 0; i < len(cars); i++ {
    fmt.Println(cars[i])
}

El recorrido de un array tiene complejidad lineal O(n).

Hash map

Un hash map es una estructura de datos que almacena pares clave-valor, usando una función hash para calcular el índice donde se almacenará cada par.

Características:

• Acceso rápido promedio O(1)
• Colisiones manejadas comúnmente con encadenamiento o sondeo abierto

Operaciones básicas:

• Inserción: O(1) promedio
• Búsqueda: O(1) promedio
• Eliminación: O(1) promedio

Ventajas:

• Acceso rápido a datos por clave
• Eficiente para búsquedas frecuentes

Desventajas:

• Puede degradarse a O(n) en el peor caso
• Uso de memoria puede ser ineficiente