Tablas hash

TABLAS HASH
INTRODUCCIÓN
- 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), función de dispersión, que nos dé directamente la localización de la clave k en la tabla. - La función de dispersión seaplica a lo que habitualmente se denomina como la clave del elemento (y que en ocasiones será él mismo). Se denomina valor de dispersión al valor h(clave_de_x), y cubetas a las clases. Se dice que x pertenece a la cubta de h(clave_de_x).

- El objetivo será encontrar una función hash que provoque el menor número posible de colisiones (ocurrencias de sinónimos), aunque esto es solo un aspecto delproblema, el otro será el de diseñar métodos de resolución de colisiones cuando éstas se produzcan.

TABLAS DE DISPERSIÓN ABIERTAS
- La manera más simple de resolver una colisión es construir, para cad a localización de la tabla, una lista enlazada de registros cuyas claves caigan en esa dirección. Puede ser LIFO o FIFO.

CLASE ABSTRACTA
template class hashTable { friend classhashTableIterator; public: // constructores

hashTable (const unsigned int & max, unsigned int (*f) (const H &)); hashTable (const hashTable & 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 buckets; unsignedint (*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 * makeIterator (const unsigned int &) = 0; /* Necesita: un número de clase o cubeta. Produce: un iterador para la clase dada. */ };

template hashTable::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 hashTable::hashTable (const hashTable & 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 bool hashTable::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 void hashTable::deleteAllValues() { // borrar todos los elementos en cada cubeta for (int i = 0; i < tablesize; i++)

buckets[i]->deleteAllValues(); }

template unsigned inthashTable::hash (const H & key) const { return (*hashfun)(key) % tablesize; }

template class hashTableIterator : public iterator { public: // constructor hashTableIterator(hashTable & aHashTable); hashTableIterator(const hashTableIterator & 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 * itr; // iterador de la cubeta actual hashTable & 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. */ };

templatehashTableIterator::hashTableIterator (hashTable & aHashTable) : base(aHashTable), currentIndex(0), itr(0) { init(); }

template bool hashTableIterator::init () { // obtener la primera cubeta no vacia currentIndex = 0; return getNextIterator(); }

template T hashTableIterator::operator () () { return (*itr)(); }

template bool hashTableIterator::operator ! () { return itr != 0; }

template bool...