org.apache.commons.collections.map
Class StaticBucketMap

java.lang.Object
  org.apache.commons.collections.map.StaticBucketMap

All Implemented Interfaces:

java.util.Map

public final class StaticBucketMap
extends java.lang.Object
implements java.util.Map

A StaticBucketMap is an efficient, thread-safe implementation of java.util.Map that performs well in in a highly thread-contentious environment. The map supports very efficient get, put, remove and containsKey operations, assuming (approximate) uniform hashing and that the number of entries does not exceed the number of buckets. If the number of entries exceeds the number of buckets or if the hash codes of the objects are not uniformly distributed, these operations have a worst case scenario that is proportional to the number of elements in the map (O(n)).

Each bucket in the hash table has its own monitor, so two threads can safely operate on the map at the same time, often without incurring any monitor contention. This means that you don't have to wrap instances of this class with Collections.synchronizedMap(Map); instances are already thread-safe. Unfortunately, however, this means that this map implementation behaves in ways you may find disconcerting. Bulk operations, such as putAll or the retainAll operation in collection views, are not atomic. If two threads are simultaneously executing

   staticBucketMapInstance.putAll(map);
 

and

   staticBucketMapInstance.entrySet().removeAll(map.entrySet());
 

then the results are generally random. Those two statement could cancel each other out, leaving staticBucketMapInstance essentially unchanged, or they could leave some random subset of map in staticBucketMapInstance.

Also, much like an encyclopedia, the results of size() and isEmpty() are out-of-date as soon as they are produced.

The iterators returned by the collection views of this class are not fail-fast. They will never raise a ConcurrentModificationException. Keys and values added to the map after the iterator is created do not necessarily appear during iteration. Similarly, the iterator does not necessarily fail to return keys and values that were removed after the iterator was created.

Finally, unlike HashMap-style implementations, this class never rehashes the map. The number of buckets is fixed at construction time and never altered. Performance may degrade if you do not allocate enough buckets upfront.

The atomic(Runnable) method is provided to allow atomic iterations and bulk operations; however, overuse of atomic will basically result in a map that's slower than an ordinary synchronized HashMap. Use this class if you do not require reliable bulk operations and iterations, or if you can make your own guarantees about how bulk operations will affect the map.

Since:

Commons Collections 3.0 (previously in main package v2.1)

Version:

$Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $

Author:

Berin Loritsch, Gerhard Froehlich, Michael A. Smith, Paul Jack, Leo Sutic, Janek Bogucki, Kazuya Ujihara

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry

Constructor Summary

StaticBucketMap()
Initializes the map with the default number of buckets (255).

StaticBucketMap(int numBuckets)
Initializes the map with a specified number of buckets.

Method Summary

void	atomic(java.lang.Runnable r) Prevents any operations from occurring on this map while the given Runnable executes.
void	clear() Clears the map of all entries.
boolean	containsKey(java.lang.Object key) Checks if the map contains the specified key.
boolean	containsValue(java.lang.Object value) Checks if the map contains the specified value.
java.util.Set	entrySet() Gets the entry set.
boolean	equals(java.lang.Object obj) Compares this map to another, as per the Map specification.
java.lang.Object	get(java.lang.Object key) Gets the value associated with the key.
int	hashCode() Gets the hash code, as per the Map specification.
boolean	isEmpty() Checks if the size is currently zero.
java.util.Set	keySet() Gets the key set.
java.lang.Object	put(java.lang.Object key, java.lang.Object value) Puts a new key value mapping into the map.
void	putAll(java.util.Map map) Puts all the entries from the specified map into this map.
java.lang.Object	remove(java.lang.Object key) Removes the specified key from the map.
int	size() Gets the current size of the map.
java.util.Collection	values() Gets the values.

Methods inherited from class java.lang.Object

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

Constructor Detail

StaticBucketMap

public StaticBucketMap()

Initializes the map with the default number of buckets (255).

StaticBucketMap

public StaticBucketMap(int numBuckets)

Initializes the map with a specified number of buckets. The number of buckets is never below 17, and is always an odd number (StaticBucketMap ensures this). The number of buckets is inversely proportional to the chances for thread contention. The fewer buckets, the more chances for thread contention. The more buckets the fewer chances for thread contention.

Parameters:

numBuckets - the number of buckets for this map

Method Detail

size

public int size()

Gets the current size of the map. The value is computed fresh each time the method is called.

Specified by:

size in interface java.util.Map

Returns:

the current size

isEmpty

public boolean isEmpty()

Checks if the size is currently zero.

Specified by:

isEmpty in interface java.util.Map

Returns:

true if empty

get

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

Gets the value associated with the key.

Specified by:

get in interface java.util.Map

Parameters:

key - the key to retrieve

Returns:

the associated value

containsKey

public boolean containsKey(java.lang.Object key)

Checks if the map contains the specified key.

Specified by:

containsKey in interface java.util.Map

Parameters:

key - the key to check

Returns:

true if found

containsValue

public boolean containsValue(java.lang.Object value)

Checks if the map contains the specified value.

Specified by:

containsValue in interface java.util.Map

Parameters:

value - the value to check

Returns:

true if found

put

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

Puts a new key value mapping into the map.

Specified by:

put in interface java.util.Map

Parameters:

key - the key to use

value - the value to use

Returns:

the previous mapping for the key

remove

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

Removes the specified key from the map.

Specified by:

remove in interface java.util.Map

Parameters:

key - the key to remove

Returns:

the previous value at this key

keySet

public java.util.Set keySet()

Gets the key set.

Specified by:

keySet in interface java.util.Map

Returns:

the key set

values

public java.util.Collection values()

Gets the values.

Specified by:

values in interface java.util.Map

Returns:

the values

entrySet

public java.util.Set entrySet()

Gets the entry set.

Specified by:

entrySet in interface java.util.Map

Returns:

the entry set

putAll

public void putAll(java.util.Map map)

Puts all the entries from the specified map into this map. This operation is not atomic and may have undesired effects.

Specified by:

putAll in interface java.util.Map

Parameters:

map - the map of entries to add

clear

public void clear()

Clears the map of all entries.

Specified by:

clear in interface java.util.Map

equals

public boolean equals(java.lang.Object obj)

Compares this map to another, as per the Map specification.

Specified by:

equals in interface java.util.Map

Overrides:

equals in class java.lang.Object

Parameters:

obj - the object to compare to

Returns:

true if equal

hashCode

public int hashCode()

Gets the hash code, as per the Map specification.

Specified by:

hashCode in interface java.util.Map

Overrides:

hashCode in class java.lang.Object

Returns:

the hash code

atomic

public void atomic(java.lang.Runnable r)

Prevents any operations from occurring on this map while the given Runnable executes. This method can be used, for instance, to execute a bulk operation atomically:

    staticBucketMapInstance.atomic(new Runnable() {
        public void run() {
            staticBucketMapInstance.putAll(map);
        }
    });
  

It can also be used if you need a reliable iterator:

    staticBucketMapInstance.atomic(new Runnable() {
        public void run() {
            Iterator iterator = staticBucketMapInstance.iterator();
            while (iterator.hasNext()) {
                foo(iterator.next();
            }
        }
    });
  

Implementation note: This method requires a lot of time and a ton of stack space. Essentially a recursive algorithm is used to enter each bucket's monitor. If you have twenty thousand buckets in your map, then the recursive method will be invoked twenty thousand times. You have been warned.

Parameters:

r - the code to execute atomically