de.enough.polish.util
Class OAIdentityHashMap

java.lang.Object
  de.enough.polish.util.OAIdentityHashMap

All Implemented Interfaces:

Map

public class OAIdentityHashMap
extends Object
implements Map

Provides the functionality of the J2SE java.util.HashMap for J2ME applications that uses Open Addressing for resolving collision.

WARNING 1: This Open Addressing HashMap does not support remove() operations! A RuntimeException will be thrown when remove is used. Clearing of the entire map is supported.

WARNING 2: Keys and values are compared using their references (==), so you need to ensure that you use only the original keys for retrieval of the stored values.

This implementation uses Open Addressing for resolving collision that occur when several (different) keys share the same hash code. In that case the key-value pair will be stored in the next free slot. There are different probing strategies for finding the next free slot:

• linear probing
  The next slot is used (meaning the index is increased by one until a free slot is found). This is a very simple and therefore fast operation, but is not good when there are many keys that share the same hash code (clustering). This is the default strategy and can be selecting using the AOHashMap.PROBING_LINEAR constant.
• quadratic probing
  in which the interval between probes increases linearly (hence, the indices are described by a quadratic function). In this strategy the interval start with 3 is increased by one in each step: interval = 3 + step. You can select this strategy by using the ASHashMap.PROBING_QUADRATIC constanct.
• double hashing
  in which the interval between probes is fixed for each record but is computed by another hash function. This is the most expensive strategy but has the advantage that there is very little clustering. You can select this strategy by using the ASHashMap.PROBING_DOUBLE_HASHING constanct.

In contrast to the java.util.Hashtable (which is available on J2ME platforms), this implementation is not synchronized and faster.

The default capacity is 17 for reducing possible collision. Feel free to use another prime number instead (like 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113). When you use a power of 2 for the initial capacity (like 16, 32, 64 and so on), no modulo operations need to be done, which might be beneficial depending on the hash codes of your keys.

Copyright (c) Enough Software 2005 - 2009

 history
        30-Nov-2005 - rob creation
 

Author:

Robert Virkus, j2mepolish@enough.de

Field Summary

static int	DEFAULT_INITIAL_CAPACITY The default capacity is 17
static int	DEFAULT_LOAD_FACTOR The default load factor is 60, so the HashMap is increased when 60% of it's capacity is reached
static int	PROBING_DOUBLE_HASHING When this probing is used, the interval between probes is fixed but calculated using another hash function.
static int	PROBING_LINEAR When this probing is used, the next free slot will be used for keys that have the same hash code as a previously inserted item.
static int	PROBING_QUADRACTIC When this probing is used, the interval between probes increases linearly.

Constructor Summary

OAIdentityHashMap()
Creates a new HashMap with the default initial capacity 17, a load factor of 60% and linear probing.

OAIdentityHashMap(int initialCapacity)
Creates a new HashMap with the specified initial capacity, a load factor of 60% and linear probing.

OAIdentityHashMap(int initialCapacity, int loadFactor)
Creates a new AOHashMap with the specified initial capacity, the specified load factor and linear probing.

OAIdentityHashMap(int initialCapacity, int loadFactor, int probingStrategy)
Creates a new AOHashMap with the specified initial capacity, the specified load factor and the specified probing strategy.

Method Summary

void	clear() Removes all elements from this map.
boolean	containsKey(Object key) Checks if a value has been stored in this map.
boolean	containsValue(Object value) Checks the given value has been stored in this map.
Object	get(Object key) Gets the value that has been stored for the specified key.
boolean	isEmpty() Determines whether this map is empty.
Object[]	keys() Retrieves all keys that have been stored in this map.
Object[]	keys(Object[] objects) Retrieves all keys that have been stored in this map.
Iterator	keysIterator() Iterates over the keys of this map.
Object	put(Object key, Object value) Adds a key-value pair to this map.
Object	remove(Object key) Remove is not supported by the Open Addressing HashMap.
int	size() The size of this map.
String	toString() Returns String containing the String representations of all objects of this map.
Object[]	values() Retrieves all values that have been stored in this map.
Object[]	values(Object[] objects) Retrieves all values that have been stored in this map.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_INITIAL_CAPACITY

public static final int DEFAULT_INITIAL_CAPACITY

The default capacity is 17

See Also:

Constant Field Values

DEFAULT_LOAD_FACTOR

public static final int DEFAULT_LOAD_FACTOR

The default load factor is 60, so the HashMap is increased when 60% of it's capacity is reached

See Also:

Constant Field Values

PROBING_LINEAR

public static final int PROBING_LINEAR

When this probing is used, the next free slot will be used for keys that have the same hash code as a previously inserted item.

See Also:

Constant Field Values

PROBING_QUADRACTIC

public static final int PROBING_QUADRACTIC

When this probing is used, the interval between probes increases linearly.

See Also:

Constant Field Values

PROBING_DOUBLE_HASHING

public static final int PROBING_DOUBLE_HASHING

When this probing is used, the interval between probes is fixed but calculated using another hash function.

See Also:

Constant Field Values

Constructor Detail

OAIdentityHashMap

public OAIdentityHashMap()

Creates a new HashMap with the default initial capacity 17, a load factor of 60% and linear probing.

OAIdentityHashMap

public OAIdentityHashMap(int initialCapacity)

Creates a new HashMap with the specified initial capacity, a load factor of 60% and linear probing.

Parameters:

initialCapacity - the initial size of the map, remember that the default load factor is 75%, you if you know the maximum size ahead of time, you need to calculate initialCapacity=maxSize * 4 / 3, when you use this constructor.

OAIdentityHashMap

public OAIdentityHashMap(int initialCapacity,
                         int loadFactor)

Creates a new AOHashMap with the specified initial capacity, the specified load factor and linear probing.

Parameters:

initialCapacity - the initial size of the map.

loadFactor - the loadfactor in percent, a number between 0 and 100. When the loadfactor is 100, the size of this map is only increased after all slots have been filled.

OAIdentityHashMap

public OAIdentityHashMap(int initialCapacity,
                         int loadFactor,
                         int probingStrategy)

Creates a new AOHashMap with the specified initial capacity, the specified load factor and the specified probing strategy.

Parameters:

initialCapacity - the initial size of the map.

loadFactor - the loadfactor in percent, a number between 0 and 100. When the loadfactor is 100, the size of this map is only increased after all slots have been filled.

probingStrategy - the probing strategy, either linear, quadratic or double hashing.

See Also:

PROBING_LINEAR, PROBING_QUADRACTIC, PROBING_DOUBLE_HASHING

Method Detail

put

public Object put(Object key,
                  Object value)

Description copied from interface: Map

Adds a key-value pair to this map.

Specified by:

put in interface Map

Parameters:

key - the key

value - the value

Returns:

the value that has been stored previously for the given key, or null.

get

public Object get(Object key)

Description copied from interface: Map

Gets the value that has been stored for the specified key.

Specified by:

get in interface Map

Parameters:

key - the key

Returns:

the value or null, when for the given key no value has been stored.

remove

public Object remove(Object key)

Remove is not supported by the Open Addressing HashMap.

Specified by:

remove in interface Map

Parameters:

key - the key of the value to remove

Returns:

nothing

Throws:

RuntimeException - always

isEmpty

public boolean isEmpty()

Description copied from interface: Map

Determines whether this map is empty. This is equivalent to calling map.getSize() == 0.

Specified by:

isEmpty in interface Map

Returns:

true when this map is empty.

size

public int size()

Description copied from interface: Map

The size of this map.

Specified by:

size in interface Map

Returns:

the size of this map, 0 when no entries have been added yet.

containsKey

public boolean containsKey(Object key)

Description copied from interface: Map

Checks if a value has been stored in this map. This is equivalent to calling map.get( key ) != null.

Specified by:

containsKey in interface Map

Parameters:

key - the key

Returns:

true when a value has been stored in this map to the specified key.

containsValue

public boolean containsValue(Object value)

Description copied from interface: Map

Checks the given value has been stored in this map. This is quite an expensive operation, since all elements need to be checked in the worst case.

Specified by:

containsValue in interface Map

Parameters:

value - the value

Returns:

true when the value has been stored in this map.

clear

public void clear()

Description copied from interface: Map

Removes all elements from this map.

Specified by:

clear in interface Map

values

public Object[] values()

Description copied from interface: Map

Retrieves all values that have been stored in this map.

Specified by:

values in interface Map

Returns:

an object array with all values.

values

public Object[] values(Object[] objects)

Description copied from interface: Map

Retrieves all values that have been stored in this map.

Specified by:

values in interface Map

Parameters:

objects - the typed array in which the elements are stored

Returns:

an object array with all values.

keys

public Object[] keys()

Description copied from interface: Map

Retrieves all keys that have been stored in this map.

Specified by:

keys in interface Map

Returns:

an object array with all keys.

keys

public Object[] keys(Object[] objects)

Description copied from interface: Map

Retrieves all keys that have been stored in this map.

Specified by:

keys in interface Map

Parameters:

objects - the typed array in which the keys are stored

Returns:

an object array with all keys.

toString

public String toString()

Returns String containing the String representations of all objects of this map.

Overrides:

toString in class Object

Returns:

the stored elements in a String representation.

keysIterator

public Iterator keysIterator()

Description copied from interface: Map

Iterates over the keys of this map. In contrast to using the keys() method no additional array is created. When the map is modified while the iterator is being used, the behavior of the iterator is unspecified (unless the iterator.remove() method is used).

Specified by:

keysIterator in interface Map

Returns:

an iterator that contains all keys.