RE: We desperately need an efficient threadsafe hashmap

[Gerhard Froehlich]

Hi,
I had to take the ball ;-).

attached a minimal implementation, just to test
the main alhorithm. is doesn't implement Map in
the moment...

just an impression...follow more later...

but it rolls!

  ~Gerhard 

"Sorry, but my karma just ran over your dogma."

>-----Original Message-----
>From: Berin Loritsch [mailto:[EMAIL PROTECTED]]
>Sent: Friday, February 15, 2002 6:53 PM
>To: [EMAIL PROTECTED]
>Subject: We desperately need an efficient threadsafe hashmap
>
>
>I remember reading an article on how to implement an efficient ThreadSafe hashmap.
>The problem is that I can't remember where.  The concept is to reduce the locking
>contention to a "bucket".  The implementation they had was fairly simple, and
>went something along these lines:
>
>LockedBucketMap
>{
>     Object[] locks;
>     Node[] buckets;
>
>     LockedBucketMap()
>     {
>         this(256);
>     }
>
>     LockedBucketMap( int numBockets )
>     {
>         locks = new Object[numBuckets];
>         buckets = new Node[numBuckets];
>
>         for (int i = 0; i < locks.length; i++)
>         {
>             locks[i] = new Object();
>         }
>     }
>
>     void put( Object key, Object value )
>     {
>         int hash = getHash(key);
>
>         Node node = null;
>
>         synchronized( locks[hash] )
>         {
>             node = buckets[hash];
>             if (node == null)
>             {
>                 buckets[hash] = new Node( key, value );
>             }
>             else
>             {
>                 while (node != null)
>                 {
>                     node = node.next;
>                 }
>                 node.next = new Node(key, value);
>             }
>         }
>     }
>
>     Object get( Object key )
>     {
>         int hash = getHash(key);
>         Node node = null;
>         Object value = null;
>
>         synchronized( locks[hash] )
>         {
>             node = buckets[hash];
>
>             while (node != null)
>             {
>                 if (node.key.equals(key)) return node.value;
>                 node = node.next;
>             }
>         }
>         return value;
>     }
>
>     int getHash( Object key )
>     {
>         return key.hashCode() % buckets.length;
>     }
>
>     class Node
>     {
>         Object key;
>         Object value;
>         Node next;
>     }
>}
>
>I don't have time to test it, debug it, or optimize it (what about using
>ArrayList and a Node that matches against the key object etc. for lookup).
>Could someone take the ball and run with it?  We desperately need to reduce
>thread contention on the ECM and ContainerManager implementations.
>
>-- 
>
>"They that give up essential liberty to obtain a little temporary safety
>  deserve neither liberty nor safety."
>                 - Benjamin Franklin
>
>
>--
>To unsubscribe, e-mail:   <mailto:[EMAIL PROTECTED]>
>For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
>
>

LockedBucketMap.java
Description: Binary data

LockedBucketMapTest.java
Description: Binary data

--
To unsubscribe, e-mail:   <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>