You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by pj...@apache.org on 2002/08/15 05:22:29 UTC
cvs commit: jakarta-commons/collections/src/java/org/apache/commons/collections StaticBucketMap.java
pjack 2002/08/14 20:22:29
Modified: collections/src/java/org/apache/commons/collections
StaticBucketMap.java
Log:
1. Collection views are now backed by map.
2. Used bit-mixing hash function.
3. Added docs about the non-atomic nature of bulk operations.
4. Improved performance of size() operation.
5. Added atomic(Runnable) method.
Revision Changes Path
1.3 +314 -89 jakarta-commons/collections/src/java/org/apache/commons/collections/StaticBucketMap.java
Index: StaticBucketMap.java
===================================================================
RCS file: /home/cvs/jakarta-commons/collections/src/java/org/apache/commons/collections/StaticBucketMap.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- StaticBucketMap.java 10 Jul 2002 03:35:32 -0000 1.2
+++ StaticBucketMap.java 15 Aug 2002 03:22:29 -0000 1.3
@@ -60,36 +60,91 @@
*/
package org.apache.commons.collections;
+import java.util.AbstractCollection;
+import java.util.AbstractSet;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.ArrayList;
+import java.util.NoSuchElementException;
/**
* A StaticBucketMap is an efficient, thread-safe implementation of
* <code>java.util.Map</code> that performs well in in a highly
* thread-contentious environment. The map supports very efficient
- * <code>get</code>, <code>put</code>, <code>contains</code>, and
- * <code>remove</code> operations, assuming (approximate) uniform hashing and
- * that the number of entries does not exceed the size of the map. If the
- * number of entries exceeds the size of the map or if the hashcodes of the
+ * {@link #get(Object) get}, {@link #put(Object,Object) put},
+ * {@link #remove(Object) remove} and {@link #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 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
- * (<I>O(n)</I>).
+ * (<I>O(n)</I>).<P>
+ *
+ * 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 {@link 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 {@link #putAll(Map) putAll} or the
+ * {@link Collection#retainAll(Collection) retainAll} operation in collection
+ * views, are <I>not</I> atomic. If two threads are simultaneously
+ * executing
+ *
+ * <Pre>
+ * staticBucketMapInstance.putAll(map);
+ * </Pre>
+ *
+ * and
+ *
+ * <Pre>
+ * staticBucketMapInstance.entrySet().removeAll(map.entrySet());
+ * </Pre>
+ *
+ * then the results are generally random. Those two statement could cancel
+ * each other out, leaving <Code>staticBucketMapInstance</Code> essentially
+ * unchanged, or they could leave some random subset of <Code>map</Code> in
+ * <Code>staticBucketMapInstance</Code>.<P>
+ *
+ * Also, much like an encyclopedia, the results of {@link #size()} and
+ * {@link #isEmpty()} are out-of-date as soon as they are produced.<P>
+ *
+ * The iterators returned by the collection views of this class are <I>not</I>
+ * fail-fast. They will <I>never</I> raise a
+ * {@link 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.<P>
+ *
+ * Finally, unlike {@link java.util.HashMap}-style implementations, this
+ * class <I>never</I> 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.<P>
+ *
+ * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
+ * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
+ * will basically result in a map that's slower than an ordinary synchronized
+ * {@link 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.<P>
*
* @author <a href="mailto:bloritsch@apache.org">Berin Loritsch</a>
* @author <a href="mailto:g-froehlich@gmx.de">Gerhard Froehlich</a>
* @author <a href="mailto:mas@apache.org">Michael A. Smith</a>
+ * @author Paul Jack
* @version CVS $Revision$ $Date$
* @since Avalon 4.0
*/
public final class StaticBucketMap implements Map
{
private static final int DEFAULT_BUCKETS = 255;
- private final Node[] m_buckets;
- private final Object[] m_locks;
+ private Node[] m_buckets;
+ private Lock[] m_locks;
/**
* Initializes the map with the default number of buckets (255).
@@ -106,6 +161,8 @@
* chances for thread contention. The fewer buckets, the more chances for
* thread contention. The more buckets the fewer chances for thread
* contention.
+ *
+ * @param numBuckets the number of buckets for this map
*/
public StaticBucketMap( int numBuckets )
{
@@ -118,11 +175,11 @@
}
m_buckets = new Node[ size ];
- m_locks = new Object[ size ];
+ m_locks = new Lock[ size ];
for( int i = 0; i < size; i++ )
{
- m_locks[ i ] = new Object();
+ m_locks[ i ] = new Lock();
}
}
@@ -142,34 +199,23 @@
private final int getHash( Object key )
{
if( key == null ) return 0;
- final int hash = key.hashCode() % m_buckets.length;
+ int hash = key.hashCode();
+ hash += ~(hash << 15);
+ hash ^= (hash >>> 10);
+ hash += (hash << 3);
+ hash ^= (hash >>> 6);
+ hash += ~(hash << 11);
+ hash ^= (hash >>> 16);
+ hash %= m_buckets.length;
return ( hash < 0 ) ? hash * -1 : hash;
}
/**
- * Obtain a Set for the keys. This operation crosses bucket boundaries,
- * so it is less efficient, and greatly increases the chance for thread
- * contention.
+ * Returns a set view of this map's keys.
*/
public Set keySet()
{
- Set keySet = new HashSet();
-
- for( int i = 0; i < m_buckets.length; i++ )
- {
- synchronized( m_locks[ i ] )
- {
- Node n = m_buckets[ i ];
-
- while( n != null )
- {
- keySet.add( n.key );
- n = n.next;
- }
- }
- }
-
- return keySet;
+ return new KeySet();
}
/**
@@ -181,16 +227,7 @@
for( int i = 0; i < m_buckets.length; i++ )
{
- synchronized( m_locks[ i ] )
- {
- Node n = m_buckets[ i ];
-
- while( n != null )
- {
- cnt++;
- n = n.next;
- }
- }
+ cnt += m_locks[i].size;
}
return cnt;
@@ -213,6 +250,7 @@
n.key = key;
n.value = value;
m_buckets[ hash ] = n;
+ m_locks[hash].size++;
return null;
}
@@ -237,6 +275,7 @@
newNode.key = key;
newNode.value = value;
n.next = newNode;
+ m_locks[hash].size++;
}
return null;
@@ -328,23 +367,7 @@
*/
public Collection values()
{
- ArrayList values = new ArrayList();
-
- for( int i = 0; i < m_buckets.length; i++ )
- {
- synchronized( m_locks[ i ] )
- {
- Node n = m_buckets[ i ];
-
- while( n != null )
- {
- values.add( n.value );
- n = n.next;
- }
- }
- }
-
- return values;
+ return new Values();
}
/**
@@ -354,23 +377,7 @@
*/
public Set entrySet()
{
- Set entrySet = new HashSet();
-
- for( int i = 0; i < m_buckets.length; i++ )
- {
- synchronized( m_locks[ i ] )
- {
- Node n = m_buckets[ i ];
-
- while( n != null )
- {
- entrySet.add( n );
- n = n.next;
- }
- }
- }
-
- return entrySet;
+ return new EntrySet();
}
/**
@@ -414,7 +421,7 @@
// Set the next node of the previous node to be the node after this one.
prev.next = n.next;
}
-
+ m_locks[hash].size--;
return n.value;
}
@@ -431,15 +438,7 @@
*/
public final boolean isEmpty()
{
- for( int i = 0; i < m_buckets.length; i++ )
- {
- if( m_buckets[ i ] != null )
- {
- return false;
- }
- }
-
- return true;
+ return size() == 0;
}
/**
@@ -449,10 +448,21 @@
{
for( int i = 0; i < m_buckets.length; i++ )
{
- m_buckets[ i ] = null;
+ Lock lock = m_locks[i];
+ synchronized (lock) {
+ m_buckets[ i ] = null;
+ lock.size = 0;
+ }
}
}
+ /**
+ * Returns true if the given object is a map with the same mappings
+ * as this map.
+ *
+ * @return true if the given object is the a map with same mappings
+ * as this map
+ */
public final boolean equals( Object obj )
{
if( obj == null ) return false;
@@ -465,6 +475,11 @@
return entrySet().equals(other.entrySet());
}
+ /**
+ * Returns a hash code for this map.
+ *
+ * @return a hash code for this map
+ */
public final int hashCode()
{
int hashCode = 0;
@@ -532,4 +547,214 @@
return retVal;
}
}
+
+ private final static class Lock {
+
+ public int size;
+
+ }
+
+
+ private class EntryIterator implements Iterator {
+
+ private ArrayList current = new ArrayList();
+ private int bucket;
+ private Map.Entry last;
+
+
+ public boolean hasNext() {
+ if (current.size() > 0) return true;
+ while (bucket < m_buckets.length) {
+ synchronized (m_locks[bucket]) {
+ Node n = m_buckets[bucket];
+ while (n != null) {
+ current.add(n);
+ n = n.next;
+ }
+ bucket++;
+ if (current.size() > 0) return true;
+ }
+ }
+ return false;
+ }
+
+ protected Map.Entry nextEntry() {
+ if (!hasNext()) throw new NoSuchElementException();
+ last = (Map.Entry)current.remove(current.size() - 1);
+ return last;
+ }
+
+ public Object next() {
+ return nextEntry();
+ }
+
+ public void remove() {
+ if (last == null) throw new IllegalStateException();
+ StaticBucketMap.this.remove(last.getKey());
+ last = null;
+ }
+
+ }
+
+ private class ValueIterator extends EntryIterator {
+
+ public Object next() {
+ return nextEntry().getValue();
+ }
+
+ }
+
+ private class KeyIterator extends EntryIterator {
+
+ public Object next() {
+ return nextEntry().getKey();
+ }
+
+ }
+
+ private class EntrySet extends AbstractSet {
+
+ public int size() {
+ return StaticBucketMap.this.size();
+ }
+
+ public void clear() {
+ StaticBucketMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new EntryIterator();
+ }
+
+ public boolean contains(Object o) {
+ Map.Entry entry = (Map.Entry)o;
+ int hash = getHash(entry.getKey());
+ synchronized (m_locks[hash]) {
+ for (Node n = m_buckets[hash]; n != null; n = n.next) {
+ if (n.equals(entry)) return true;
+ }
+ }
+ return false;
+ }
+
+ public boolean remove(Object o) {
+ Map.Entry entry = (Map.Entry)o;
+ int hash = getHash(entry.getKey());
+ synchronized (m_locks[hash]) {
+ for (Node n = m_buckets[hash]; n != null; n = n.next) {
+ if (n.equals(entry)) {
+ StaticBucketMap.this.remove(n.getKey());
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ }
+
+
+ private class KeySet extends AbstractSet {
+
+ public int size() {
+ return StaticBucketMap.this.size();
+ }
+
+ public void clear() {
+ StaticBucketMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new KeyIterator();
+ }
+
+ public boolean contains(Object o) {
+ return StaticBucketMap.this.containsKey(o);
+ }
+
+ public boolean remove(Object o) {
+ int hash = getHash(o);
+ synchronized (m_locks[hash]) {
+ for (Node n = m_buckets[hash]; n != null; n = n.next) {
+ Object k = n.getKey();
+ if ((k == o) || ((k != null) && k.equals(o))) {
+ StaticBucketMap.this.remove(k);
+ return true;
+ }
+ }
+ }
+ return false;
+
+ }
+
+ }
+
+
+ private class Values extends AbstractCollection {
+
+ public int size() {
+ return StaticBucketMap.this.size();
+ }
+
+ public void clear() {
+ StaticBucketMap.this.clear();
+ }
+
+ public Iterator iterator() {
+ return new ValueIterator();
+ }
+
+ }
+
+
+ /**
+ * Prevents any operations from occuring on this map while the
+ * given {@link Runnable} executes. This method can be used, for
+ * instance, to execute a bulk operation atomicly:
+ *
+ * <Pre>
+ * staticBucketMapInstance.atomic(new Runnable() {
+ * public void run() {
+ * staticBucketMapInstance.putAll(map);
+ * }
+ * });
+ * </Pre>
+ *
+ * It can also be used if you need a reliable iterator:
+ *
+ * <Pre>
+ * staticBucketMapInstance.atomic(new Runnable() {
+ * public void run() {
+ * Iterator iterator = staticBucketMapInstance.iterator();
+ * while (iterator.hasNext()) {
+ * foo(iterator.next();
+ * }
+ * }
+ * });
+ * </Pre>
+ *
+ * <B>Implementation note:</B> 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.
+ *
+ * @param r the code to execute atomicly
+ */
+ public void atomic(Runnable r) {
+ if (r == null) throw new NullPointerException();
+ atomic(r, 0);
+ }
+
+ private void atomic(Runnable r, int bucket) {
+ if (bucket >= m_buckets.length) {
+ r.run();
+ return;
+ }
+ synchronized (m_locks[bucket]) {
+ atomic(r, bucket + 1);
+ }
+ }
+
+
}
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>