|
Keel 2.1RC2 | ||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||||
java.lang.Objectorg.apache.commons.collections.StaticBucketMap
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 hashcodes 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.
| Nested Class Summary | |
private class |
StaticBucketMap.EntryIterator |
private class |
StaticBucketMap.EntrySet |
private class |
StaticBucketMap.KeyIterator |
private class |
StaticBucketMap.KeySet |
private static class |
StaticBucketMap.Lock |
private class |
StaticBucketMap.NodeThe Map.Entry for the StaticBucketMap. |
private class |
StaticBucketMap.ValueIterator |
private class |
StaticBucketMap.Values |
| Nested classes inherited from class java.util.Map |
java.util.Map.Entry |
| Field Summary | |
private static int |
DEFAULT_BUCKETS |
private StaticBucketMap.Node[] |
m_buckets |
private StaticBucketMap.Lock[] |
m_locks |
| 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 occuring on this map while the given Runnable executes. |
private void |
atomic(java.lang.Runnable r, int bucket) |
void |
clear()Implements Map.clear(). |
boolean |
containsKey(java.lang.Object key)Implements Map.containsKey(Object). |
boolean |
containsValue(java.lang.Object value)Implements Map.containsValue(Object). |
java.util.Set |
entrySet()Implements Map.entrySet(). |
boolean |
equals(java.lang.Object obj)Implements Map.equals(Object). |
java.lang.Object |
get(java.lang.Object key)Implements Map.get(Object). |
private int |
getHash(java.lang.Object key)Determine the exact hash entry for the key. |
int |
hashCode()Implements Map.hashCode(). |
boolean |
isEmpty()Implements Map.isEmpty(). |
java.util.Set |
keySet()Implements Map.keySet(). |
java.lang.Object |
put(java.lang.Object key, java.lang.Object value)Implements Map.put(Object, Object). |
void |
putAll(java.util.Map other)Implements Map.putAll(Map). |
java.lang.Object |
remove(java.lang.Object key)Implements Map.remove(Object). |
int |
size()Implements Map.size(). |
java.util.Collection |
values()Implements Map.values(). |
| Methods inherited from class java.lang.Object |
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
private static final int DEFAULT_BUCKETS
private StaticBucketMap.Node[] m_buckets
private StaticBucketMap.Lock[] m_locks
| Constructor Detail |
public StaticBucketMap()
public StaticBucketMap(int numBuckets)
numBuckets - the number of buckets for this map| Method Detail |
private final int getHash(java.lang.Object key)
He = |Hk mod n|
He is the entry's hashCode, Hk is the key's hashCode, and n is the number of buckets.
public java.util.Set keySet()
Map.keySet().
keySet in interface java.util.Mappublic int size()
Map.size().
size in interface java.util.Map
public java.lang.Object put(java.lang.Object key,
java.lang.Object value)
Map.put(Object, Object).
put in interface java.util.Mappublic java.lang.Object get(java.lang.Object key)
Map.get(Object).
get in interface java.util.Mappublic boolean containsKey(java.lang.Object key)
Map.containsKey(Object).
containsKey in interface java.util.Mappublic boolean containsValue(java.lang.Object value)
Map.containsValue(Object).
containsValue in interface java.util.Mappublic java.util.Collection values()
Map.values().
values in interface java.util.Mappublic java.util.Set entrySet()
Map.entrySet().
entrySet in interface java.util.Mappublic void putAll(java.util.Map other)
Map.putAll(Map).
putAll in interface java.util.Mappublic java.lang.Object remove(java.lang.Object key)
Map.remove(Object).
remove in interface java.util.Mappublic final boolean isEmpty()
Map.isEmpty().
isEmpty in interface java.util.Mappublic final void clear()
Map.clear().
clear in interface java.util.Mappublic final boolean equals(java.lang.Object obj)
Map.equals(Object).
equals in interface java.util.Mappublic final int hashCode()
Map.hashCode().
hashCode in interface java.util.Mappublic void atomic(java.lang.Runnable r)
Runnable executes. This method can be used, for instance, to execute a bulk operation atomicly:
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 atomicly
private void atomic(java.lang.Runnable r,
int bucket)
|
Keel 2.1RC2 | ||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||||