retrieve the key from a map

[ralf]

Hi everyone,

I want to retrieve a key from a map, and I don't find a way to do this.
For instance there is the following code:

HashMap m = new HashMap();
String key = new String("k");
m.put(key, "v");

Later I don't have any reference to "key" anymore, other than the
reference in the map. But I know, the string is "k". I want to retrieve
the instance that is the key in the map.

Any ideas?
Ralf.

 

[M.J. Dance]

Hi everyone,

I want to retrieve a key from a map, and I don't find a way to do this.
For instance there is the following code:

HashMap m = new HashMap();
String key = new String("k");
m.put(key, "v");

Later I don't have any reference to "key" anymore, other than the
reference in the map. But I know, the string is "k". I want to retrieve
the instance that is the key in the map.

Any ideas?
Ralf.

Unless you're using IdentityHashMap (or some other special-purpose
implementation of Map), knowing that 'the string is "k"' should be enough.
Otherwise use m.keySet() and go from there.

 

[Ed]

(e-mail address removed) skrev:

Hi everyone,

I want to retrieve a key from a map, and I don't find a way to do this.

Distasteful, brute-force approach:

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

class Crap {

public static void main(String[] args) {
Map map = new HashMap();
map.put("man", "john");
map.put("woman", "jane");
System.out.println("Key for john is: " +
getKey(map, "john"));
}

private static String getKey(Map map, String value) {
for (Iterator i = map.keySet().iterator(); i.hasNext() {
String key = (String)i.next();
if (map.get(key).equals(value)) {
return key;
}
}
return "No value found";
}
}



..ed

 

[Zaph0d]

...
HashMap m = new HashMap();

The key here is the word "Hash" in HashMap.

A hash algorithm is an algorithm that maps data to a key so that
different data will generate different keys. A good hash algorithm
means that the keys that are generated are uniformly disributed along
the range (int min->int max for example). Also, good hash algorithm
should minimize collisions - two different datas having the same key.

Each Object in java has an overrideable hashCode() method which is
supposed to return the object hash. An Object hash code is its java
reference number ("pointer"). A String hash code is built from the
string (you can see the details in String api docs).

A HashMap stores and retreives according the they "key" object
hashCode(), and then according to equals(). The process is this: 1.
find the "cell" holding all the keys with a specific hashcode. 2.
iterate through these keys using equals() with the key object given. 3.
if equals returns true, do the 'ok' action (overwrite the key/data pair
/ retreive the related data). if no equals returns true, do the 'fail'
action (create a new key/data pair and store it / return null).

Take String for example - String overrides hashcode and equals. String
A equals String B if their characters match. Also, String hashcode is
computed based on the characters. That means that it doesn't matter
which instance of String you used to store the data, you can retrieve
it using a String with the same characters.

If you want to store your own repeateable keys, just build hashCode and
equals according to the repeatable data: same data->same hashcode and
equals=true (doesn't have to hold the other direction, but every
hashcode collision can cost performance).

If you're still confused, please read on Hash maps in a good algorithm
site/book.

 

[ralf]

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.

 

[Patricia Shanahan]

Hi everyone,

I want to retrieve a key from a map, and I don't find a way to do this.
For instance there is the following code:

HashMap m = new HashMap();
String key = new String("k");
m.put(key, "v");

Later I don't have any reference to "key" anymore, other than the
reference in the map. But I know, the string is "k". I want to retrieve
the instance that is the key in the map.

If you know the String is "k", you can find the specific key instance by
getting the keySet, and iterating over it checking for .equals equality
to "k".

If you do this frequently, keep a separate hash map that contains each
key in m as both key and value:

m_keys.put(key,key)

When you want to do the retrieval:

m_keys.get("k")

However, I have my doubts about a design that depends on overriding
..equals in a class, but does not treat instances that equal each other
as being equivalent. Note that two .equals equal instances cannot both
be keys in the map at the same time.

What are you really trying to achieve?

Patricia

 

[Robert Klemme]

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;
}
}

 

[Chris Uppal]

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

 

[Ed]

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

 

[Robert Klemme]

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

 

[Patricia Shanahan]

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

 

[Chris Uppal]

Robert Klemme wrote:

[me:]

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

 

[Matt Humphrey]

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 (e-mail address removed) http://www.iviz.com/

 

[Patricia Shanahan]

Robert Klemme wrote:

[me:]

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;
}
}

}

 

[Robert Klemme]

Robert Klemme wrote:

[me:]

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

 

[Chris Uppal]

/*
* Created on Aug 14, 2004
*/

Not only highly intelligent but prescient too !

;-)

-- chris

 

[Chris Uppal]

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

 

[ralf]

Hi!

Thank you for your ideas. I'd like to summarize it in one mail.

Iterating over keySet is what I meant with "obvious brute force
attack". The map is expected to have quite a lot of entries (could
easily eat up a quarter of all available VM heap memory or so). In
fact, this brute force attack currently used, but of course I want to
have an alternative way.

A separate hashmap is not what I want. Then I have two of such big maps
in memory instead of just one. That hit counter is a small
nice-to-have, which does not justify any significant additional memory
footprint or cpu usage.

Wrapping values into another class is also not an option for the same
reason. This would require one additional object instance for each
cache entry - too expensive for me.

Design - Yes I know, that an equals-method (and hashCode), that does
not cover all member fields of the class (it omits field hits in my
example) is not a nice design. However, all this is deeply buried
within the core of the framework. Neither class Key nor Cache is
publicly visible.

Memory Usage is quite important for me. The map is for caching database
queries across transactions. All objects in the map are there for a
long time, which moves them sooner or later into the old-gen space,
which is subject to expensive full-GCs.

Until recently I solved the problem using commons-collections. The maps
of commons-collections do provide a protected method getEntry(Object
key). Within a subclass I can implement getKey(Object key) with
getEntry(key).getKey(). Java Collections do have that getEntry method
as well, but this is package private, so I cannot access is via
subclassing.

While writing this mail I thought about calling getEntry via
reflection, bypassing the package-private-restriction. Really ugly...


Thank you for responses,
Ralf.

 

[Robert Klemme]

Wrapping values into another class is also not an option for the same
reason. This would require one additional object instance for each
cache entry - too expensive for me.

But the same is true for your approach of putting the counter into the
key class (unless I am missing something). Memory wise it does not
matter whether you wrap the key or the value. And if your basic key is
a String for example, then you have an instance of your class Key which
holds this string (=> 1 additional instance). There might be other
aspects of your code that you did not exhibit yet.

Design - Yes I know, that an equals-method (and hashCode), that does
not cover all member fields of the class (it omits field hits in my
example) is not a nice design. However, all this is deeply buried
within the core of the framework. Neither class Key nor Cache is
publicly visible.

Even then you should care about design. Someone will have to maintain
this X months from now and he / she will be thankful if you do.

Memory Usage is quite important for me. The map is for caching database
queries across transactions. All objects in the map are there for a
long time, which moves them sooner or later into the old-gen space,
which is subject to expensive full-GCs.

Is it caching queries or query results? Also, if it's query results,
why do you have to cache them across transactions? This might lead to
inconsistencies.

Kind regards

robert

 

[Chris Uppal]

Until recently I solved the problem using commons-collections. The maps
of commons-collections do provide a protected method getEntry(Object
key). Within a subclass I can implement getKey(Object key) with
getEntry(key).getKey(). Java Collections do have that getEntry method
as well, but this is package private, so I cannot access is via
subclassing.

If your application is such that you have to consider memory use so carefully,
then it is is certainly worth your while creating your own implementation of
Map which has all the features you need and lacks ones you don't. (E.g you
probably wouldn't want the object count overhead of using the Entry objects,
but would just have two or three parallel arrays to hold keys, values, and
counts).

-- chris