bloritsch 2002/06/26 18:10:56
Modified: collections/src/java/org/apache/avalon/excalibur/collections
BucketMap.java
collections/src/test/org/apache/avalon/excalibur/collections/test
ThreadedMapTest.java
Log:
fix hashing algorithm so we are not sensitive to power of two boundaries
Revision Changes Path
1.20 +11 -9
jakarta-avalon-excalibur/collections/src/java/org/apache/avalon/excalibur/collections/BucketMap.java
Index: BucketMap.java
===================================================================
RCS file:
/home/cvs/jakarta-avalon-excalibur/collections/src/java/org/apache/avalon/excalibur/collections/BucketMap.java,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -r1.19 -r1.20
--- BucketMap.java 26 Jun 2002 17:43:54 -0000 1.19
+++ BucketMap.java 27 Jun 2002 01:10:56 -0000 1.20
@@ -27,7 +27,7 @@
*/
public final class BucketMap implements Map
{
- private static final int DEFAULT_BUCKETS = 255;
+ private static final int DEFAULT_BUCKETS = 256;
private final Node[] m_buckets;
private volatile int m_size = 0;
@@ -51,12 +51,6 @@
{
int size = Math.max( 17, numBuckets );
- // Ensure that bucketSize is never a power of 2 (to ensure maximal
distribution)
- if( size % 2 == 0 )
- {
- size--;
- }
-
m_buckets = new Node[ size ];
for( int i = 0; i < size; i++ )
@@ -80,7 +74,15 @@
*/
private final int getHash( Object key )
{
- final int hash = key.hashCode() % m_buckets.length;
+ int hash = key.hashCode();
+
+ hash += ~(hash << 9);
+ hash ^= (hash >>> 14);
+ hash += (hash << 4);
+ hash ^= (hash >>> 10);
+
+ hash %= m_buckets.length;
+
return ( hash < 0 ) ? hash * -1 : hash;
}
1.6 +6 -6
jakarta-avalon-excalibur/collections/src/test/org/apache/avalon/excalibur/collections/test/ThreadedMapTest.java
Index: ThreadedMapTest.java
===================================================================
RCS file:
/home/cvs/jakarta-avalon-excalibur/collections/src/test/org/apache/avalon/excalibur/collections/test/ThreadedMapTest.java,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- ThreadedMapTest.java 26 Jun 2002 21:13:43 -0000 1.5
+++ ThreadedMapTest.java 27 Jun 2002 01:10:56 -0000 1.6
@@ -25,8 +25,8 @@
*/
public class ThreadedMapTest extends TestCase
{
- private static final int ITERATIONS = 10000;
- private static final int THREADS = 20;
+ private static final int ITERATIONS = 4000;
+ private static final int THREADS = 50;
private MapStart[] stages;
@@ -47,12 +47,12 @@
public void testBucketMapSizedThreaded() throws Exception
{
- initialize( ITERATIONS, THREADS, new BucketMap( ( ITERATIONS / 2 ) +
1) );
+ initialize( ITERATIONS, THREADS, new BucketMap( ITERATIONS / 2 ) );
long start = System.currentTimeMillis();
start();
long end = System.currentTimeMillis();
- System.out.println("BucketMap (" + ((ITERATIONS / 2) + 1) + "
buckets) took " + (end - start) + "ms");
+ System.out.println("BucketMap (" + ITERATIONS / 2 + " buckets) took
" + (end - start) + "ms");
System.out.println("Thats " + ( (float)(end - start) /
(float)(ITERATIONS * THREADS) ) + "ms per operation");
}
@@ -63,13 +63,13 @@
start();
long end = System.currentTimeMillis();
- System.out.println("Unsized BucketMap (255 buckets) took " + (end -
start) + "ms");
+ System.out.println("Unsized BucketMap (256 buckets) took " + (end -
start) + "ms");
System.out.println("Thats " + ( (float)(end - start) /
(float)(ITERATIONS * THREADS) ) + "ms per operation");
}
public void testSynchronizedHashMapSizedThreaded() throws Exception
{
- initialize( ITERATIONS, THREADS, Collections.synchronizedMap(new
HashMap(((ITERATIONS / 2) + 1))) );
+ initialize( ITERATIONS, THREADS, Collections.synchronizedMap(new
HashMap(ITERATIONS / 2)) );
long start = System.currentTimeMillis();
start();
long end = System.currentTimeMillis();
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
