Tabla de direcciones directas

Direct Address Table es una estructura de datos que tiene la capacidad de asignar registros a sus claves correspondientes mediante arrays. En las tablas de direcciones directas, los registros se colocan usando sus valores clave directamente como índices. Facilitan operaciones rápidas de búsqueda, inserción y borrado.

Podemos entender el concepto usando el siguiente ejemplo. Creamos una array de tamaño igual al valor máximo más uno (suponiendo un índice basado en 0) y luego usamos los valores como índices. Por ejemplo, en el siguiente diagrama, la clave 21 se usa directamente como índice.

ventajas:

1. Búsqueda en tiempo O(1): las tablas de direcciones directas utilizan arrays que son estructuras de datos de acceso aleatorio, por lo que los valores clave (que también son el índice de la array) se pueden usar fácilmente para buscar registros en tiempo O(1).
2. Inserción en tiempo O(1): podemos insertar fácilmente un elemento en una array en tiempo O(1). Lo mismo sigue en una tabla de direcciones directas también.
3. Eliminación en el tiempo O(1): La eliminación de un elemento toma el tiempo O(1) en una array. De manera similar, para eliminar un elemento en una tabla de direcciones directas, necesitamos el tiempo O(1).

Limitaciones:

1. Conocimiento previo del valor máximo de la clave
2. Prácticamente útil solo si el valor máximo es muy inferior.
3. Provoca desperdicio de espacio de memoria si hay una diferencia significativa entre los registros totales y el valor máximo.

Hashing puede superar estas limitaciones de las tablas de direcciones directas.

¿Cómo manejar las colisiones?
Las colisiones se pueden manejar como Hashing. Podemos usar Enstringmiento o direccionamiento abierto para manejar las colisiones. La única diferencia con el hash aquí es que no usamos una función hash para encontrar el índice. Preferimos usar valores directamente como índices.