Tema 5 - Examples/Ejercicios

(Java) Implementa los métodos correspondientes si usamos Linear Probing como se describe en las
últimas transparencias del tema 5. La clase debe implementar la interfaz siguiente:

public interface HashTable<K, V> extends Iterable<K> {
       public boolean isEmpty();
       public int size();
       public void insert(K key, V value);
       public V search(K key);
       public boolean isElem(K key);
       public void delete(K key);
       Iterable<K> keys();
       Iterable<V> values();
       Iterable<Tuple2<K,V>> keysValues();
}
Usa las siguientes variables de instancia y constructor de la clase:
public class LinearProbingHashTable<K,V> implements HashTable<K,V> {
       private K keys[];
       private V values[];
       private int size;
       private double maxLoadFactor;
       public LinearProbingHashTable(int numCells, double loadFactor) {
              keys = (K[]) new Object[numCells];
              values = (V[]) new Object[numCells];
              size = 0;
              maxLoadFactor = loadFactor;
       }
}
Antes de todo, define el método:

private int searchIdx(K key)

que toma una clave y devuelve la posición donde debemos insertar un elemento con tal clave
utilizando prueba lineal. Para memorizar pares de claves y valores usaremos dos tablas; si la
posición devuelta por el método searchIdx correspondiente a una clave k es p, k deberá
memorizarse en keys[p] y el correspondiente valor en values[p]. Si tras un número de
inserciones el factor de carga sobrepasa el límite maxLoadFactor, las tablas deben reasignarse a
través del método:

private void rehashing() {
       // computamos un nuevo tamaño de las tablas
       int newCapacity = HashPrimes.primeDoubleThan(keys.length);
       K oldKeys[] = keys;
       V oldValues[] = values;
       keys = (K[]) new Object[newCapacity];
       values = (V[]) new Object[newCapacity];
       // reinsertamos los elementos en las nuevas tablas
       for(int i=0; i<oldKeys.length; i++)
              if(oldKeys[i] != null) {
                     int newIdx = searchIdx(oldKeys[i]);
                     keys[newIdx] = oldKeys[i];
                     values[newIdx] = oldValues[i];
              }
}
Para impIementar la operación delete, primeramente debemos localizar la posición
correspondiente p en la tabla de claves, y asignar null a las posiciones keys[p] y values[p], y a
continuación trasladar (borrar y reinsertar) los elementos posteriores para no dejar huecos.


public class LinearProbingHashTable<K, V> implements HashTable<K, V> {
private K keys[];  // Invariante: Siempre hay al menos un hueco private V values[]; private int size; private double maxLoadFactor; // Invariante:   0 < maxLoadFactor < 1
public LinearProbingHashTable(int numCells, double loadFactor) { keys = (K[]) new Object[numCells]; values = (V[]) new Object[numCells]; size = 0; maxLoadFactor = loadFactor; }
public boolean isEmpty() { return size == 0; }
public int size() { return size; }
private int hash(K key) { return (key.hashCode() & 0x7fffffff) % keys.length; }
private double loadFactor() { return (double) size / (double) keys.length; }
private int searchIdx(K key) { int x = hash(key); //primero comprobamos si es distinto de null el campo a buscar, si no lo es comprobamos si es igual. //debemos comprobar primero sino es null para que no salte la excepcion de null pointeger. if(keys[x]!=null && keys[x].equals(key)){ return x; } while(keys[x]!=null && !keys[x].equals(key)){ x= (x + 1)%keys.length; } if(keys[x].equals(key)){ return x; } return -1; }
public V search(K key) { int x = hash(key); if(keys[x].equals(key)){ return values[x]; } else{ while(keys[x]!=null && !keys[x].equals(key) && values[x]!=null){ x= (x + 1)%keys.length; } } if(keys[x].equals(key)){ return values[x]; } return null; }
public boolean isElem(K key) { // POR HACER return searchIdx(key)!=-1; }
public void insert(K key, V value) { int x = hash(key); // Aseguramos que loadFactor() es menor que 1, es decir que hay hueco. if(loadFactor()>maxLoadFactor) rehashing(); if(keys[x]==null || keys[x].equals(key)){ keys[x]=key; values[x]=value; } while(keys[x]!=null && !keys[x].equals(key)){ x = (x + 1)%keys.length; } keys[x]=key; values[x]=value; size++; }
public void delete(K key) { int x = searchIdx(key); if(x!=-1){ keys[x]=null; --size; } }
private void rehashing() { // compute new table size int newCapacity = HashPrimes.primeDoubleThan(keys.length); //System.out.printf("REHASH %d\n",newCapacity); K oldKeys[] = keys; V oldValues[] = values; keys = (K[]) new Object[newCapacity];   values = (V[]) new Object[newCapacity]; // reinsert elements in new table for(int i=0; i<oldKeys.length; i++){ if(oldKeys[i] != null) { int newIdx = searchIdx(oldKeys[i]); keys[newIdx] = oldKeys[i]; values[newIdx] = oldValues[i]; } } }
// An iterator on keys in table private class TableIter implements Iterator<K> { private int traversed; // Numero de elementos visitados private int nextIdx;   // Indice del siguiente nodo a visitar
public TableIter() { traversed = 0; nextIdx = 0; }
public boolean hasNext() { return size!=traversed; }
public K next() { if (!hasNext()) throw new NoSuchElementException(); while(keys[nextIdx]== null){ nextIdx++; } K temp = keys[nextIdx]; nextIdx++; traversed++; return temp; }
public void remove() { throw new UnsupportedOperationException(); }
}
public Iterator<K> iterator() { return new TableIter(); }
}