Java Fixed Hashtable (tabla hash de longitud fija en Java)
Recientemente he tenido la necesidad de implementar una tabla hash de longitud fija (es decir, cada elemento de la tabla es una lista enlazada con los distintos valores cuya clave tiene la misma hash) en lenguaje Java por motivos que no vienen al caso 😛 . Busqué (escasamente, todo hay que decirlo) una que se adaptase a mis necesidades en Google pero entre mi pereza a la hora de buscar y no tener clara la licencia de las que encontré más o menos a mi gusto decidí partir de cero. Así que aquí dejo mi versión con licencia GPL. Consta de dos clases. La primera de ellas representa cada elemento contenido dentro de cada casilla de la tabla:
/** * Hashtable element (list of nodes with key and value) * @author Diego Toharia deigote ALGARROBA gmail PUNTO com * Licence GNU GPL */ public class HashtableElement { /** * Hashtable table element nodes * @author Diego Toharia deigote ALGARROBA gmail PUNTO com */ public class Hashnode { // Key and value public Object value, key; // Links to previous and next nodes public Hashnode next, prev; // Constructor public Hashnode(Object key, Object value, Hashnode next) { this.key = key; this.value = value; this.next = next; // New nodes are always in list first position if (this.next != null) this.next.prev = this; this.prev = null; } // To string public String toString() { return key + " . " + value; } // Clone public Hashnode clone() { return new Hashnode(key, value, next); } } // The first element of the linked list public Hashnode first; // Constructors public HashtableElement() { first = null; } public HashtableElement(Hashnode first) { this.first = first; } // Add a node public Object add(Object key, Object value) { // Try to find the key for (Hashnode it = first; it != null; it = it.next) if (it.key.equals(key)) { Object ret = it.value; it.value = value; return ret; } // If not found, add a new node at list start and return null first = new Hashnode(key, value, first); return null; } // Remove a node public Object remove(Object key) { // Try to find the key for (Hashnode it = first; it != null; it = it.next) if (it.key.equals(key)) { Object ret = it.value; if (it.prev != null) it.prev.next = it.next; else first = it.next; if (it.next != null) it.next.prev = it.prev; return ret; } // If not found, return null return null; } // Get a node public Object get(Object key) { // Try to find the key for (Hashnode it = first; it != null; it = it.next) if (it.key.equals(key)) return it.value; return null; } // Clone operation public HashtableElement clone() { // If there is no list, return an empty table element if (first == null) return new HashtableElement(); Hashnode newListIterator = null, oldListIterator = first; // Actual list iterator must be at the end while (oldListIterator.next != null) oldListIterator = oldListIterator.next; // Create a new list while (oldListIterator != null) { newListIterator = new Hashnode(oldListIterator.key, oldListIterator.value, newListIterator); oldListIterator = oldListIterator.prev; } return new HashtableElement(newListIterator); } // To string public String toString() { Hashnode iterator = first; String ret = ""; while (iterator != null) { ret += iterator.toString(); iterator = iterator.next; ret += " || "; } return ret; } }
La segunda representa a la tabla en sí:
import java.io.PrintStream; /** * Fixed-sized linked list based hashtable * @author Diego Toharia deigote ALGARROBA gmail PUNTO com * Licence GNU GPL */ class HashtableFixed { // Table size private int size; // Array of node lists private HashtableElement[] table; // Objects in the table private int length; // Lock for synchronized if required private ReentrantLock lock; /** * Constructor (table size and if the table is coarse-grained synchronized) */ public HashtableFixedCoarse(int size, boolean sync) { this.size = size; table = new HashtableElement[size]; for (int i = 0; i < size; i++) table[i] = new HashtableElement(); length = 0; if (sync) lock = new ReentrantLock(); else lock = null; } /** * Gets the table size * @return */ public int size() { return size; } /** * Gets the number of elements in the table * @return */ public int dataSize() { return length; } /** * Get an element using its key (null if element doesn't exist) * @param key * @return */ public Object get(Object key) { Object ret = null; if (lock != null) lock.lock(); // Null key or value is not allowed if (key != null) { // Get the key hash code int index = Math.abs(key.hashCode()) % size; // Get the node from the table element with same hash ret = table[index].get(key); } if (lock != null) lock.unlock(); return ret; } /** * Sets the value for the given key * @param key The key (can't be null) * @param value The value (can't be null) * @return The last value corresponding to this key */ public Object put(Object key, Object value) { Object ret = null; if (lock != null) lock.lock(); // Null key or value are not allowed if (key != null && value != null) { // Get the key hash code int index = Math.abs(key.hashCode()) % size; // Put the node in the table element with same hash ret = table[index].add(key, value); // If it's a new key, increment number of elements if (ret == null) length++; } if (lock != null) lock.unlock(); return ret; } /** * Remove the given key entry * @param key * @return The key value before remove it */ public Object remove(Object key) { Object ret = null; if (lock != null) lock.lock(); // Null key is not allowed if (key != null) { // Get the key hash code int index = Math.abs(key.hashCode()) % size; // Remove the node in the table element with same hash ret = table[index].remove(key); } // If the key was found, decrement number of elements length--; if (lock != null) lock.unlock(); return ret; } /** * Clear the table */ public void clear() { if (lock != null) lock.lock(); for (int i=0; i < size; i++) table[i].first = null; if (lock != null) lock.unlock(); } public void print(PrintStream out) { if (lock != null) lock.lock(); String msg = ""; for (int i = 0; i < table.length; i++) msg += i + ": " + table[i].toString() + "\n"; out.println(msg); if (lock != null) lock.unlock(); } /** * Test program * @param args */ public static void main (String args[]) { HashtableFixedCoarse t = new HashtableFixedCoarse(10, true); final int NUMS = 20; long t1 = System.currentTimeMillis(), t2 = 0; for(int i = 0; i < NUMS; i++) System.out.println("Put " + -i + "." + i + " (replace " + t.put(new Integer(-i), new Integer(i)) + ")"); System.out.println("\nlength " + t.dataSize()); t.print(System.out); for(int i = 0; i < NUMS; i += 3) System.out.println("Removed " + t.remove(new Integer(-i))); System.out.println("\nlength " + t.dataSize()); t.print(System.out); for(int i = 0; i < NUMS; i += 2) System.out.println("Put " + -i + "." + (i*10) + " (replace " + t.put(new Integer(-i), new Integer(i*10)) + ")"); System.out.println("\nlength " + t.dataSize()); t.print(System.out); for(int i = 0; i < NUMS; i += 2) System.out.println("Removed " + t.remove(new Integer(-i))); System.out.println("\nlength " + t.dataSize()); t.print(System.out); t2 = System.currentTimeMillis(); System.out.println(t2-t1); } }
Sólo un par de cosas a tener en cuenta: que mi objetivo no ha sido buscar la máxima eficiencia posible, así que puede que haya cosas mejorables (aparte de posibles bugs, que creo que no), y que el sincronismo es de grano grueso y por lo tanto se usa un único cerrojo que engloba todo el código de cada método (en caso de usar sincronismo claro) en lugar de cerrojos de lectura-escritura con exclusión mútua lo más corta posible.
Espero que a alguien le sea de utilidad o… algo.
Parecidos razonables
-
Java: cambiar el valor de un atributo privado de un objeto
May 29, 2007
32 -
Grails – generic methods for equals and hashCode calculation
December 27, 2012
3 -
Bash – find directories of certain sizes
January 11, 2013
1 -
Servicios web (2): Desplegando un servicio JWS
June 12, 2006
4 -
Groovy – Simplest way of resolving a nested property
July 24, 2013
4
Una cosita. Bueno, dos.
¿Porqué necesitas implementar tu propia tabla Hash teniendo las proporcionadas por Java? Desconozco si la implementación de Java es una tabla hash enlazada o no (ahora que el código es GPL se puede saber), pero me gustaría saber el que te llevó a descartar su implementación.
Y lo segundo es que clone() no debería llamar a constructores (lo dice la documentación, pero nadie le hace caso), en How to avoid traps and correctly override methods from java.lang.Object te explican como se debe hacer (enlazo a la segunda página, pero el artículo entero es de lectura obligada).
Ale, a reimplementar.
Jeje basta para decir que algo no viene al caso para que cobre interés 🙄 necesitaba una tabla sencilla (la de java.util no lo es) de longitud fija (la de java.util no lo es) para tener una complejidad definida en la operación de añadir un elemento a la tabla,y cuya sincronización fuese opcional manteniendo el resto de la implementación igual (en la de java.util no lo es). Además necesitaba acceso al código, y aunque el de la versión de java.util está disponible con el kit de desarrollo, no sé ni me apetecía investigar acerca de su licencia actual.
El objetivo ya cumplido era posteriormente hacer una versión de dicha tabla hash que en vez de cerrojos use transacciones manteniendo el resto de la implementación igual para hacer microbencharks de la biblioteca de transacciones en la que estoy trabajando. Por eso necesitaba sencillez y control del código.
Sobre lo del clone, realmente he añadido dicha función porque necesitaba un clonado para mi sistema transaccional, el nombre clone es casualidad 😛 pero gracias a esa casualidad (y a tu tradicional infinita sapiencia 🙂 ) he descubierto cómo usar el clone para que las copias se hagan de manera algo más automática (la otra opción es serializar, pero es costosa, aunque la uso en caso de que los objetos transaccionales no soporten clonación). Lo probaré a ver, gracias 💡 .
❓ ❗ 😛 😉 😉 😥 😆 😐 😐 😈 😎 💡
Muy elocuente, si señora 🙂
Mi viejo no invente de nuevo la rueda.
Jolín, hasta virtualmente se me nota que ya no soy ningún jovenzuelo 😥
Si… Palabras como “elocuente” delatan que no has hecho la ESO.
Siento decepcionarte, pero de hecho, es lo que estudié (bueno, al menos asistí a
algunaclase 😀 ) después de la EGB (es decir, que sólo hice 3º y 4º de ESO en lugar de todo el ciclo.. quizá sea eso – ¿lo pillas? – 😛 )Bueno.. pues eso!
Ueee!! El blog del humooooor!!!1once
Pingback: Hash - La Comunidad DragonJAR
puedes crear una tabla hash con los métodos y funciones put, remove, containsKey, containsValue, get, values, clear y size????
porque necesito una implementación de una tabla hash con esos métodos, si puedes te lo re agradeceré.
Si, si que puedo. Así que de nada, supongo :-).
Deigote mi correo es corajejd@gmail.com, te lo paso a ver si me podés un código de tabla hash con los métodos y funciones:
put, remove, containsKey, containsValue, get, values, clear y size, además puedes agregarle el uso de los generics ??
si puedes te lo re agradeceré.
Buenas. Pensaba que estaba claro pero el anterior comentario era irónico. Es decir, puedo, pero no lo voy a hacer. Saludos.