Cache: how to represent an entry

This article continues telling about my hash-based implementation of the caching mechanism. It describes the method of storing the key-value entries. Both keys and values are contained in the instances of the Ref interface. All implementations of this interface for strong, soft, and weak references have been moved into the Kind enum since the previous article.

First, consider the Cache class. It is not fully complete and contains only the fields and methods needed to implement the entries.

• • The keyKind field is used to indicate the kind of references used to store the keys.

  • The valueKind field is used to indicate the kind of references used to store the values.

  • The identity field defines whether the reference-equality is used in place of the object-equality.

  • The Cache(Kind,Kind,boolean) constructor creates a new Cache instance and initializes the fields above with the given parameters.

  • The queue field represents a reference queue for the cleared references. It is used only for soft or weak references and enables removing unused entries from the cache before accessing the hash table.

  • The hashSeed field represents a randomizing value associated with the Cache instance that is applied to the hash code of keys to make hash collisions harder to find.

  • The hash(Object) method is used to compute the hash code based on the specified object. If identity is true, then the hash code is calculated as defined by the hash method of the IdentityHashMap class. Otherwise, it is calculated as defined by the hash method of the WeakHashMap class.

    •     private int hash(Object key) {         if (key == null) {             return this.hashSeed;         }         if (this.identity) {             int hash = System.identityHashCode(key);             return (hash << 1) - (hash << 8);         }         if (key instanceof String) {             return ((String) key).hash32();         }         int hash = this.hashSeed ^ key.hashCode();         // This function ensures that hashCodes that differ only by         // constant multiples at each bit position have a bounded         // number of collisions (approximately 8 at default load factor).         hash ^= (hash >>> 20) ^ (hash >>> 12);         return hash ^ (hash >>> 7) ^ (hash >>> 4);     } 

  • My implementation of the caching mechanism uses the power-of-two length hash tables to store the entries. If several entries fall into the same cell of the hash table, these entries will be arranged as a chain. That is why the hash method implementation increases the spread of entries in different cells and reduces the size of such chains.

Consider the CacheEntry class, which represents a single entry.

• • The cache field holds the reference to the Cache instance, to which this entry corresponds. It might be a good idea to move the CacheEntry class into the Cache class, because these classes use the fields of each other.

  • The hash field contains the hash code of the key to accelerate the search in the entry chain, because one chain can store entries with different hash codes.

  • The key field is used to store a reference to the corresponding key.

  • The value field is used to store a reference to the corresponding value.

  • The next field is used to create a one-way chain.

  • The CacheEntry(Cache,int,K,V,CacheEntry) constructor creates a new CacheEntry instance and initializes the fields above with the given parameters.

  • The matches(int,Object) method checks that the entry matches to the specified key with the given hash code.

  • The matches(Object) method checks that the entry matches to the specified value.

  • The equals(Object,Object) method is used to compare two objects. It uses a reference-equality in place of an object-equality if the identity field is set to true in the corresponding cache.

    •     boolean equals(Object first, Object second) {         return (first == second) || !this.cache.identity && (first != null) && first.equals(second);     } 

  • The entry field is used to store a weak reference to the Map.Entry implementation described below.

  • The getMapEntry() method returns a proxy entry that is created as needed.

  • The replace() method replaces the value of the entry and updates the proxy entry, if it exists.

It's a bad idea to enable users to get the real entry as in the WeakHashMap implementation. I discovered the 8003845 bug that reveals losing the key by a Map.Entry instance when it is returned by WeakHashMap. So I decided to return another object, which contains strong references to the keys and values, and updates the corresponding entry on change.

Consider the ProxyEntry class, which represents such an implementation.

• • The entry field holds the reference to the CacheEntry instance, to which this proxy corresponds. This proxy entry is a simple implementation of the Map.Entry interface. It uses the fields and methods of the corresponding entry. Therefore, it is easy to convert this class into an inner anonymous class.

  • The ProxyEntry(CacheEntry) constructor initializes the field above. This is yet another argument for creating an inner anonymous class.

  • The key field is used to store a strong reference to the corresponding key.

  • The value field is used to store a strong reference to the corresponding value. This field automatically updates when calling the getValue() method.

  • Note that this Map.Entry implementation can be used to store key-value pairs even after the entry is removed from the cache.