TABLAS HASH

INTRODUCCIÓN

Todas las colecciones que hemos visto hasta ahora se han basado, fundamentalmente, en listas y árboles. De forma que el coste asintótico de las operaciones de inserción, borrado y test de pertenencia, es de O(n) y O(log n), respectivamente.

Estos costes para grandes colecciones (por ejemplo, conjuntos o diccionarios posiblemente infinitos) pueden resultar inaceptables, y cabe preguntarse si es posible reducirlos de forma significativa. Precisamente, éste es el objetivo de las estructuras de datos conocidas como tablas de dispersión (tablas hash), tanto abiertas como cerradas.

Intuitivamente, una tabla es una colección de elementos, cada uno de los cuales tiene una clave y una información asociada.

Esta aproximación consiste en proceder, no por comparaciones entre valores clave, sino encontrando alguna función h(k) que nos dé directamente la localización de la clave k en la tabla.

Para conseguir reducir el coste de las operaciones, los miembros potenciales de la colección se dividen en un número finitos de clases. Así, si se desea tener b clases, numeradas de 0 a b-1, los miembros de la colección se distribuyen en las mismas mediante lo que se conoce como la función de dispersión h.

Dado un elemento x de la colección, la función de dispersión se aplica a lo que habitualmente se denomina como la clave del elemento (y que en ocasiones será él mismo). Por otra parte, es relativamente frecuentemente, denominar por valor de dispersión al valor h(clave_de_x), nombrar como cubetas a las clases y decir que x pertenece a la cubeta h(clave_de_x).

La función de dispersión debe elegirse de forma que distribuya lo más uniformemente posible los n elementos de la colección entre las b clases. Así, todas las cubetas contendrán aproximadamente el mismo número de elementos (n/b).

La primera pregunta que podemos hacernos es si es fácil encontrar tales funciones h. La respuesta es, en principio, bastante pesimista, puesto que si tomamos como situación ideal el que tal función dé siempre localizaciones distintas a claves distintas y pensamos p.ej. en una tabla de tamaño 40 en donde queremos direccionar 30 claves, nos encontramos con que hay 40³⁰ = 1.15 * 10⁴⁸ posibles funciones del conjunto de claves en la tabla, y sólo 40*39*11 = 40!/10! = 2.25 * 10⁴¹ de ellas no generan localizaciones duplicadas. En otras palabras, sólo 2 de cada 10 millones de tales funciones serian 'perfectas' para nuestros propósitos. Esa tarea es factible sólo en el caso de que los valores que vayan a pertenecer a la tabla hash sean conocidas a priori. Existen algoritmos para construir funciones hash perfectas que son utilizadas para organizar las palabras clave en un compilador de forma que la búsqueda de cualquiera de esas palabras clave se realice en tiempo constante.

Las funciones que evitan valores duplicados son sorprendentemente difíciles de encontrar, incluso para tablas pequeñas. Por ejemplo, la famosa "paradoja del cumpleaños" asegura que si en una reunión están presentes 23 o más personas, hay bastante probabilidad de que dos de ellas hayan nacido el mismo día del mismo mes. En otras palabras, si seleccionamos una función aleatoria que aplique 23 claves a una tabla de tamaño 365 la probabilidad de que dos claves no caigan en la misma localización es de sólo 0.4927.

En consecuencia, las aplicaciones h(k), a las que desde ahora llamaremos funciones hash, tienen la particularidad de que podemos esperar que h( k_i ) = h( k_j ) para bastantes pares distintos ( k_i,k_j ). El objetivo será pues encontrar una función hash que provoque el menor número posible de colisiones (ocurrencias de sinónimos), aunque esto es solo un aspecto del problema, el otro será el de diseñar métodos de resolución de colisiones cuando éstas se produzcan.

En estas condiciones el coste de las operaciones sobre la colección será el siguiente:

O(h(clave_de_x)) + O(a cceso a la cubeta) + O(n/b)

Como veremos los valores de dispersión se obtienen realizando cálculos bastante simples sobre las claves de los elementos, con lo que el primero de los costes resulta ser de O(1). Por otro lado, el acceso a las cubetas será también de O(1) si las cubetas (o sus direcciones) se almacenan en un vector (tabla de cubetas).

En definitiva, si se puede estimar n y elegir b aproximadamente igual de grande, entonces cada cubeta tendrá en promedio sólo uno o dos miembros, y las operaciones sobre la colección serán de tiempo constante.

TABLAS DE DISPERSIÓN ABIERTAS

La manera más simple de resolver una colisión es construir, para cada localización de la tabla, una lista enlazada de registros cuyas claves caigan en esa dirección. La cantidad de tiempo requerido para una búsqueda dependerá de la longitud de las listas y de las posiciones relativas de las claves en ellas. Existen variantes dependiendo del mantenimiento que hagamos de las listas de sinónimos (FIFO, LIFO, por valor Clave, etc), aunque en la mayoría de los casos, y dado que las listas individuales no han de tener un tamaño excesivo, se suele optar por la alternativa más simple, la LIFO.

En cualquier caso, si las listas se mantienen en orden esto puede verse como una generalización del método de búsqueda secuencial en listas. La diferencia es que en lugar de mantener una sola lista con un solo nodo cabecera se mantienen M listas con M nodos cabecera de forma que se reduce el número de comparaciones de la búsqueda secuencial en un factor de M (en media) usando espacio extra para M punteros. Para nuestro ejemplo y con la alternativa LIFO, la tabla quedaría como se muestra en la siguiente figura:

CLASE ABSTRACTA

template <class B, class H, class T>

class hashTable {

friend class hashTableIterator<B, H, T>;

public:

// constructores

hashTable (const unsigned int & max,

unsigned int (*f) (const H &));

hashTable (const hashTable<B, H, T> & source);

virtual bool isEmpty () const;

/* Produce: cierto si la tabla receptora está vacía. */

virtual void deleteAllValues ();

/* Modifica: la tabla receptora haciéndola vacía. */

protected:

// área de datos

const unsigned int tablesize;

vector<B *> buckets;

unsigned int (*hashfun) (const H &);

// operaciones internas

unsigned int hash (const H & key) const;

/* Necesita: una clave.

Produce: el valor de dispersión de la clave dada. */

virtual iterator<T> * makeIterator (const unsigned int &) = 0;

/* Necesita: un número de clase o cubeta.

Produce: un iterador para la clase dada. */

};

template <class B, class H, class T>

hashTable<B, H, T>::hashTable (const unsigned int & max,

unsigned int (*f)(const H &))

: tablesize(primo(max)), buckets(primo(max)), hashfun(f)

{

for (unsigned int i = 0; i < tablesize; i++) {

buckets[i] = new B;

assert(buckets[i] != 0);

}

template <class B, class H, class T>

hashTable<B, H, T>::hashTable

(const hashTable<B, H, T> & source)

: tablesize(source.tablesize), buckets(source.buckets),

hashfun(source.hashfun)

{

for (unsigned int i = 0; i < tablesize; i++) {

buckets[i] = new B(*source.buckest[i]);

assert(buckets[i] != 0);

}

template <class B, class H, class T>

bool hashTable<B, H, T>::isEmpty () const

{

for (int i = 0; i < tablesize; i++)

if (!buckets[i]->isEmpty())

return false;

// todas las cubetas están vacías

return true;

}

template <class B, class H, class T>

void hashTable<B, H, T>::deleteAllValues()

{

// borrar todos los elementos en cada cubeta

for (int i = 0; i < tablesize; i++)

buckets[i]->deleteAllValues();

}

template <class B, class H, class T>

unsigned int hashTable<B, H, T>::hash (const H & key) const

{

return (*hashfun)(key) % tablesize;

}

template <class B, class H, class T>

class hashTableIterator : public iterator<T> {

public:

// constructor

hashTableIterator(hashTable<B, H, T> & aHashTable);

hashTableIterator(const hashTableIterator<B, H, T> & source);

// protocolo iterador

virtual bool init ();

virtual T operator () ();

virtual bool operator ! ();

virtual bool operator ++ ();

virtual bool operator ++ (int);

virtual T & operator = (const T & value);

protected:

// área de datos

unsigned int currentIndex; // índice de la cubeta actual

iterator<T> * itr; // iterador de la cubeta actual

hashTable<B, H, T> & base;

// operación interna

bool getNextIterator ();

/* Efecto: obtiene el iterador sobre la siguiente

cubeta no vacía.

Produce: cierto si encuentra una cubeta no vacía. */

};

template <class B, class H, class T>

hashTableIterator<B, H, T>::hashTableIterator

(hashTable<B, H, T> & aHashTable)

: base(aHashTable), currentIndex(0), itr(0)

{

init();

}

template <class B, class H, class T>

bool hashTableIterator<B, H, T>::init ()

{

// obtener la primera cubeta no vacia

currentIndex = 0;

return getNextIterator();

}

template <class B, class H, class T>

T hashTableIterator<B, H, T>::operator () ()

{

return (*itr)();

}

template <class B, class H, class T>

bool hashTableIterator<B, H, T>::operator ! ()

{

return itr != 0;

}

template <class B, class H, class T>

bool hashTableIterator<B, H, T>::operator ++ ()

{

// si se puede, avanzar en el iterador actual

if (itr && (*itr)++)

return true;

// en caso contrario obtener el siguiente iterador

currentIndex++;

return getNextIterator();

}

template <class B, class H, class T>

bool hashTableIterator<B, H, T>::getNextIterator ()

{

if (itr != 0)

delete itr;

// buscar el nuevo cubo en el que iterar

for (; currentIndex < base.tablesize; currentIndex++) {

itr = base.makeIterator(currentIndex);

assert(itr != 0);

if (itr->init()) // si hay elemento actual retornar

return true;

delete itr;

}

itr = 0; // no hay más elementos

return false;

}

REPRESENTACIÓN BASADA EN LISTAS

Sus primitivas son:

// Clase hashList

// Implementación de la clase hashTable con listas.

// La clave es el valor.

template <class T>

class hashList : public hashTable<setList<T>, T, T> {

public:

// constructores

hashList (const unsigned int & max,

unsigned int (*f) (const T &));

hashList (const hashList<T> & source);

void add (const T & value);

/* Necesita: un valor de tipo T.

Modifica: la tabla receptora añadiendo, si no existe,

el valor dado. */

bool includes (const T & value) const;

/* Necesita: un valor de tipo T.

Produce: cierto si el valor dado se encuentra

en la tabla receptora. */

void remove (const T & value);

/* Necesita: un valor de tipo T.

Modifica: la tabla receptora eliminando de la misma,

si existe, el valor dado. */

protected:

// operación interna

virtual iterator<T> * makeIterator (const unsigned int & i );

};

template <class T>

hashList<T>::hashList (const unsigned int & max,

unsigned int (*f) (const T &))

: hashTable<setList<T>, T, T>(max, f)

{}

template <class T>

void hashList<T>::add (const T & value)

{

buckets[hash(value)]->add(value);

}

template <class T>

bool hashList<T>::includes (const T & value) const

{

return buckets[hash(value)]->includes(value);

}

template <class T>

void hashList<T>::remove (const T & value)

{

buckets[hash(value)]->remove(value);

}

template <class T>

iterator<T> * hashList<T>::makeIterator (const unsigned int & i)

{

return new setListIterator<T>(*buckets[i]);

}

template <class T> class hashListIterator

: public hashTableIterator<setList<T>, T, T> {

public:

hashListIterator (hashList<T> & aHashList);

hashListIterator (const hashListIterator<T> & source);

};

template <class T>

hashListIterator<T>::hashListIterator (hashList<T>

& aHashList)

: hashTableIterator<setList<T>, T, T>(aHashList)

{

}

template <class T>

hashListIterator<T>::hashListIterator

(const hashListIterator<T> & source)

: hashTableIterator<setList<T>, T, T>(source)

{

}

OTRAS REPRESENTACIONES

Para las cubetas de las tablas de dispersión abiertas en las que las claves son los mismo elementos se puede elegir cualquier clase en las que se disponga, o se pueden realizar fácilmente, de las operaciones add, includes y remove. Así, por ejemplo, se podría realizar una clase similar a la anterior utilizando árboles AVL en lugar de listas.

En los casos en que la clave no coincide con el elemento es necesario almacenar el par (clave,valor) y las operaciones en la tabla de dispersión se realizan en función de la clave. En consecuencia, las cubetas deberían ser colecciones de pares (clave, valor); es decir, diccionarios.

Representación Basada en Diccionarios

Sus primitivas son:

template <class H, class T>

class hashDictionary

: public hashTable<dictionaryList<H, T>, H,

association<H, T> *> {

public:

// constructores

hashDictionary (const unsigned int & max,

unsigned int (*f) (const H &));

hashDictionary (const unsigned int & max,

unsigned int (*f) (const H &), const T & initial);

hashDictionary (const hashDictionary<H, T> & source);

// operación de acceso

T & operator [] (const H & key);

// test de pertenencia

bool includesKey (const H & key) const;

// operación de borrado

void removeKey (const H & key);

protected:

virtual iterator<association<H, T> *> *

makeIterator (const unsigned int & i);

};

template <class H, class T>

hashDictionary<H, T>::hashDictionary

(const unsigned int & max,

unsigned int (*f) (const H &), const T & initial)

: hashTable<dictionaryList<H, T>, H,

association<H, T> *>(max, f)

{

for (unsigned int i = 0; i < tablesize; i++)

buckets[i]->setInitial(initial);

}

template <class H, class T>

T & hashDictionary<H, T>::operator [] (const H & key)

{

return buckets[hash(key)]->operator[](key);

}

template <class H, class T>

iterator<association <H, T> *> *

hashDictionary<H, T>::makeIterator (const unsigned int & i)

{

return new dictionaryListIterator<H, T>(*buckets[i]);

}

template <class H, class T>

class hashDictionaryIterator

: public hashTableIterator<dictionaryList<H, T>, H,

association<H, T> *> {

public:

hashDictionaryIterator

(hashDictionary<H, T> & aHashDictionary);

hashDictionaryIterator

(const hashDictionaryIterator<H, T> & source);

};

template <class H, class T>

hashDictionaryIterator<H, T>::hashDictionaryIterator

(hashDictionary<H, T> & aHashDictionary)

: hashTableIterator<dictionaryList<H, T>,

H, association<H, T> *>(aHashDictionary)

{

}

template <class H, class T>

hashDictionaryIterator<H, T>::hashDictionaryIterator

(const hashDictionaryIterator<H, T> & source)

: hashDictionaryIterator<dictionaryList<H, T>,

H, association<H, T> *>(source)

{

}

TABLAS DE DISPERSIÓN CERRADAS

Al igual que las tablas de dispersión abiertas, las tablas de dispersión cerradas son estructuras de datos que permiten reducir de forma significativa el coste de las operaciones de inserción, borrado y test de pertenencia en grandes colecciones. Para ello, también en este caso se utiliza la función de dispersión sobre la clave de los elementos para distribuir éstos en b clases numeradas de 0 a b-1.

Sin embargo, en una tabla de dispersión cerrada sólo se permite un elemento por clase, ya que los miembros de la colección se almacenan directamente en la tabla, en vez de usar ésta para almacenar las direcciones de las cubetas.

Como es obvio, no es posible asegurar que la función de dispersión sea inyectiva y, por tanto, deberá existir una estrategia de redispersión (función de rehashing) para miembros de la colección con el mismo valor de dispersión.

Así, si se intenta colocar x en la cubeta h(clave_de_x) y ésta ya tiene un elemento (situación denominada colisión), la estrategia de redispersión elige una sucesión de cubetas alternativas h1(clave_de_x), h2(clave_de_x), ... hasta encontrar una libre en la que poder ubicar el elemento.

ANÁLISIS DE DISPERSIÓN CERRADA

Las primitivas son:

template <class H, class T>

class hashVector {

friend class hashVectorIterator<H, T>;

public:

// constructores

hashVector (unsigned int max,

unsigned int (*hash)(const H &),

unsigned int (*rhash)(const H &, int));

hashVector (unsigned int max,

unsigned int (*hash)(const H &),

unsigned int (*rhash)(const H &, int),

const T & init);

hashVector (const hashVector<H, T> & source);

// destructor

~hashVector ();

// test de vacío

bool isEmpty () const;

// operación de índice (adición, acceso y modificación)

T & operator [] (const H & aKey);

// operación de borrado

void remove (const H & aKey);

// test de pertenencia

bool includes (const H & aKey);

// borrado de todos los elementos

void deleteAllValues ();

protected:

// área de datos

vector<association<H,T> *> data; // tabla de cubetas

vector<bool> erase; // se borró el contenido de una

// cubeta?

unsigned int numberOfSlots; // cubetas nunca ocupadas

unsigned int numberOfElements; // elementos en la tabla

unsigned int tablesize; // dimensión de la tabla

T initial; // valor por defecto

unsigned int (*hashfun) (const H &); // función hash

unsigned int (*rhashfun) (const H &, int); // función

// de rehash

// operaciones internas

unsigned int firstEqualEmpty (const H &) const;

/* Necesita: una clave.

Produce: la cubeta que contiene la clave dada, o la

primera cubeta nunca ocupada que se

encuentra en la sucesión de cubetas que se

obtiene al aplicar la función de dispersión y,

si es necesario, las funciones de redispersión

a la clave dada. */

unsigned int firstEqualEraseEmpty (const H &) const;

/* Necesita: una clave.

Produce: la cubeta que contiene la clave dada, o la

primera cubeta nunca ocupada o en la que

se borró el contenido, en la sucesión de cubetas

generada al aplicar la función de dispersión

y, si es necesario, las funciones de redispersión

a la clave dada. */

};

template <class H, class T>

hashVector<H, T>::hashVector

(unsigned int max, unsigned int (*hash)(const H &),

unsigned int (*rhash)(const H &, int))

: data(primo(max), (association<H, T> *) 0),

erase(primo(max), false), hashfun(hash),

rhashfun(rhash), numberOfElements(0)

{

tablesize = data.length();

numberOfSlots = tablesize;

}

template <class H, class T>

hashVector<H, T>::hashVector

(const hashVector<H,T> & source)

: data(source.tablesize), erase(source.erase),

hashfun(source.hashfun), rhashfun(source.rhashfun),

numberOfSlots(source.numberOfSlots),

numberOfElements(source.numberOfElements),

tablesize(source.tablesize), initial(source.initial)

{

for (unsigned int i = 0; i < tablesize; i++)

if (source.data[i])

data[i] = new association<H, T>(*source.data[i]);

else

data[i] = 0;

}

template <class H, class T>

hashVector<H, T>::~hashVector ()

{

deleteAllValues();

}

template <class H, class T>

bool hashVector<H, T>::isEmpty () const

{

for (int i = 0; i != data.length() ; i++)

if (data[i])

return false;

return true;

}

template <class H, class T>

unsigned int hashVector<H, T>::firstEqualEmpty

(const H & aKey) const

{

int pos = (*hashfun)(aKey) % tablesize;

for (unsigned int i=0; i < tablesize && (data[pos] ||

erase[pos]) && data[pos]->key() != aKey; i++)

pos = (*rhashfun)(aKey, i+1) % tablesize;

return pos;

}

template <class H, class T>

unsigned int hashVector<H, T>::firstEqualEraseEmpty

(const H & aKey) const

{

int pos = (*hashfun)(aKey) % tablesize;

for (unsigned int i=0; i < tablesize && data[pos]

&& data[pos]->key() != aKey; i++)

pos = (*rhashfun)(aKey, i+1) % tablesize;

return pos;

}

template <class H, class T>

bool hashVector<H, T>::includes (const H & aKey)

{

int pos = firstEqualEmpty(aKey);

return data[pos] && data[pos]->key() == aKey;

}

template <class H, class T>

T & hashVector<H, T>::operator [] (const H & aKey)

{

int pos = firstEqualEmpty(aKey);

// clave encontrada

if (data[pos] && data[pos]->key() == aKey)

return data[pos]->valueField;

// clave no encontrada

pos = firstEqualEraseEmpty(aKey);

// si es necesario redimensionar la tabla

if (numberOfSlots <= 0.1 * tablesize) {

vector<association<H,T> *> oldData(data);

// inicialmente en la nueva tabla no habra elementos

tablesize = primo(2 * tablesize); // se duplica el

// espacio

data = vector<association<H,T> *> (tablesize,

(association<H,T> *) 0);

erase = vector<bool>(tablesize, false);

numberOfSlots = tablesize;

numberOfElements = 0;

// insertar todos los elementos que ya estaban en

// la tabla

for (unsigned int i = 0; i < oldData.length(); i++)

if (oldData[i] != 0) {

operator [] (oldData[i]->key()) =

oldData[i]->value();

delete oldData[i];

}

// insertar clave y valor por defecto

data[pos] = new association<H,T>(aKey, initial);

if (erase[pos])

erase[pos] = false;

else

numberOfSlots--;

numberOfElements++;

return data[pos]->valueField;

}

template <class H, class T>

void hashVector<H, T>::remove (const H & aKey)

{

int pos = firstEqualEmpty(aKey);

if (data[pos] && data[pos]->key() == aKey) {

erase[pos] = true;

numberOfElements--;

// recuperar el espacio

delete data[pos];

data[pos] = 0;

}

template <class H, class T>

class hashVectorIterator : public iterator<T> {

public:

// constructor

hashVectorIterator (hashVector<H, T> & aHashVector);

hashVectorIterator (const hashVectorIterator<H, T> & source);

// protocolo iterador

virtual bool init ();

virtual bool operator ! ();

virtual bool operator ++ (); // prefijo

virtual bool operator ++ (int); // postfijo

virtual T operator () ();

virtual T & operator = (const T & val);

// método especifico de esta subclase

H key ();

/* Produce: la clave del elemento actual. */

protected:

// área de datos

unsigned int currentKey;

hashVector<H, T> & theHashVector;

// operación interna

bool getNext ();

/* Efecto: obtiene la siguiente cubeta que contiene

un elemento de la tabla.

Produce: cierto si encuentra una cubeta no vacía. */

};

template <class T>

void heapSort (vector<T> & v)

/* Necesita: un vector v.

Modifica: el vector ordenando sus componentes por

el método del montículo (heap). */

{

unsigned int n = v.length();

for (int i = n / 2 - 1; i >= 0; --i)

reorganize(v, i, n - 1);

for (unsigned int i = n - 1; i > 0; --i) {

swap(v, 0, i);

reorganize(v, 0, i-1);

}

template <class T>

setList<setList<T> *> partes (setList<T> & c)

{

setListIterator<T> itrC(c);

setList<setList<T> *> result;

setList<T> * vacio = new setList<T>();

// adición del conjunto vacío

result.add(vacio);

for (itrC.init(); !itrC; ++itrC) {

setList<setList<T> *> temp(result);

setListIterator<setList<T> *> itrT(temp);

for (itrT.init(); !itrT; ++itrT) {

// añadir el elemento de C a cada elemento de temp

setList<T> * newParte = new setList<T>(*itr());

newParte->add(itrC());

result.add(newParte);

}

return result;

}

FUNCIONES HASH

Como se mencionó antes, uno de los problemas a abordar con las tablas hash es el cálculo de la función hash, que transforma claves en localizaciones de la tabla.

Más concretamente, necesitamos una función que transforme claves(normalmente enteros o cadenas de caracteres) en enteros en un rango [0..M-1], donde M es el número de registros que podemos manejar con la memoria de que dispongamos. Como factores a tener en cuenta para la elección de la función h(k) están que minimice las colisiones y que sea relativamente rápida y fácil de calcular, aunque la situación ideal sería encontrar una función h que generara valores aleatorios uniformemente sobre el intervalo [0..M-1]. Las dos aproximaciones que veremos están encaminadas hacia este objetivo y ambas están basadas en generadores de números aleatorios.

HASHING MULTIPLICATIVO

Esta técnica trabaja multiplicando la clave k por sí misma o por una constante, usando después alguna porción de los bits del producto como una localización de la tabla hash.

Cuando la elección es multiplicar k por sí misma y quedarse con alguno de los bits centrales, el método se denomina el cuadrado medio. Este método, aún siendo simple y pudiendo cumplir el criterio de que los bits elegidos para marcar la localización son función de todos los bits originales de k, tiene como principales inconvenientes el que las claves con muchos ceros se reflejarán en valores hash también con muchos ceros, y el que el tamaño de la tabla está restringido a ser una potencia de 2.

Otro método multiplicativo, que evita las restricciones anteriores consiste en calcular h(k) = Int[M * Frac(C*k)] donde M es el tamaño de la tabla y 0 <= C <= 1, siendo importante elegir C con cuidado para evitar efectos negativos como que una clave alfabética K sea sinónima a otras claves obtenidas permutando los caracteres de k. Knuth prueba que un valor recomendable es:

HASHING POR DIVISIÓN

En este caso la función se calcula simplemente como h(k) = k mod M usando el 0 como el primer índice de la tabla hash de tamaño M.

Aunque la fórmula es aplicable a tablas de cualquier tamaño es importante elegir el valor de M con cuidado. Por ejemplo si M fuera par, todas las claves pares (resp. impares) serían aplicadas a localizaciones pares (resp. impares), lo que constituiría un sesgo muy fuerte. Una regla simple para elegir M es tomarlo como un número primo. En cualquier caso existen reglas mas sofisticadas para la elección de M, basadas todas en estudios teóricos de funcionamiento de los métodos de generación de números aleatorios.

BORRADOS Y REHASHING

Cuando intentamos borrar un valor k de una tabla que ha sido generada por dispersión cerrada, nos encontramos con un problema. Si k precede a cualquier otro valor k en una secuencia de pruebas, no podemos eliminarlo sin más, ya que si lo hiciéramos, las pruebas siguientes para k se encontrarían el "agujero" dejado por k por lo que podríamos concluir que k no está en la tabla, hecho que puede ser falso. La solución es que necesitamos mirar cada localización de la tabla hash como inmersa en uno de los tres posibles estados: vacía, ocupada o borrada, de forma que en lo que concierne a la búsqueda, una celda borrada se trata exactamente igual que una ocupada. En el caso de las inserciones, podemos usar la primera localización vacía o borrada que se encuentre en la secuencia de pruebas para realizar la operación. Observemos que este problema no afecta a los borrados de las listas en la dispersión abierta. Para la implementación de la idea anterior podría pensarse en la introducción en los algoritmos de un valor etiqueta para marcar las casillas borradas, pero esto sería solo una solución parcial ya que quedaría el problema de que si los borrados son frecuentes, las búsquedas sin éxito podrían requerir O(M) pruebas para detectar que un valor no está presente.

Cuando una tabla llega a un desbordamiento o cuando su eficiencia baja demasiado debido a los borrados, el único recurso es llevarla a otra tabla de un tamaño más apropiado, no necesariamente mayor, puesto que como las localizaciones borradas no tienen que reasignarse, la nueva tabla podría ser mayor, menor o incluso del mismo tamaño que la original. Este proceso se suele denominar rehashing y es muy simple de implementar si el arca de la nueva tabla es distinta al de la primitiva, pero puede complicarse bastante si deseamos hacer un rehashing en la propia tabla.

RESOLUCIÓN DE CONFLICTOS

MEDIANTE REDISPERSIÓN

Supongamos que tenemos almacenados una colección de datos en una tabla de dispersión según se ilustra en la figura:

Imaginemos que queremos introducir en la tabla un nuevo dato cuya clave es 596397. Utilizando una función de dispersión,

f (k) = k % 1000

obtenemos f (596397) = 397. Por lo tanto, el dato habrá que almacenarlo en la posición 397.

Sin embargo, observamos que dicha posición está ocupada por otro dato con clave distinta (4957397), por lo que el nuevo dato se deberá insertar en otra posición.

El método más simple consiste en realizar una búsqueda lineal de la siguiente posición libre en el vector, es decir, definir

h (k) = (k+1) % 1000

Sin embargo, dependiendo de la función de dispersión elegida, puede ser que no encontremos ninguna posición para insertar el nuevo elemento. Esto puede ocurrir porque la tabla está llena, por lo que habrá que llevar la cuenta del número de elementos que ya se han almacenado, o bien porque la función de dispersión secundaria nos remita a una posición ocupada a pesar de que existan posiciones libres. Para evitar ésta última situación, hay que exigir a la función h que produzca índices uniformemente distribuidos en el intervalo 0, …, n-1 (siendo n el número de elementos del vector).

MEDIANTE ENCADENAMIENTO

Este método consiste en permitir múltiples claves de registros en una misma posición. En este caso existen dos posibilidades:

1. Una solución es dejar que cada dirección calculada contenga espacios para múltiples pares, en vez de un único par. Cada una de estas posiciones se denomina cubo. La siguiente figura ilustra la forma que tendría una tabla hash:

Por ejemplo, una tabla con 26 posiciones y 2 pares por cubo, tendría el siguiente aspecto (los 0 indican registros vacíos):

	SLOT 1	SLOT 2
1	A	A2
2	0	0
3	0	0
4	D	0
5	GA	G
…	…	…
26	0	0

2. Otra solución, es usar la dirección calculada, no como posición real del registro, sino como el índice en un vector de listas enlazadas. Cada posición del vector accede a una lista de pares que comparten la misma dirección.

La siguiente figura ilustra esta situación:

Para buscar un registro dado, aplicamos primero la función hash a su clave y luego buscamos la cadena para el registro en la línea. De este modo, si la lista es muy grande, se pierde la eficiencia del método.

En la siguiente figura se comparan los esquemas de redireccionamiento y encadenamiento para la misma función hash:

f (k) = k mod 100

Los registros se añadieron en el orden:

45300, 20006, 50002, 40000, 25001, 13000, 65905, 30001, 95000

FUNCIONES DE DISPERSIÓN

Analicemos la eficiencia de los dos tipos de dispersión vistos (si suponemos que tenemos N elementos y B cubetas):

Dispersión abierta.

– Si tenemos B cubetas, y N elementos almacenados en total.

– Cada lista tendrá de media N/B miembros.

– Las operaciones Inserta, Suprime y Miembro tendrá un tiempo de O(1+N/B).

– Si N £ B, entonces tendremos O(cte).

– Si suponemos una buena función h: reparte los elementos en las cubetas de forma uniforme.

Dispersión cerrada.

– La tabla nunca se puede llenar con más de B elementos.

– La probabilidad de colisión crece cuantos más elementos haya, disminuyendo la eficiencia.

– El costo de la operación Inserta es O(1/(1-N/B)). Cuando N ® B tiende a infinito.

Para evitar el problema de la pérdida de eficiencia, se puede tomar la medida de que si el tamaño N aumenta mucho, se cree una nueva tabla con más elementos B, y luego se pasa a reestructurar la tabla hash.

En la dispersión abierta se opta por reestructurar sin N > 2B.

En el caso de la dispersión cerrada, reestructurar si N > 0.9B.

EJEMPLO

• Una aplicación almacena información sobre determinados objetos.

• Necesitamos acceder a los objetos de forma ordenada (según determinada propiedad de los mismos) y de forma directa (según otra propiedad).

• Ejemplo:

– Un ranking de tenistas, ordenados según su categoría. Necesitamos acceder según el orden del ranking y según los nombres de los tenistas.

– Cada tenista nuevo es añadido en el último lugar del ranking.

– Un jugador puede retar al anterior en el ranking. Si le gana intercambian sus posiciones en el ranking.

– Operaciones: Agrega(nombre); anterior:= Reta(nombre);

Cambia(posición);

• Soluciones posibles:

– Usar un array Escala[i]= nombre_tenista.

Agrega y Cambia son rápidas, O(cte), pero Reta necesita recorrer todo el array para buscar el nombre del tenista, O(n).

– Usar una tabla de dispersión con nombres, indicando la posición.

Agrega tiene O(cte). Reta y Cambia tienen O(n). El acceso por nombres es rápido pero por posiciones es lento, se debe buscar toda la tabla.

• Otra solución:

– Combinar las estructuras anteriores, array y tabla de dispersión.

– Agrega (nombre): Insertar en las dos estructuras: O(cte).

– Reta (nombre): Buscar en la tabla hash y acceder luego a Escala: O(cte).

– Cambia (posición): Cambiar las posiciones en los dos lugares: O(cte).

• En general, una estructura de datos dual es aquella que combina dos o más tipos diferentes de estructuras.

• Ventajas: Si está bien diseñada, incrementa la eficiencia de las operaciones.

• Inconvenientes: Hay duplicación de información, se desperdicia memoria.