4.0.0 JNI/reflection invocation 2/4/8 times as slow as in 3.3.3

Andrew Haley aph@redhat.com
Fri Jan 28 10:02:00 GMT 2005


Ranjit Mathew writes:
 > On Fri, 28 Jan 2005 09:47:04 +0000, Andrew Haley <aph@redhat.com> wrote:
 > >
 > > But I can't see that we handle collisions at all.  Look at this:
 > > 
 > >   public Object put(Object key, Object value)
 > >   {
 > >     // Rehash if the load factor is too high.
 > >     if (size > threshold)
 > >       {
 > > ...
 > >       }
 > > 
 > >     int h = hash(key);
 > >     if (table[h] == key)
 > >       {
 > >         Object r = table[h + 1];
 > >         table[h + 1] = value;
 > >         return r;
 > >       }
 > > 
 > >     // At this point, we add a new mapping.
 > >     modCount++;
 > >     size++;
 > >     table[h] = key;
 > >     table[h + 1] = value;
 > >     return null;
 > >   }
 > > 
 > > Aren't we overwriting an existing key here?  Surely we need to
 > > increment h until an empty entry is found.
 > 
 > Look at the implementation of hash() - it computes
 > the hash code and then also finds the appropriate bucket
 > for the key.

Oh yeuch, how nasty.

Okay, so we're using linear probing rather than double hashing, in
which case Algorithm R is appropriate.

Andrew.



More information about the Java mailing list