El blog de Deigote

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 icon_razz.gif . 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.