Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 932
  • Last Modified:

A custom Map implementation with expiring entries

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
oucher
Asked:
oucher
  • 6
1 Solution
 
zzynxSoftware engineerCommented:
I'm willing to provide you the (tested) code if you're willing to increment the points to 300
0
 
zzynxSoftware engineerCommented:
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
 
oucherAuthor Commented:
OK, let's see what you've got.
0
Industry Leaders: 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!

 
zzynxSoftware engineerCommented:
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
 
zzynxSoftware engineerCommented:
As you saw in my test code, I performed sleeps between inserts/gets.
Otherwise you have "equal" stamps
0
 
zzynxSoftware engineerCommented:
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
 
zzynxSoftware engineerCommented:
Thank you for accepting. :°)
This keeps us answering your future questions too.
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 6
Tackle projects and never again get stuck behind a technical roadblock.
Join Now