How to use hash map to store values of function.

[Sanny]

I read somwewhere to get efficiency we can record the output of
punction in a table and when the function is called we just search the
table. If our Values are found in it we can directly get the result
from the stored table.

If the value is not present we can call the function and store the
result in the Table for future needs.

Anyone knows how to implement it.

My function is Something like

function int getcarvalue(String carname, int Modelnumber, String
cartime){


}

Here I want to store the return value in Hash Map Such that I can get
values directly by searching the Table.

In this function if cartime > currentcartimevalue then we can reuse
the function. It is not needed that cartime should match.

Only String carname, int Modelnumber should Match. if cartime >
currentcartimevalue We can reuse the function value without any
problem.


I have to store 1 Million such records, So will finding values from
Hashp Map Table faster than using the function directly?

Bye
Sanny

 

[GArlington]

I read somwewhere to get efficiency we can record the output of
punction in a table and when the function is called we just search the
table. If our Values are found in it we can directly get the result
from the stored table.

If the value is not present we can call the function and store the
result in the Table for future needs.

Anyone knows how to implement it.

My function is Something like

function int getcarvalue(String carname, int Modelnumber, String
cartime){

}

As you do not show the code in the function it is hard to say if your
Hashmap lookup is going to be faster.

Here I want to store the return value in Hash Map Such that I can get
values directly by searching the Table.

Is your function querying the DB to get the value? Still it is hard to
say if your Hashmap lookup is going to be faster because most DB
drivers will cache at least some (most commonly used) queries - your
implementation might end up being slower than theirs.

In this function if cartime > currentcartimevalue then we can reuse
the function. It is not needed that cartime should match.

Only String carname, int Modelnumber should Match.

Use Hash of both values to create a key for your Hashmap.

if cartime > currentcartimevalue We can reuse the function value without any
problem.

You will have to retrieve the value from the Hashmap to compare the
timestamp to current time and then depending on that comparison maybe
call the function anyway.

I have to store 1 Million such records, So will finding values from
Hashp Map Table faster than using the function directly?

As I said before, it depends on implementation and DB caching
settings...

 

[Roedy Green]

function int getcarvalue(String carname, int Modelnumber, String
cartime){

The trickiest part (but amounts to only 3 lines of code) is computing
a hashCode function that mashes together carname, modelNumber and
cartime. See http://mindprod.com/jgloss/hashcode.html for how.

You create a tiny class called CarId which has three fields carname,
modelnumber and cartime. This is your Key both to file and lookup
cached results.

The value of the hashmap is the carvalue wrapped in an Integer.

Before you compute a value, you look up in the hashmap a CarID. If
there is nothing you comput the value and file it by carID in the
hashmap.

If you do find it you return the value instead and avoid the
presumably costly computation or web lookup function.

See http://mindprod.com/jgloss/hashmap.html

This cache might balloon and use so much RAM that it detracts from
performance. If that happens, there are many things you can do.

1. weak references. see http://mindprod.com/jgloss/weakreferences

2. LRU logic. You enchain intems, and when the cache gets too big you
chop the least recently used. The overhead is remarkably low. Every
time you lookup, move that element to the head of the chain.

3. pruning. You timestamp or usage mark entries and periodically go
through them all and prune ones not used much recently.


PS. Caching only makes sense if:

1. the computation of carvalue is a bottleneck.

2. the computation of carvalue takes longer than filing and looking up
cache.

3. you get mostly repeats.

 

[Lew]

Use Hash of both values to create a key for your Hashmap.

In addition to GArlington's good advice, you might want an entity class to
represent your "primary key" information, in this case the tuple (carname,
Modelnumber). We'll change those names, now, to match Java coding
conventions, camel case with lower-case first letter for methods and
variables, upper-case first letter for classes, etc.:

public class Key
{
private final String carName;
private final Integer model;

private final transient int hash;

public Key( String car, Integer mod )
{
if ( car == null || mod == null )
{
throw new IllegalArgumentException(
new NullPointerException(
"null key" ));
}
this.carName = car;
this.model = mod;
assert this.carName != null && this.model != null;

hash = carName.hashCode() * 31 + model.hashCode();
}
public final String getCarName() { return carName; }
public final Integer getModel() { return model; }
@Override public boolean equals( Object o )
{
if ( ! getClass().isInstance( o ))
{ return false; }
Key ok = (Key) o;
return (carName.equals( ok.carName )
&& model.equals( ok.model ));
}
@Override public int hashCode()
{
return hash;
}
}

Make your Map a Map < Key, CarValue >.

Key is amenable to serialization, with the caveat that you need to make a
defensive copy on the read from the stream. This will regenerate the
transient hash cache.

Key is amenable to genericization if you make it Key <T>, and make model type
T. Change the variable 'carName' to 'name'. If T is mutable you will need to
make an immutable copy of the constructor argument. Defensive copy on
deserialization becomes even more important.

JPA frameworks and the like, such as Hibernate and OpenJPA, are a lot like this.

A full-blown entity class will sport dependent attributes keyed by the primary
key component. So the whole entity class will comprise a Key component /and/
the Value class component:

public class Entity <K, V>
{
private final Key<K> key;
private V value;
public Entity( K k, V v )
{ // standard check for null key
key = k;
value = v; // null allowed
}
// etc.
}

Now your map is Map < K, Entity < K, V >>.

In a database the key is represented by the key columns, and the value by the
dependent columns in a table. Either type K or V may represent tuples of
other typed attributes.

 

[bugbear]

I read somwewhere to get efficiency we can record the output of
punction in a table and when the function is called we just search the
table. If our Values are found in it we can directly get the result
from the stored table. ..
..
..
I have to store 1 Million such records, So will finding values from
Hashp Map Table faster than using the function directly?

Depends on the speed of the function, and the amount of RAM you have, and
the efficiency and coverage of your hash function.

BugBear

 

[bugbear]

I read somwewhere to get efficiency we can record the output of
punction in a table and when the function is called we just search the
table. If our Values are found in it we can directly get the result
from the stored table.

Most of the relevant issues were explained in the thread
on evaluating sin()

BugBear

 

[Roedy Green]

private final transient int hash;

if you make your hash transient you have to write some code to
recompute it on reconstitution.

See http://mindprod.com/jgloss/serialization.html#TRANSIENT

If you are going to serialise these beasts, which I don't think would
be likely, you need to say implements Serializable.

 

[Lew]

if you make your hash transient you have to write some code to
recompute it on reconstitution.

See http://mindprod.com/jgloss/serialization.html#TRANSIENT

If you are going to serialise these beasts, which I don't think would
be likely, you need to say implements Serializable.

Correct on both counts, though I disagree that serialization is not a likely
need in the example. The Key class as presented is a prime candidate for
serialization. Its whole presentation was intended to provide a basis for
"full-blown entity classes" as one would find with Hibernate or JPA generally.
It is natural, and helpful for some systems like Apache OpenJPA, to make
entity classes serializable.

I declared the instance variables transient without making the class
Serializable so I could make the point in that post about how one would go
about serializing it. You'll note the comments at the bottom that were hints
about where one would go past the Key class as presented. Obviously in a
Usenet post one can only hope to outline the groundwork, not lay out a
complete working application.