cocoon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Berin Loritsch" <blorit...@apache.org>
Subject RE: [RT]: Calculating the cache key
Date Tue, 28 May 2002 12:45:54 GMT
> From: Carsten Ziegeler [mailto:cziegeler@s-und-n.de] 
> 
> Volker Schmitt wrote:
> > 
> > Hi,
> > 
> > the current Interface of CacheableProcessingComponent:
> > 
> > <snip>
> > 
> > why not using Object as a return value of "generateKey" ? I think
> > this is more
> > flexible and allows the implementation of Compound keys.
> > 
> Yes, I thought about this over the weekend, too. Object as 
> the return value is the most flexible.
> 
> But when using Object the caching algorithm is required to 
> build compound objects (arrays etc.) and cannot use simple 
> string operations 
> for building the compound key anymore. (Or the Object must 
> implement a reliable toString() method)

I don't get the infatuation with the string method.  Keep in
mind that the Object only has to worry about equals() and
hashCode().  Both are fairly easy to implement. The default
hashCode() for all Objects is the memory address the object
occupies.  Now, using an Object to manage a compound key
of straight ints or longs, can use lazy initialization.  Suppose
the following class:

public class CompoundKey
{
    long[] m_keys = null;
    long   m_hash = -1;
    int    m_end  = 0;
    boolean m_validHash = false;

    public CompoundKey( int numElements )
    {
        m_keys = new long[numElements];
    }

    public void addKey( long element )
    {
        if (m_end < m_keys.length)
        {
            m_validHash = false;
            m_keys[m_end] = element;
            m_end++;
        }
        else
        {
            // Sitemap should know how many elements--this is an error
        }
    }

    public long hashCode()
    {
        if ( ! m_validHash )
        {
            m_hash = 0;
            for( int I = 0; I < m_end; I++)
            {
                m_hash += (m_keys[i] / m_end) * 3
            }

            m_validHash = true;
        }

        return m_hash;
    }

    public boolean equals(Object other)
    {
        if (! other instanceof CompoundKey) return false;
        CompoundKey test = (CompoundKey) other;

        if ( m_end != test.m_end ) return false;

        for (int I = 0; I < m_end; I++)
        {
            if (m_keys[I] != test.m_keys[I]) return false;
        }

        return true;
    }
}


> While building a compound object with for example an array is 
> a simple solution, I see currently a problem in storing this 
> into the cache. The cache can for example be implemented as a 
> hash table, so the compound key object must somehow implement 
> hashCode() and equals(). While equals() can be easily 
> implemented, I see no good solution for hashCode(). Do you 
> know a solution for this?

Look above.

There are two things you need to know about the default hashCode()
for this to work:

1) Default hash values are the address of the object--meaning that
   they are all aligned on a power of 2 ( typically every 4 or 8
   bytes depending on 32 or 64 bit machines ).

2) Very regular hash values (like the default) will heavily weight
   themselves to a particular buckets in the hash table (I found this
   out creating the new BucketMap in Avalon collections).

3) You must ensure that the resultant hashCode is not an even number,
   this will help ensure a more even distribution of hashvalues.  (this
   is what the String hashCode tries to do).

4) The hashing algorithm must be quick--but it can be cashed for a
   quick access.  That way if multiple tests on the hashCode occur,
   you can save an expensive recalculation phase for each code.


---------------------------------------------------------------------
To unsubscribe, e-mail: cocoon-dev-unsubscribe@xml.apache.org
For additional commands, email: cocoon-dev-help@xml.apache.org


Mime
View raw message