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.