Solved

A custom Map implementation with expiring entries

Posted on 2004-04-05
7
872 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
Comment Utility
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
Comment Utility
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
Comment Utility
OK, let's see what you've got.
0
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

 
LVL 37

Accepted Solution

by:
zzynx earned 300 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Thank you for accepting. :°)
This keeps us answering your future questions too.
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

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)
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 will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
The viewer will learn how to implement Singleton Design Pattern in Java.

772 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

14 Experts available now in Live!

Get 1:1 Help Now