Retrieve the key from a map (2)

java-programmer, Retrieve the key from a map (2) Sorry to everyone,

probably I simplified my example a bit too much. So here is what I
really want;

I want to implement a cache, where the key class is implemented by
myself, but the value class is java.util.List. I want to count the hits
of this cache, separately for each cache entry. Therefore I want to
store the hits-counter at the key class.

class Key
{
Object value;
int hits;

int hashCode()
{
return value.hashCode();
}

boolean equals(Object o)
{
return (o instanceof Key) && value.equals(((Key)o).value);
}
}

class Cache
{
HashMap<Key, List> store = new HashMap<Key, List>()

void put(Key key, List value)
{
store.put(key, value);
}

List get(Key key)
{
Key originalKey = store.getKey(key) // does not exist !!!!!!
if(originalKey!=null)
originalKey.hits++;
return store.get(key);
}
}

As you can see, for the hit counter to work, I need the same (not just
equal) key, that was used for insertion into the map. I don't know how
to do this - apart from the obvious brute force attack.

Ralf.

java-programmer >> Retrieve the key from a map (2) On 07.09.2006 15:17, email***@***.com wrote:
> Sorry to everyone,
>
> probably I simplified my example a bit too much. So here is what I
> really want;
>
> I want to implement a cache, where the key class is implemented by
> myself, but the value class is java.util.List. I want to count the hits
> of this cache, separately for each cache entry. Therefore I want to
> store the hits-counter at the key class.

I'd rather not do that. The reason is: the key must be know outside of
your class Cache and thus the key should not carry information which is
internal to your cache. Also it may make usage of the Cache class more
complicated; for example: if you use String as key then the client must
create a StringKeyWithCounts and hand that off to your class (at least
the way you do it right now). If you do it internally in class Cache
you still pay the overhead of object creation which you need to do the
lookup.

Rather do this: create a value class that is internal to your Cache
(private static) with a field for the value and a field for the hit
counter. See the sample below.

Kind regards

robert

import java.util.HashMap;
import java.util.Map;

public class Cache<K, V> {

private Map<K, Val<V>> values = new HashMap<K, Val<V>>();

public void set( K key, V val ) {
Val<V> tmp = values.get( key );

if ( tmp == null ) {
tmp = new Val<V>();
values.put( key, tmp );
}

tmp.setValue( val );
}

public V get( K key ) {
Val<V> tmp = values.get( key );

if ( tmp == null ) {
return null;
}
else {
tmp.increment();
return tmp.getValue();
}
}

public int getHits( K key ) {
Val<V> tmp = values.get( key );
return tmp == null ? 0 : tmp.getCount();
}
}

class Val<V> {
private V value;

private int count;

public void setValue( V val ) {
this.value = val;
}

public V getValue() {
return value;
}

public void increment() {
++count;
}

public int getCount() {
return count;
}
}

java-programmer >> Retrieve the key from a map (2) email***@***.com wrote:

> I want to implement a cache, where the key class is implemented by
> myself, but the value class is java.util.List. I want to count the hits
> of this cache, separately for each cache entry. Therefore I want to
> store the hits-counter at the key class.

It would be a lot simpler to keep a separate Map from keys to hit-counts than
to try to keep the count "in" the key.

-- chris

java-programmer >> Retrieve the key from a map (2)
Robert Klemme skrev:

>
> public class Cache<K, V> {
>
> private Map<K, Val<V>> values = new HashMap<K, Val<V>>();
>
> public void set( K key, V val ) {
> Val<V> tmp = values.get( key );
>
> if ( tmp == null ) {
> tmp = new Val<V>();
> values.put( key, tmp );
> }
>
> tmp.setValue( val );
> }
>
> public V get( K key ) {
> Val<V> tmp = values.get( key );
>

Light-years OT:

One of the more ridiculous reasons I don't like generics: it makes code
look like a fleet of WW2 bombers droning overhead before they spill
their deathly loads on me. All those hard, merciless angle-brackets.
Funny how the syntax gives such three-dimensional depth to the code.

Listen! Hear that?

Dddddddddrrrrrrrrroooooooooonnnnnnnnneeeeeeeeeee ...

.ed

Download Fractality, free Java code analyzer:
www.EdmundKirwan.com/servlet/fractal/frac-page130.html

java-programmer >> Retrieve the key from a map (2) On 07.09.2006 15:46, Chris Uppal wrote:
> email***@***.com wrote:
>
>> I want to implement a cache, where the key class is implemented by
>> myself, but the value class is java.util.List. I want to count the hits
>> of this cache, separately for each cache entry. Therefore I want to
>> store the hits-counter at the key class.
>
> It would be a lot simpler to keep a separate Map from keys to hit-counts than
> to try to keep the count "in" the key.

That's an option. However, I prefer the solution I presented for the
following reasons:

- more time efficient (just a single map lookup)
- more space efficient (just one hash table)
- easier maintenance of consistency (only one map to update)

Depending on the circumstances this can matter or not. Also other
solutions might be more appropriate for other requirements.

Kind regards

robert

java-programmer >> Retrieve the key from a map (2) Chris Uppal wrote:
> email***@***.com wrote:
>
>> I want to implement a cache, where the key class is implemented by
>> myself, but the value class is java.util.List. I want to count the hits
>> of this cache, separately for each cache entry. Therefore I want to
>> store the hits-counter at the key class.
>
> It would be a lot simpler to keep a separate Map from keys to hit-counts than
> to try to keep the count "in" the key.

If it were going to be kept anywhere in a single map, the hit count
should be part of the value, not the key. However, two maps would be
simpler and cleaner.

Patricia

java-programmer >> Retrieve the key from a map (2) Robert Klemme wrote:

[me:]
> > It would be a lot simpler to keep a separate Map from keys to
> > hit-counts than to try to keep the count "in" the key.
>
> That's an option. However, I prefer the solution I presented for the
> following reasons:
>
> - more time efficient (just a single map lookup)
> - more space efficient (just one hash table)
> - easier maintenance of consistency (only one map to update)

Agreed, but you don't list the downsides: more complicated code, code which
does two unrelated things with one operation, code in whch the actual values
have a somewhat obscure relationship with the logical values.

Swings and roundabouts...

-- chris

java-programmer >> Retrieve the key from a map (2)
<email***@***.com> wrote in message
news:email***@***.com...
> Sorry to everyone,
>
> probably I simplified my example a bit too much. So here is what I
> really want;
>
> I want to implement a cache, where the key class is implemented by
> myself, but the value class is java.util.List. I want to count the hits
> of this cache, separately for each cache entry. Therefore I want to
> store the hits-counter at the key class.

<snip code>

I agree with Patricia's assessment and I think you should focus on the value
rather than the key--roughly

class CacheEntry {
String key
List list
int hits
}

Your cache should simply map String keys to CacheEntry . You can index this
with any key, not necessarily the original, but you'll get back your list
and hits as well as your original key (if you still happen to need it, which
I doubt). You can switch to a more complex key and this needn't change, but
if the tight coupling between values and hits bothers you, you'll have to
use two separate hash tables (as others have pointed out) nominally for no
other reason than to map the source keys into the cache keys.

Matt Humphrey email***@***.com http://www.iviz.com/

java-programmer >> Retrieve the key from a map (2) Chris Uppal wrote:
> Robert Klemme wrote:
>
> [me:]
>>> It would be a lot simpler to keep a separate Map from keys to
>>> hit-counts than to try to keep the count "in" the key.
>> That's an option. However, I prefer the solution I presented for the
>> following reasons:
>>
>> - more time efficient (just a single map lookup)
>> - more space efficient (just one hash table)
>> - easier maintenance of consistency (only one map to update)
>
> Agreed, but you don't list the downsides: more complicated code, code which
> does two unrelated things with one operation, code in whch the actual values
> have a somewhat obscure relationship with the logical values.
>
> Swings and roundabouts...

and inability to reuse existing code, developed for unrelated
applications, that does one, but not both, of the jobs.

The following would need a remove method added, but it should be obvious
how to do that.

/*
* Created on Aug 14, 2004
*/
package utilities;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
* Utility class for counting instances of equal objects.
*/
public class Counter {

private Map<Object,Count> data = new HashMap<Object,Count>();

/**
* Increment by one the count associated with a specified
* key.
* @param key
*/
public void increment(Object key) {
Count count = data.get(key);
if (count == null) {
count = new Count();
data.put(key, count);
}
count.increment();
}

/**
* Get the count associated with a specified key.
* @param key The key whose count is required.
* @return The number of times increment has been called with
* a key equal to this one.
*/
public int get(Object key) {
Count count = data.get(key);
if (count == null) {
return 0;
} else {
return count.get();
}
}

/**
* Get number of unique counted objects
*
* @return Number of key objects for which increment
* has been called. Equal objects are only counted once.
*/
public int size() {
return data.size();
}

/**
* Get all the unique counted objects
* @return A set containing a refence to the counted objects.
*/
public Set getKeys() {
return Collections.unmodifiableSet(data.keySet());
}

private static class Count {
private int val = 0;

private void increment() {
val++;
}

private int get() {
return val;
}
}

}

java-programmer >> Retrieve the key from a map (2) Chris Uppal wrote:
> Robert Klemme wrote:
>
> [me:]
>>> It would be a lot simpler to keep a separate Map from keys to
>>> hit-counts than to try to keep the count "in" the key.
>> That's an option. However, I prefer the solution I presented for the
>> following reasons:
>>
>> - more time efficient (just a single map lookup)
>> - more space efficient (just one hash table)
>> - easier maintenance of consistency (only one map to update)

Honestly, I don't understand your points:

> Agreed, but you don't list the downsides: more complicated code,

Um, where is this code complicated?

> code which
> does two unrelated things with one operation,

The requirement that the cache class must count hits automatically means
that two unrelated things happen in one method: lookup and counting. Or
did you mean something else?

> code in whch the actual values
> have a somewhat obscure relationship with the logical values.

This is completely encapsulated inside the Cache class. And I also do
not see how this is obscure.

Maybe I'm too tired right now to get your point. I'd appreciate it if
you elaborate it a bit more. Or you illustrate your point with another
solution so everyone can compare both of them.

Kind regards

robert

java-programmer >> Retrieve the key from a map (2) Patricia Shanahan wrote:

> /*
> * Created on Aug 14, 2004
> */

Not only highly intelligent but prescient too !

;-)

-- chris

java-programmer >> Retrieve the key from a map (2) Ed wrote:

> > private Map<K, Val<V>> values = new HashMap<K, Val<V>>();
[...]
> One of the more ridiculous reasons I don't like generics: it makes code
> look like a fleet of WW2 bombers droning overhead before they spill
> their deathly loads on me.

You have a vivid imagination...

But I shall happily add this to my own "reasons why generics suck" list.

-- chris