| SpeedHashtable.java |
/**
* (c) 2002 Spieleck
*/
package de.spieleck.util;
import java.io.Serializable;
import java.util.Dictionary;
import java.util.Enumeration;
/**
* A more efficient version of <code>java.util.Hashtable</code>.
* <P>
* This is faster for the following reasons: <UL>
* <LI>It is not synchronized.
* <LI>It uses its own algorithm.
* <LI>Methods are finalized and can get better optimized by the JVM.
* <LI>It only performs allocation when the hash table is resized.
* </UL>
* The original source of this has been found in James Clark XP
* SAXParser, but it has been improved and is even faster. This is
* achieved by better use of given arrays (by different load factor and
* different usedLimit calculation).
* <P>
* <B>Note</B> within larger projekts this class might have secondary
* benefits since it doesn't allocate objects unlike the
* sun implementation of Hashtable and HashMap.
* <P>
* @author fsn
* @version 1
*/
public class SpeedHashtable
extends Dictionary
implements Serializable
{
private static final int INIT_SIZE = 5;
private final static int HASHSTEP = 5;
/**
* The array of entries and keys.
* The first half of table contains the keys, the second half the values.
* The value for a key at index i is at index i + capacity
*/
private Object[] table;
/**
* The current capacity of the array (half of table.length).
* This implementation requires capacity to be a power of 2.
*/
protected int capacity;
/** capacity - 1. */
protected int capacity1;
/** The actually number of used entries in the array. */
protected int used;
/** The load factor allowed by this table. */
private double loadFactor;
/** The limit where the table is resized (approx used * loadFactor). */
private int usedLimit;
/**
* Creates a hash table with standard initial capacity.
*/
public SpeedHashtable()
{
this(INIT_SIZE, 0.75);
}
/**
* Creates a hash table with the specified initial capacity.
*/
public SpeedHashtable(int n)
{
this(n, 0.75);
}
/**
* Create hashtable with non standard load factor
*/
public SpeedHashtable(double loadFactor)
{
this(INIT_SIZE, loadFactor);
}
/**
* Create hashtable with non standard load factor and special size
*/
public SpeedHashtable(int n, double loadFactor)
{
this.loadFactor = loadFactor;
n = (int)((n + 1) / loadFactor);
int h = 4;
while (h < n)
h += h;
used = 0;
internalInit(h);
}
/** Init the internal structures. */
private final void internalInit(int size)
{
capacity = size;
capacity1 = size - 1;
table = new Object[size << 1];
usedLimit = (int)(size * loadFactor);
}
public final int size()
{
return used;
}
public final boolean isEmpty()
{
return used == 0;
}
/**
* Exploration strategy for the heap
*/
private final int nextIndex(int i)
{
return i < HASHSTEP
? capacity + i - HASHSTEP
: i - HASHSTEP;
}
/**
* First hash index.
* <P>
* XXX: Note that if we could delay the & (capacity-1), we could
* use the remaining bits of the hashCode for secondary of free
* spaces and could avoid that all elements travel along the same
* way. But this would mean rather inconvenient changes in the whole
* class and is proably outweight by the fact that we strictly leave
* 25% of the spaces empty anyway.
*/
private final int firstIndex(Object key)
{
return hashCode(key) & capacity1;
}
/**
* This is a customization API to replace hashCode()
* by more efficient methods.
*/
protected int hashCode(Object key)
{
return key.hashCode();
}
/** This API is obviously useless :-) */
public final boolean containsKey(Object key)
{
return get(key) != null;
}
/** This data allows nice threadunsafe optimizations. */
protected int lastGetIndex;
/** This data allows nice threadunsafe optimizations. */
protected Object lastKey;
public Object get(Object key)
{
if (key != null)
{
lastKey = key;
int i = firstIndex(key);
for (; table[i] != null; i = nextIndex(i))
if (table[i].equals(key))
{
lastGetIndex = i;
return table[i | capacity];
}
lastGetIndex = i;
}
return null;
}
public Object put(Object key, Object value)
{
if (value == null || key == null)
throw new NullPointerException();
return unsafePut(key, value);
}
/**
* Slightly dirty solution to the double hash and search effect
* in the (very common sequence):
* <PRE>
* SpeedHashtable fh = ...
* Object something = fh.get(key);
* if ( something ... )
* {
* Object somethingdifferent = ...
* fh.put(key, somethingdifferent);
* }
* </PRE>
* This can now be written more efficient as
* <PRE>
* Object something = fh.get(key);
* if ( something ... )
* {
* Object somethingdifferent = ...
* fh.replaceLastGet(somethingdifferent);
* }
* </PRE>
* <B>Caution:</B> Due to rehashing can only be called once per get()!
* This is not at all a thread safe mechanism
*/
public Object replaceLastGet(Object value)
{
if (value == null)
throw new NullPointerException();
int h = lastGetIndex | capacity;
Object old = table[h];
table[h] = value;
// New entries need some bookkeeping
if (old == null)
{
table[lastGetIndex] = lastKey;
if (++used > usedLimit)
rehash();
}
return old;
}
/**
* Internal Version of the putter, not as fail safe...
*/
protected final Object unsafePut(Object key, Object value)
{
int h;
for (h = firstIndex(key); table[h] != null; h = nextIndex(h))
if (key.equals(table[h]))
{
h |= capacity;
Object old = table[h];
table[h] = value;
return old;
}
// Not the below could be programmed shorter but slightly slower
// if we first inserted and later on rehashed!
if (++used > usedLimit)
{
rehash();
for (h = firstIndex(key);
table[h] != null;
h = nextIndex(h))
;
}
table[h] = key;
table[h | capacity] = value;
return null;
}
/**
* Rehash the table to a larger size
*/
private final void rehash()
{
int j;
int oldCap = capacity;
Object[] oTable = table;
internalInit(capacity * 2);
for (int i = oldCap; i > 0;)
{
if (oTable[--i] != null)
{
for (j = firstIndex(oTable[i]);
table[j] != null;
j = nextIndex(j))
;
table[j] = oTable[i];
table[j | capacity] = oTable[i | oldCap];
}
}
}
/**
* Append contents from another SpeedHashtable.
* <P>XXX Could be a bit more optimized and avoid the tab2.get() ...
*/
public void append(SpeedHashtable tab2)
{
Enumeration en = tab2.keys();
while (en.hasMoreElements())
{
Object key = en.nextElement();
unsafePut(key, tab2.get(key));
}
}
/**
* Removes the object with the specified key from the table.
* Returns the object removed or null if there was no such object
* in the table.
*/
public Object remove(Object key)
{
if (used > 0)
{
for (int i = firstIndex(key);
table[i] != null;
i = nextIndex(i))
if (table[i].equals(key))
{
Object obj = table[i];
do
{
table[i] = null;
table[i | capacity] = null;
int j = i;
int r;
do
{
i = nextIndex(i);
if (table[i] == null)
break;
r = firstIndex(table[i]);
}
while ((i <= r && r < j) || (r < j && j < i)
|| (j < i && i <= r));
table[j] = table[i];
table[j | capacity] = table[i | capacity];
}
while (table[i] != null);
--used;
return obj;
}
}
return null;
}
/**
* Snapshot hashtable keys.
* <P>Looks like the fastest way to get fairly safe access to
* many keys in a fast changing SpeedHashtable.
* Still not synchronized according to SpeedHashtable principle,
* but obviously meaningless when certain changes happen in
* background.
*/
public Object[] getKeySnap()
{
// Internal snapshot to decrease likelihood of problems when
// container gets restructured...
Object[] tab = table;
int used = this.used;
Object[] res = new Object[used];
for (int i = capacity, j = 0; j < used && i > 0;)
if (tab[--i] != null)
res[j++] = tab[i];
return res;
}
/**
* Snapshot hashtable elements.
* @see #getKeySnap()
*/
public Object[] getElementSnap()
{
Object[] tab = table;
int used = this.used;
Object[] res = new Object[used];
for (int i = capacity, j = 0; j < used && i < table.length;)
if (tab[i] != null)
res[j++] = tab[i++];
return res;
}
/**
* Removes all objects from the hash table, so that the hash table
* becomes empty.
*/
public void clear()
{
int i = capacity;
// Note table[i | capacity ] = null is not needed for the Hashtable
// to work, but for the GC to realize the object can be freed!!!!
while (--i >= 0)
table[i] = table[i | capacity] = null;
used = 0;
}
public Enumeration keys()
{
return new Enumerator(table, 0);
}
public Enumeration elements()
{
return new Enumerator(table, capacity);
}
private static class Enumerator
implements Enumeration
{
private final Object[] table;
private final int offset;
private int i;
Enumerator(Object[] table, int offset)
{
this.table = table;
this.offset = offset;
if (table == null)
i = -1;
else
{
i = (table.length >> 1);
skip();
}
}
private final void skip()
{
while (--i >= 0 && table[i] == null)
;
}
public boolean hasMoreElements()
{
return i >= 0;
}
public Object nextElement()
{
if (i < 0)
throw new java.util.NoSuchElementException();
Object result = table[i + offset];
skip();
return result;
}
}
}
| SpeedHashtable.java |