org.apache.commons.collections.map
Class StaticBucketMap
java.lang.Object
|
+--org.apache.commons.collections.map.StaticBucketMap
All Implemented Interfaces:
Map
public final class StaticBucketMap
extends java.lang.Object
implements 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(Object) get,
put(Object,Object) put,
remove(Object) remove and
containsKey(Object) 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 java.util.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(Map) putAll or the
Collection.retainAll(Collection) 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
java.util.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 java.util.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(Runnable) atomic
will basically result in a map that's slower than an ordinary synchronized
java.util.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.
- Commons Collections 3.0 (previously in main package v2.1)
- Berin Loritsch
- Gerhard Froehlich
- Michael A. Smith
- Paul Jack
- Leo Sutic
- Janek Bogucki
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.
- numBuckets - the number of buckets for this map
atomic
public void atomic(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.
- r - the code to execute atomically
clear
public void clear()
Clears the map of all entries.
containsKey
public boolean containsKey(final Object key)
Checks if the map contains the specified key.
- key - the key to check
- true if found
containsValue
public boolean containsValue(final Object value)
Checks if the map contains the specified value.
- value - the value to check
- true if found
entrySet
public Set entrySet()
Gets the entry set.
- the entry set
equals
public boolean equals(Object obj)
Compares this map to another, as per the Map specification.
- obj - the object to compare to
- true if equal
get
public Object get(final Object key)
Gets the value associated with the key.
- key - the key to retrieve
- the associated value
hashCode
public int hashCode()
Gets the hash code, as per the Map specification.
- the hash code
isEmpty
public boolean isEmpty()
Checks if the size is currently zero.
- true if empty
keySet
public Set keySet()
Gets the key set.
- the key set
put
public Object put(final Object key, final Object value)
Puts a new key value mapping into the map.
- key - the key to use
- value - the value to use
- the previous mapping for the key
putAll
public void putAll(Map map)
Puts all the entries from the specified map into this map.
This operation is not atomic and may have undesired effects.
- map - the map of entries to add
remove
public Object remove(Object key)
Removes the specified key from the map.
- key - the key to remove
- the previous value at this key
size
public int size()
Gets the current size of the map.
The value is computed fresh each time the method is called.
- the current size
values
public Collection values()
Gets the values.
- the values
java.util.Map
that performs well in in a highly thread-contentious environment. The map supports very efficient get(Object) get, put(Object,Object) put, remove(Object) remove and containsKey(Object) 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 java.util.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(Map) putAll or the Collection.retainAll(Collection) retainAll operation in collection views, are not atomic. If two threads are simultaneously executing and then the results are generally random. Those two statement could cancel each other out, leavingstaticBucketMapInstance
essentially unchanged, or they could leave some random subset ofmap
instaticBucketMapInstance
. 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 java.util.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 java.util.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(Runnable) atomic will basically result in a map that's slower than an ordinary synchronized java.util.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.