Hash tables, diccionarios o la memoria del futuro

El ordenador, siguiendo el modelo actual, posee una memoria dividida en celdas que puede referenciarse palabra a palabra para obtener contenido de manera inmediata.  Los ingenieros decimos que el acceso a una celda de memoria tiene coste en O(1) o constante. No hay que buscar nada tan sólo pedir lo que haya en la celda número 42 y ¡presto! ahí está.

Este esquema de memoria es muy versátil porque representa listas de elementos. Casi cualquier estructura de datos puede representarse en una lista y, utilizando punteros, las listas no tienen por qué ser homogeneas. Podemos guardar en ellas de todo e identificar cada objeto guardado por el índice dentro de la lista. En otras palabras, por su posición.

Traducir una lista de objetos a un segmento de la memoria es tan simple como conocer el número de elementos, el tamaño de los mismos y la posición del primero.

Sobra decir que al concepto de lista está unido, muy fuertemente, el concepto de orden y posición.

Si hablamos de colecciones de elementos sin orden, como por ejemplo un conjunto, dónde no nos interesa en qué posición está un objeto, tan sólo si está o no está, encontramos que las listas dejan de resolver el problema elegantemente. Sin duda añadir un objeto a una lista es tan sencillo como añadir un nuevo elemento a una lista… ¿o no? Es un conjunto y en los conjuntos, formalmente descritos, no hay dos elementos iguales por lo que nos convendría no tener repeticiones. Así que antes de insertar un objeto habrá que buscarlo en la lista lo que en el mejor de los casos, tiene una complejidad de O(log n) y en el caso medio, de O(n). En palabras sencillas, buscar es una tarea sencilla pero cara en colecciones muy grandes.

Además, encontrar un objeto del conjunto, al no tener un orden predeterminado (nadie nos asegura que siempre metamos A primero, B segundo,  C tercero…), requiere una búsqueda también. Y eliminarlo, por definición requiere primero encontrarlo, así que tres cuartos de lo mismo.

Con esto en mente, un pedazo de ingeniero eléctrico, Dudley Allen Buck, describió un nuevo tipo de memoria llamada asociativa o direccionada por contenido. Esta memoria toma un objeto entero y lo busca en su interior pero esta búsqueda está hecha de tal forma que el acceso sigue siendo constante. ¿Magia? Nop, ¡ingenio!

Seguir leyendo «Hash tables, diccionarios o la memoria del futuro»