ClosedHashTables
Publicado: 23 Dic 2015, 16:33
por sanko
Paquete Tablas Hash Cerradas:
AbstractHash:
HashNode:
ClosedHashTable:
ClosedHashTableTest:
ClosedHashTableTest2:
Código: Seleccionar todo
- AbstractHash
- HashNode
- ClosedHashTable
- ClosedHashTableTest
- ClosedHashTableTest2package tablasHash;
/**
* @author Néstor
* @version 2015-16
*
* @param <T>
*/
public abstract class AbstractHash <T>{
/**
* Devuelve el número de elementos que contiene la tabla Hash en el momento de la invocación
*
* @return El número de elementos.
*/
abstract public int getNumOfElems();
/**
* Devuelve el tamaño de la tabla Hash
*
* @return El tamaño de la tabla, conveniente que sea un número primo
*/
abstract public int getSize();
/**
* Inserta un nuevo elemento en la tabla hash
*
* @param elem Elemento que se inserta
* @return true si lo ha insertado o false en caso contrario
*/
abstract public boolean add(T elem);
/**
* Busca y devuelve un elemento de la tabla hash
*
* @param elem La clave que se busca,
*
* @return El elemento encontrado si lo encuentra o null en caso contrario
*/
abstract public T find(T elem);
/**
* Borra un elemento que se encuentra en la tabla hash
*
* @param elem elemento para borrar
* @return true si lo ha borrado o false en caso contrario
*/
abstract public boolean remove(T elem);
/**
* Realiza una redispersión (aumentando el tamaño) al número primo mayor que el doble del tamaño actual, y recolocando los elementos
*
* @return true si la realiza, false en caso contrario
*/
abstract protected boolean reDispersion ();
/**
* Realiza una redispersión inversa (disminuyendo el tamaño) al número primo menor que la mitad del tamaño actual, y recolocando los elementos
* @return true si la realiza, false en caso contrario
*/
abstract protected boolean inverseReDispersion();
/**
* Convierte la tabla a una String que se pueda mostrar de forma "visible"
*
* @return el String con la información de la tabla hash
*/
abstract public String toString ();
/**
* Calcula el resultado de aplicar la función hash sobre el parámetro (versión 2015-16)
* Utiliza hashCode() Convierte posibles negativos a positivos
*
* @return el resultado correspondiente
*/
protected int fHash(T elem){
int primo=getSize();
return (elem.hashCode()%primo+primo)%primo;
}
/**
*
* Calcula si un número positivo es un número primo, los negativos devuelve que no lo son
*
* @param n El número que queremos comprobar
* @return true si es primo, false en caso contrario
*/
protected boolean isPrime(int n){
if (n<2 || (n>2 && n%2==0))
return false;
if (n<=7)
return true;
for (int i=3;i*i<=n;i+=2) //impares
if (n%i==0)
return false; // no es primo
return true;
}
/**
* @param n El número del que se quiere saber el siguiente número primo mayor que él
* @return El primer número primo mayor que el parámetro
*/
protected int nextLargestPrimeNumber(int n){
int num=n+1;
while (!isPrime(num)) {
num++;
}
return num;
}
/**
* @param n El número del que se quiere saber el anterior número primo menor que él.
* @return El primer número primo menor, si no hay números primos menores, devuelve el menor número primo (positivo) 2
*/
protected int previousSmallerPrimeNumber (int n){
if (n<=2)
return 2;
int num=n-1;
while (!isPrime(num)) {
num--;
}
return num;
}
}package tablasHash;
/**
* @author Néstor
* @version 2015-16
*
* @param <T>
*/
public class HashNode<T> {
private T info;
private byte estado;
static final byte BORRADO = -1;
static final byte VACIO = 0;
static final byte LLENO = 1;
public HashNode () {
info = null;
estado=VACIO;
}
public T getInfo() {
return info;
}
public void borrar (){
estado=BORRADO;
}
public void setInfo(T elem){
info=elem;
estado=LLENO;
}
public byte getEstado() {
return estado;
}
public String toString (){
StringBuilder cadena=new StringBuilder("{");
switch (getEstado()){
case LLENO:
cadena.append(info);
break;
case VACIO:
cadena.append("_E_");
break;
case BORRADO:
cadena.append("_D_");
}
cadena.append("}");
return cadena.toString();
}
}package tablasHash;
/**
* @author Esteban
* @version 2015-16
*
*/
public class ClosedHashTable<T> extends AbstractHash<T> {
// IMPORTANTE
// No cambiar el nombre ni visibilidad de los atributos protected
protected HashNode<T> associativeArray[];
private int hashSize; // Tamaño de la tabla, debe ser un número primo (B de teoría)
private int numElementos; // Número de elementos en la tabla en cada momento.
static final byte LINEAL = 0; // Tipo de exploración en caso de colisión, por defecto será LINEAL
static final byte CUADRATICA = 1;
static final byte DOBLE = 2;
private double fcUP; // Límite superior para aumentar tamaño de tabla
private double fcDOWN; // Límite inferior para disminuir el tamaño de tabla
private byte expl;
/**
* Constructor para fijar el tamaño, los factores de carga límite para redispersión y redispersion inversa
* y el tipo de exploración en las colisiones
* @param tam tamaño del Hash, si no es un número primo lo ajusta al primo superior
* @param fcUP Factor de carga límite, por encima del cual hay que redispersar (directa)
* @param fcDOWN Factor de carga límite, por debajo del cual hay que redispersar (inversa)
* @param expl tipo de exploración (LINEAL=0, CUADRATICA=1, ...), si inválido LINEAL
*/
@SuppressWarnings("unchecked")
public ClosedHashTable(int tam, double fcUP, double fcDOWN, byte expl) {
//Si el tamaño es un número primo...
if(isPrime(tam))
{
//Creamos una tabla de dicho tamaño
associativeArray = new HashNode[tam];
//Creamos todos los nodos de la tabla
for(int i = 0; i < tam; i++)
{
associativeArray[i] = new HashNode<T>();
}
this.fcUP = fcUP;
this.fcDOWN = fcDOWN;
this.expl = expl;
//Inicializamos los contadores
hashSize = tam;
numElementos = 0;
}
//En caso contrario...
else
{
//Creamos una tabla cuyo tamaño sea el siguiente nº primo al tamaño pasado por parámetro
int siguientePrimo = nextLargestPrimeNumber(tam);
associativeArray = new HashNode[siguientePrimo];
//Creamos todos los nodos de la tabla vacíos
for(int i = 0; i < siguientePrimo; i++)
{
associativeArray[i] = new HashNode<T>();
}
this.fcUP = fcUP;
this.fcDOWN = fcDOWN;
this.expl = expl;
//Inicializamos los contadores
hashSize = siguientePrimo;
numElementos = 0;
}
// hashSize=isPrime(tam) ? tam : nextLargestPrimeNumber(tam); // Establece un tamaño válido
// associativeArray = (HashNode<T>[]) new HashNode[hashSize]; // Crea el array de HashNode's
// this.fcUP = fcUP;
// this.fcDOWN = fcDOWN;
// this.expl = expl;
// //contadores
// numElementos = 0;
}
/**
* Realiza la funcion de exploración en la tabla hash cuando hay colisión
* Dependiendo del caso, hará exploración lineal, cuadrática,...
*
* @param iter iteración de la colisión
* @param pos posición original (resultado de fHash())
* @return Nueva posición según la exploración actual de la tabla
*/
protected int fExploracion(int iter, int pos) {
//Si la exploración es lineal...
if(expl == LINEAL) return (pos + iter)%hashSize;
//Si la exploracion es doble
else if(expl == DOBLE) return (pos + iter*(previousSmallerPrimeNumber(pos)-(pos % hashSize))) % hashSize;
//Si la exploración es cuadrática...
else return (pos + iter*iter)%hashSize;
//si fuera exploracion doble: añadir otro caso
}
private void setExporacion(byte expl){
//Si se desea cambiar la exploración a lineal o cuadrática
if(expl == LINEAL || expl == CUADRATICA || expl == DOBLE){
//Sólo se permite si está vacía
if(getNumOfElems() == 0) this.expl = expl;
}
//si se añade exploracion doble modificar metodo
}
@Override
public int getNumOfElems() {
return numElementos;
}
@Override
public int getSize() {
return hashSize;
}
protected double getLF(){
return (double) ((numElementos*1.0)/hashSize);
}
@Override
protected boolean reDispersion () {
//Si el factor de carga de la tabla Hash es mayor que el límite superior
if(getLF() >= fcUP)
{
//Guardamos la tabla actual y el tamaño
HashNode<T>[] lastAssociativeArray = associativeArray;
int lastHashSize = hashSize;
//El nuevo tamaño será el nº primo superior más cercano al doble del tamaño actual)
int newHashSize = 0;
newHashSize = nextLargestPrimeNumber(hashSize*2);
//if(isPrime(hashSize*2)) newHashSize = hashSize*2;
//else newHashSize = nextLargestPrimeNumber(hashSize*2);
//Creamos la nueva tabla e inicializamos contadores
associativeArray = new HashNode[newHashSize];
numElementos = 0;
hashSize = newHashSize;
//Creamos todos los nodos de la tabla vacíos
for(int i = 0; i < hashSize; i++)
associativeArray[i] = new HashNode<T>();
//Introducimos en la nueva tabla todos los elementos que había en la vieja, teniendo en cuenta sólo los nodos que tienen estado "LLENO"
for(int i = 0; i < lastHashSize; i++){
if(lastAssociativeArray[i].getEstado() == HashNode.LLENO){
add(lastAssociativeArray[i].getInfo());
}
}
return true;
}
else
{
return false;
}
}
@Override
protected boolean inverseReDispersion() {
//Si el factor de carga de la tabla Hash es menor que el límite inferior
if(getLF() < fcDOWN)
{
//Guardamos la tabla actual y el tamaño
HashNode<T>[] lastAssociativeArray = associativeArray;
int lastHashSize = hashSize;
//Buscamos el nuevo tamaño de la tabla (primo inferior más cercano a la mitad del tamaño actual)
int newHashSize = 0;
//if(isPrime(hashSize/2)) newHashSize = hashSize/2;
//else newHashSize = previousSmallerPrimeNumber(hashSize/2);
newHashSize = previousSmallerPrimeNumber(hashSize/2);
//Creamos la nueva tabla y la asignamos a la referencia. Además, inicializamos los contadores
associativeArray = new HashNode[newHashSize];
numElementos = 0;
hashSize = newHashSize;
//Creamos todos los nodos de la tabla vacíos
for(int i = 0; i < hashSize; i++)
associativeArray[i] = new HashNode<T>();
//Introducimos en la nueva tabla todos los elementos que había en la vieja, teniendo en cuenta sólo los nodos que tienen estado "LLENO"
for(int i = 0; i < lastHashSize; i++){
if(lastAssociativeArray[i].getEstado() == HashNode.LLENO)
add(lastAssociativeArray[i].getInfo());
}
return true;
}
else
{
return false;
}
}
@Override
public boolean add(T elem) {
//si el elem a insertar es nulo
if(elem == null) return false;
if(find(elem) != null) return false;
//Posicion donde se intertará en la tabla
int pos = fHash(elem);
int iter = 1;
//siempre que el estado no sea vacio
while(associativeArray[pos].getEstado() == HashNode.LLENO){
//calculamos una nueva posicion con la funcion de exploracion
//aumentando las iteraciones
pos = fExploracion(iter, fHash(elem));
iter++;
}
//Despues de calcular la posicion nueva, se inserta el elemento
associativeArray[pos].setInfo(elem);
//y se aumenta el numero de elementos
numElementos++;
//APLICAR REDISPERSION SI FUERA NECESARIO { COMPLETAR }
reDispersion();
return true;
}
@Override
public T find(T elem) {
//Comprobamos que el elemento que queremos buscar no es null
if(elem != null)
{
//Obtenemos la posición en la que debería estar en la tabla
int pos = fHash(elem);
int iter = 1;
int counter = 0;
//Mientras no esté en estado "VACIO" dicha posición...
while(counter<=getSize() && pos>=0 && associativeArray[pos].getEstado() != HashNode.VACIO){
//Si la posición está en estado "LLENO" y el elemento de dicha posición es el que buscamos, devolvemos dicho elemento
if(associativeArray[pos].getEstado() == HashNode.LLENO){
if(associativeArray[pos].getInfo().equals(elem)){
return associativeArray[pos].getInfo();
}
}
//En caso contrario, volvemos a calcular una nueva posición con la función de exploración aumentando las iteracciones
pos = fExploracion(iter, fHash(elem));
iter++;
counter++;
}
return null;
}
else
{
return null;
}
}
@Override
public boolean remove(T elem) {
if(find(elem) == null) return false;
//Comprobamos que el elemento que queremos buscar no es null
if(elem != null){
//Obtenemos la posición en la que debería estar en la tabla
int pos = fHash(elem);
int iter = 1;
//Mientras no esté en estado "VACIO" dicha posición...
while(associativeArray[pos].getEstado() != HashNode.VACIO){
//Si la posición está en estado "LLENO" y el elemento de dicha posición es el que queremos borrar...
if(associativeArray[pos].getEstado() == HashNode.LLENO){
if(associativeArray[pos].getInfo().equals(elem)){
//Ponemos el estado dicha posición a "BORRADO" y disminuimos el número de elementos
associativeArray[pos].borrar();
numElementos--;
//Si todavía hay elementos en la tabla, aplicamos redispersión inversa si es posible
if(numElementos != 0) inverseReDispersion();
return true;
}
}
//En caso contrario, volvemos a calcular una nueva posición con la función de exploración aumentando las iteracciones
pos = fExploracion(iter, fHash(elem));
iter++;
}
return false;
}
else{
return false;
}
}
@Override
public String toString (){
String result = "";
for(int i=0; i<associativeArray.length; i++){
result += associativeArray[i].toString();
}
return result;
}
}package tablasHash;
import static org.junit.Assert.*;
import org.junit.Test;
public class ClosedHashTableTest {
@Test
/**
* Método para comprobar el correcto funcionamiento del método ADD
* sin tener en cuenta las redispersiones y las colisiones
*/
public void testADDwithoutRedispersionAndColisions() {
ClosedHashTable<Integer> tabla = new ClosedHashTable<Integer>(8, 0.5, 0.16, (byte) 0);
assertEquals(11, tabla.getSize());
assertEquals(0, tabla.getNumOfElems());
assertTrue(tabla.add(4));
assertEquals(1, tabla.getNumOfElems());
assertTrue(tabla.add(0));
assertEquals(2, tabla.getNumOfElems());
}
@Test
/**
* Método para comprobar el correcto funcionamiento del método ADD
* teniendo en cuenta colisiones pero sin tener en cuenta redispersiones
*/
public void testADDwithoutRedispersion(){
//Prueba positiva lineal
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(7, 0.5, 0.16, (byte) 0);
assertEquals(7, tabla.getSize());
assertEquals(0, tabla.getNumOfElems());
assertTrue(tabla.add(7));
assertEquals(1, tabla.getNumOfElems());
assertTrue(tabla.add(14));
assertEquals(2, tabla.getNumOfElems());
assertTrue(tabla.add(21));
assertEquals(3, tabla.getNumOfElems());
assertTrue(tabla.add(28));
assertEquals(4, tabla.getNumOfElems());
//Prueba positiva cuadrática
ClosedHashTable<Integer> tabla2 = new ClosedHashTable<>(7, 0.5, 0.16, (byte) 1);
assertEquals(7, tabla2.getSize());
assertEquals(0, tabla2.getNumOfElems());
assertTrue(tabla2.add(7));
assertEquals(1, tabla2.getNumOfElems());
assertTrue(tabla2.add(14));
assertEquals(2, tabla2.getNumOfElems());
assertTrue(tabla2.add(21));
assertEquals(3, tabla2.getNumOfElems());
assertTrue(tabla2.add(28));
assertEquals(4, tabla2.getNumOfElems());
}
@Test
/**
* Método que se limita a comprobar que el método ADD añade nodos correctamente
*/
public void testADD(){
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(3, 0.5, 0.16, (byte) 1);
assertEquals(3, tabla.getSize());
assertEquals(0, tabla.getNumOfElems());
assertTrue(tabla.add(3));
assertEquals(1, tabla.getNumOfElems());
assertEquals(3, tabla.getSize());
assertTrue(tabla.add(6));
assertEquals(2, tabla.getNumOfElems());
assertEquals(7, tabla.getSize());
}
@Test
/**
* Método para comprobar que el método REMOVE funciona correctamente
*/
public void testRemove(){
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(11, 0.5, 0.16, (byte) 1);
assertEquals(11, tabla.getSize());
assertEquals(0, tabla.getNumOfElems());
tabla.add(0);
tabla.add(11);
tabla.add(22);
assertEquals(11, tabla.getSize());
assertEquals(3, tabla.getNumOfElems());
assertTrue(tabla.remove(11));
assertEquals(2, tabla.getNumOfElems());
assertEquals(11, tabla.getSize());
assertTrue(tabla.remove(22));
assertEquals(1, tabla.getNumOfElems());
assertEquals(3, tabla.getSize());
assertFalse(tabla.remove(null));
assertFalse(tabla.remove(80));
}
@Test
/**
* Método para comprobar que el método FIND funciona correctamente
*/
public void testFind(){
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(11, 0.5, 0.16, (byte) 1);
tabla.add(0);
tabla.add(11);
tabla.add(22);
assertEquals(0, tabla.find(0), 0.0);
tabla.remove(0);
assertNull(tabla.find(0));
}
@Test
/**
* Método para comprobar que la clase funciona correctamente con claves de tipo String
*/
public void testStringKeys(){
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(5, 0.5, 0.16, (byte) 1);
for(int i=0; i<5; i++){
tabla.add(i);
}
//System.out.println(tabla);
}
@Test
public void testLF(){
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(5, 0.5, 0.16, (byte) 0);
//System.err.println(tabla);
tabla.add(0);
//System.err.println(tabla);
tabla.add(1);
assertEquals(11, tabla.nextLargestPrimeNumber(tabla.getSize()*2));
//System.err.println(tabla);
tabla.add(2);
//System.err.println(tabla);
tabla.add(3);
assertEquals(5, tabla.getSize()/2);
//System.err.println(tabla);
tabla.remove(3);
//System.err.println(tabla);
tabla.remove(2);
//System.err.println(tabla);
tabla.remove(1);
//System.err.println(tabla);
}
@Test
public void checkRedispersions(){
ClosedHashTable<Integer> tabla = new ClosedHashTable<>(11, 0.5, 0.16, (byte) 0);
for(int i=0; i<10000; i++){
int tam = tabla.getSize();
//System.err.println("EL LF de " + i + " es: " + tabla.getLF());
//System.err.println("El tamaño de " + i + "es: " + tabla.getSize());
tabla.add(i);
if(tabla.getSize() == tabla.nextLargestPrimeNumber(tam*2)){
System.err.println("####################");
System.err.println("Se produjo redispersion al añadir el elemento: " + i);
System.err.println("####################");
}
}
//System.err.println(tabla.getLF());
//System.err.println(tabla);
System.err.println("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@");
//System.err.println();
checkInverseRedispersionWhileRemoving(tabla);
}
private void checkInverseRedispersionWhileRemoving(ClosedHashTable<Integer> tabla){
for(int i=0; i<10000; i++){
int tam = tabla.getSize();
tabla.remove(i);
if(tabla.getSize() == tabla.previousSmallerPrimeNumber(tam/2)){
System.err.println("####################");
System.err.println("Se produjo redispersion inversa al eliminar el elemento: " + i);
System.err.println("####################");
}
}
//System.err.println(tabla.getLF());
System.err.println(tabla);
}
//IMPLEMENTAR TAN BIEN PRUEBAS PARA PROBAR CON EL TOSTRING()
}package tablasHash;
import static org.junit.Assert.*;
import org.junit.Test;
public class ClosedHashTableTest2 {
@Test
public void testAdd() {
ClosedHashTable<Integer> t = new ClosedHashTable<Integer>(10, 0.5, 0.16, (byte) 1);
assertTrue(t.add(1));
assertFalse(t.add(1));
assertTrue(t.add(2));
for ( int i = 3; i < 103; i++){
assertTrue(t.add(i));
}
assertNotNull(t.find(2));
}
@Test
public void testRemove(){
ClosedHashTable<Integer> t = new ClosedHashTable<Integer>(10, 0.5, 0.16, (byte) 1);
assertFalse(t.remove(2));
assertTrue(t.add(3));
assertFalse(t.remove(2));
assertTrue(t.remove(3));
for (int i = 0; i < 10; i++){
assertTrue(t.add(i));
assertTrue(t.remove(i));
assertFalse(t.remove(null));
assertFalse(t.remove(i));
}
}
@Test
public void testSeminario(){
ClosedHashTable<Integer> t = new ClosedHashTable<Integer>(5, 0.5, 0.16, (byte) 0);
t.add(4);
t.add(13);
t.add(24);
t.add(3);
t.remove(24);
t.add(24);
t.add(5);
t.remove(3);
assertEquals("Hash 1: ",t.toString(),"{_E_}{_E_}{24}{13}{4}{_D_}{5}{_E_}{_E_}{_E_}{_E_}");
}
@Test
public void testRedispersion(){
ClosedHashTable<Integer> t = new ClosedHashTable<Integer>(5, 0.5, 0.16, (byte) 0);
t.add(1);
t.add(3);
t.add(5);
assertEquals("Red1", "{_E_}{1}{_E_}{3}{_E_}{5}{_E_}{_E_}{_E_}{_E_}{_E_}", t.toString());
t = new ClosedHashTable<Integer>(17, 0.5, 0.16, (byte)1);
for (int i = 0; i <8; i ++){
t.add(i);
}
assertEquals("Red2", "{0}{1}{2}{3}{4}{5}{6}{7}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}", t.toString());
t.add(8);
assertEquals("Red3", "{0}{1}{2}{3}{4}{5}{6}{7}{8}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}", t.toString());
t.remove(8);
t.remove(7);
t.remove(6);
t.remove(5);
assertEquals("Red4", "{0}{1}{2}{3}{4}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}{_E_}", t.toString());
}
@Test
public void testFind(){
ClosedHashTable<Integer> t = new ClosedHashTable<Integer>(7, 0.5, 0.16, (byte) 0);
t.add(3);
assertNotNull(t.find(3));
assertEquals("Find1", (Integer)3, t.find(3));
assertNull(t.find(4));
assertNull(t.find(null));
t.add(2);
t.add(1);
assertEquals("Find2", (Integer)1, t.find(1));
t.add(4);
assertEquals("Find3", (Integer)4, t.find(4));
t.remove(2);
assertNull(t.find(2));
ClosedHashTable<String> tH= new ClosedHashTable<String>(7, 0.5, 0.16, (byte) 0);
tH.add("A");
assertNotNull(tH.find("A"));
assertEquals("Find1", "A", tH.find("A"));
assertNull(tH.find("B"));
assertNull(tH.find(null));
tH.add("B");
tH.add("C");
assertEquals("Find2", "C", tH.find("C"));
tH.add("J");
assertEquals("Find3", "J", tH.find("J"));
tH.remove("B");
assertNull(tH.find("B"));
}
}