Solved

A custom Map implementation with expiring entries

Posted on 2004-04-05
7
878 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
  • 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 37

Accepted Solution

by:
zzynx earned 300 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Free Alternative to JIRA 4 91
How can I do a Massively massive community reviewing-and-grading site? 7 69
Strange loading of website behaviour 3 32
Problem to start Neon 20 85
For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This video teaches viewers about errors in exception handling.

912 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now