de.spieleck.util
Class SpeedHashtable

java.lang.Object
  |
  +--java.util.Dictionary
        |
        +--de.spieleck.util.SpeedHashtable

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

StringKeyHashtable

public class SpeedHashtable

extends java.util.Dictionary

implements java.io.Serializable

A more efficient version of java.util.Hashtable.

This is faster for the following reasons:

• It is not synchronized.
• It uses its own algorithm.
• Methods are finalized and can get better optimized by the JVM.
• It only performs allocation when the hash table is resized.

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).

Note within larger projekts this class might have secondary benefits since it doesn't allocate objects unlike the sun implementation of Hashtable and HashMap.

See Also:

Serialized Form

Field Summary

protected int	capacity The current capacity of the array (half of table.length).
protected int	capacity1 capacity - 1.
protected int	lastGetIndex This data allows nice threadunsafe optimizations.
protected java.lang.Object	lastKey This data allows nice threadunsafe optimizations.
protected int	used The actually number of used entries in the array.

Constructor Summary

SpeedHashtable()
Creates a hash table with standard initial capacity.

SpeedHashtable(double loadFactor)
Create hashtable with non standard load factor

SpeedHashtable(int n)
Creates a hash table with the specified initial capacity.

SpeedHashtable(int n, double loadFactor)
Create hashtable with non standard load factor and special size

Method Summary

void	append(SpeedHashtable tab2) Append contents from another SpeedHashtable.
void	clear() Removes all objects from the hash table, so that the hash table becomes empty.
boolean	containsKey(java.lang.Object key) This API is obviously useless :-)
java.util.Enumeration	elements()
java.lang.Object	get(java.lang.Object key)
java.lang.Object[]	getElementSnap() Snapshot hashtable elements.
java.lang.Object[]	getKeySnap() Snapshot hashtable keys.
protected int	hashCode(java.lang.Object key) This is a customization API to replace hashCode() by more efficient methods.
boolean	isEmpty()
java.util.Enumeration	keys()
java.lang.Object	put(java.lang.Object key, java.lang.Object value)
java.lang.Object	remove(java.lang.Object key) Removes the object with the specified key from the table.
java.lang.Object	replaceLastGet(java.lang.Object value) Slightly dirty solution to the double hash and search effect in the (very common sequence): SpeedHashtable fh = ...
int	size()
protected java.lang.Object	unsafePut(java.lang.Object key, java.lang.Object value) Internal Version of the putter, not as fail safe...

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

capacity

protected int capacity

The current capacity of the array (half of table.length). This implementation requires capacity to be a power of 2.

capacity1

protected int capacity1

capacity - 1.

used

protected int used

The actually number of used entries in the array.

lastGetIndex

protected int lastGetIndex

This data allows nice threadunsafe optimizations.

lastKey

protected java.lang.Object lastKey

This data allows nice threadunsafe optimizations.

Constructor Detail

SpeedHashtable

public SpeedHashtable()

Creates a hash table with standard initial capacity.

SpeedHashtable

public SpeedHashtable(int n)

Creates a hash table with the specified initial capacity.

SpeedHashtable

public SpeedHashtable(double loadFactor)

Create hashtable with non standard load factor

SpeedHashtable

public SpeedHashtable(int n,
                      double loadFactor)

Create hashtable with non standard load factor and special size

Method Detail

size

public final int size()

Overrides:

size in class java.util.Dictionary

isEmpty

public final boolean isEmpty()

Overrides:

isEmpty in class java.util.Dictionary

hashCode

protected int hashCode(java.lang.Object key)

This is a customization API to replace hashCode() by more efficient methods.

containsKey

public final boolean containsKey(java.lang.Object key)

This API is obviously useless :-)

get

public java.lang.Object get(java.lang.Object key)

Overrides:

get in class java.util.Dictionary

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)

Overrides:

put in class java.util.Dictionary

replaceLastGet

public java.lang.Object replaceLastGet(java.lang.Object value)

Slightly dirty solution to the double hash and search effect in the (very common sequence):

 SpeedHashtable fh = ...
 Object something = fh.get(key);
 if ( something ... )
 {
   Object somethingdifferent = ...
   fh.put(key, somethingdifferent);
 }
 

This can now be written more efficient as

 Object something = fh.get(key);
 if ( something ... )
 {
   Object somethingdifferent = ...
   fh.replaceLastGet(somethingdifferent);
 }
 

Caution: Due to rehashing can only be called once per get()! This is not at all a thread safe mechanism

unsafePut

protected final java.lang.Object unsafePut(java.lang.Object key,
                                           java.lang.Object value)

Internal Version of the putter, not as fail safe...

append

public void append(SpeedHashtable tab2)

Append contents from another SpeedHashtable.

XXX Could be a bit more optimized and avoid the tab2.get() ...

remove

public java.lang.Object remove(java.lang.Object 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.

Overrides:

remove in class java.util.Dictionary

getKeySnap

public java.lang.Object[] getKeySnap()

Snapshot hashtable keys.

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.

getElementSnap

public java.lang.Object[] getElementSnap()

Snapshot hashtable elements.

See Also:

getKeySnap()

clear

public void clear()

Removes all objects from the hash table, so that the hash table becomes empty.

keys

public java.util.Enumeration keys()

Overrides:

keys in class java.util.Dictionary

elements

public java.util.Enumeration elements()

Overrides:

elements in class java.util.Dictionary