commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael A. Smith" <...@apache.org>
Subject RE: [Commons-Avalon:collections] code integration
Date Thu, 20 Jun 2002 16:25:32 GMT
On Thu, 20 Jun 2002, Jack, Paul wrote:
> > yup, I understand that...  My point is that the rest of the 
> > map contract 
> > should be addressed as well.  :)
> 
> Agreed.  I'll fix the collection views if you'd like.

If you want.  I won't stop you.  :)

> Also, BucketMap does not support null keys or values but 
> returns null when such values are supplied to put().  
> Map contract specifies NullPointerException in that case.
> 
> The tests won't pick that up, so we should add a test case.
> 
> Also, there's no no-argument and Map-argument constructors;
> not required, but recommended.

good finds.  We could/should add tests for each of those.  

> > btw, one thing that java.util.HashMap and java.util.Hashtable 
> > provide is the ability to have the underlying hashtable grow 
> > when the contents of the hashtable grow to a certain load 
> > factor of the size of the underlying table.  I didn't see the 
> > same feature in BucketMap.  Wouldn't that mean that BucketMap 
> > would degrade in performance significantly (compared with 
> > java.util's hash based maps) as the size of the map 
> > increases well beyond its number of buckets?  
> 
> I don't think auto-resizing could be implemented in BucketMap
> without affecting the optimizations in the get and put 
> methods.  Basically, what monitor do you enter when you're
> resizing the array of monitors?  Any clever workaround would
> incur double-checked-locking-esque problems.

no double-checked-locking-esque problems...

rather than having each bucket a linked list, make each bucket a 
resizable hashtable.  The number of buckets changes from some non-power 
of two to be a power of two. 

Compute the hashcode of the key, and with an appropriate mask (i.e. the
fixed size - 1) to determine the proper bucket.  synchronize on the
bucket.  Mod the computed hash code by that particular buckets current 
sub-bucket size to find the linked list that should contain the key.  
iterate the linked list to find the element.  When adding, determine 
current load on the bucket's hashtable (probably pre-computed/cached for 
with each add), and determine whether expansion is necessary.  This 
expansion expands the one top-level bucket.  

hope that makes sense.  

> I think BucketMap is optimal for the case when you know upfront
> that you have a maximum number of possible mappings at any
> time.

The other option is to make sure that this is a well documented 
limitation.  We could always add a DynamicBucketMap that adds the 
expansion capabilities at the cost I described before.

regards,
michael



--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message