Solved

A custom Map implementation with expiring entries

Posted on 2004-04-05
7
892 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
Independent Software Vendors: 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!

 
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

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!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Why my table column Id is not passed to java object? 4 46
null output 3 42
Java: The Public Class Main 4 45
Chrome and Firefox Java 5 67
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…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

763 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