Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

A custom Map implementation with expiring entries

Posted on 2004-04-05
7
Medium Priority
?
924 Views
Last Modified: 2008-03-04
How would you write an efficient Map implementation that works just like HashMap, except for the following rules?

1) It only allows a maximum number of entries, specified at creation, at any time.
2) An entry is marked with the current timestamp when it is accessed with .get(), but without modifying the entry object in any way (i.e. this Map must still be able to contain any kind of Object).
3) When the map is full and another entry is added with .put(), the entry with the oldest timestamp is first dropped.

0
Comment
Question by:oucher
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
7 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 10758073
I'm willing to provide you the (tested) code if you're willing to increment the points to 300
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10758153
This is the test code

        MyMap map = new MyMap(3);
        map.put( new Integer(1), "One");
        try { Thread.sleep(1000); } catch (java.lang.InterruptedException ex) { }
        System.out.println(map);
        map.put( new Integer(2), "Two");
        try { Thread.sleep(1000); } catch (java.lang.InterruptedException ex) { }
        System.out.println(map);
        map.put( new Integer(3), "Three");
        try { Thread.sleep(1000); } catch (java.lang.InterruptedException ex) { }
        System.out.println(map);
        map.put( new Integer(4), "Four");
        try { Thread.sleep(1000); } catch (java.lang.InterruptedException ex) { }
       
        System.out.println(map);
        System.out.println(map.get(new Integer(3)));
        try { Thread.sleep(1000); } catch (java.lang.InterruptedException ex) { }
        System.out.println(map.get(new Integer(4)));
        try { Thread.sleep(1000); } catch (java.lang.InterruptedException ex) { }
        System.out.println(map);
        map.put( new Integer(5), "Five");
        System.out.println(map);

This is the ouput

key=1 value=One date=Mon Apr 05 17:28:31 CEST 2004

key=2 value=Two date=Mon Apr 05 17:28:32 CEST 2004
key=1 value=One date=Mon Apr 05 17:28:31 CEST 2004

key=2 value=Two date=Mon Apr 05 17:28:32 CEST 2004
key=1 value=One date=Mon Apr 05 17:28:31 CEST 2004
key=3 value=Three date=Mon Apr 05 17:28:33 CEST 2004

key=2 value=Two date=Mon Apr 05 17:28:32 CEST 2004
key=4 value=Four date=Mon Apr 05 17:28:34 CEST 2004
key=3 value=Three date=Mon Apr 05 17:28:33 CEST 2004

Three
Four
key=2 value=Two date=Mon Apr 05 17:28:32 CEST 2004
key=4 value=Four date=Mon Apr 05 17:28:36 CEST 2004
key=3 value=Three date=Mon Apr 05 17:28:35 CEST 2004

key=4 value=Four date=Mon Apr 05 17:28:36 CEST 2004
key=3 value=Three date=Mon Apr 05 17:28:35 CEST 2004
key=5 value=Five date=Mon Apr 05 17:28:37 CEST 2004
0
 

Author Comment

by:oucher
ID: 10767935
OK, let's see what you've got.
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 37

Accepted Solution

by:
zzynx earned 1200 total points
ID: 10772279
Sorry, I didn't saw it quicker.
Anyway, here it is:

import java.util.*;

public class MyMap extends HashMap {

  int maxCap = 15; // default value
  Map mapDateKey = new HashMap();
  List theDates = new ArrayList();

  public class MyInfo {
     Object object = null;
     Date   stamp = null;
     public MyInfo(Object theObject) {
        object = theObject;
        setStamp();
     }
     public Date getStamp() { return stamp; }
     public Object getObject() { return object; }
     public void setStamp() { stamp = new Date(); }
  }

  public MyMap() {
     super();
  }

  public MyMap(int maxCapacity) {
     super();
     maxCap = maxCapacity;
  }

  public Object put(Object key, Object value) {
     if ( size()==maxCap ) {
       Collections.sort(theDates);
       Date oldestDate = (Date) theDates.get(0);
       Object oldKey = mapDateKey.get(oldestDate);
       remove(oldKey);
     }
     MyInfo m = new MyInfo(value);
     mapDateKey.put(m.getStamp(), key);
     theDates.add(m.getStamp());
     return super.put(key, m);
  }

  public Object remove(Object key) {
      MyInfo m = (MyInfo) super.get(key);
      if (m==null)
          return null;
      theDates.remove(m.getStamp());
      return super.remove(key);
  }
 
  public Object get(Object key) {
     MyInfo m = (MyInfo) super.get(key);
     if (m==null)
         return null;
     m.setStamp();
     return m.getObject();
  }
 
  public String toString() {
     Iterator it = super.keySet().iterator();
     String txt = "";
     while (it.hasNext()) {
         Object key = it.next();
         MyInfo m = (MyInfo) super.get(key);
         txt += ("key="+key + " value=" + m.getObject() + " date=" +m.getStamp() + "\r\n");
     }
     return txt;
  }
}

Success.
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10772287
As you saw in my test code, I performed sleeps between inserts/gets.
Otherwise you have "equal" stamps
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10772355
I did the basic functions.
Of course, you have to provide/overwrite all functions of Map that touch the number of elements,
to keep the help variables theDates & mapDateKey in synch.

e.g. if you need to call clear() you have to overwrite it with:
(Remark: be careful, you can call clear() on MyMap and at first sight it will work,
               but it will only call super.clear() and your help variables - vital for the good working - will get out of synch)

public void clear() {
   super.clear();
   theDates.clear();
   mapDateKey.clear();
}
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10807862
Thank you for accepting. :°)
This keeps us answering your future questions too.
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
Suggested Courses

610 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question