retrieve last n items from map of items java

Question

I have a map and I would like to retrieve the last 50 items inserted onto the map or items added to the map in the last 2 seconds (whichever greater) ..

What's the most efficient way I can do that?

Map<Date, Book> books = new HashMap<Date, Book>();

Notes: - I want to maximize throughput and minimize latency. - I want to run on the JVM and minimize heap footprint.

You can make use of TreeMap or similar data structure that keeps the order. — zenwraight, Oct 11 '18 at 18:46
And if you are building an application, I would recommend storing all the data into db and run a query to fetch data either by date or last 50 items. — zenwraight, Oct 11 '18 at 18:47
TreeMap maintains order in sorted order but I want to maintain last insertion order.. — Kshitij Roshan, Oct 11 '18 at 18:50
And you have to do it using only hashmap or u can use some other data structure also ? — zenwraight, Oct 11 '18 at 18:50
@zenwraight, TreeMap would not preserve insertion order and LinkedHashMap will preserve the order but in this case, I think stack would be a better option to store the keys. — suvojit_007, Oct 11 '18 at 18:52
@KshitijRoshan as mentioned in the answer, I feel Stack will do ur work , or Queue, something around that line. — zenwraight, Oct 11 '18 at 18:53
_last 50 items_ - Do you mean last by `Date`, the key of `Map book`? — LuCio, Oct 11 '18 at 18:54
This may be related: https://stackoverflow.com/questions/3527216/accessing-the-last-entry-in-a-map — Brandon G, Oct 11 '18 at 18:56
I would highly recommend using a Priority queue. Pass your comparator object to the queue which sorts the books by date and then filter out the dequeued objects by the time constraint. — shark1608, Oct 11 '18 at 19:08
I want to maximize throughput and minimize latency.I want to run on the JVM and minimize heap footprint. — Kshitij Roshan, Oct 11 '18 at 19:12
Yes! The keys can be anything though, I assigned date as the keys as it made more sense to me.. — Kshitij Roshan, Oct 11 '18 at 20:16

suvojit_007 · Answer 1 · 2018-10-11T19:01:19.900

2

Use a stack to store the Date and then pop items as a key from the stack. Just push Date as key whenever you make an entry in HashMap.

edited Oct 11 '18 at 19:01

answered Oct 11 '18 at 18:45

suvojit_007

1,690
2
17
23

I want to maximize throughput and minimize latency.I want to run on the JVM and minimize heap footprint. – Kshitij Roshan Oct 11 '18 at 19:12
@KshitijRoshan push and pop operation are very much efficient in Stack so I think you should use Stack in this case. – suvojit_007 Oct 12 '18 at 10:43
1

`Stack` is deprecated (since long ago). Use an `ArrayDeque` instead – fps Oct 12 '18 at 15:01
@FedericoPeraltaSchaffner `LinkedList` can be used too. – suvojit_007 Oct 12 '18 at 15:09
@suvojit_007 Agreed. It can be used too, it's a matter of preference. I think `ArrayDeque` is better for most cases, but in this particular case, `LinkedList` would do the job. – fps Oct 12 '18 at 15:11

score 1 · Answer 2 · answered Oct 11 '18 at 18:55

To answer your question in one sentence:

Per default, Maps don't have a last entry, it's not part of their contract. A (Hash)Map Stores the items memory optimized.

Possible Solutions Sorted Maps:

You can access the last entry through the lastEntry method:

NavigableMap<String,Integer> map = new TreeMap<String, Integer>();
// add some entries
Entry<String, Integer> lastEntry = map.lastEntry();

Or u use a Linked map:

Map<String,String> map = new LinkedHashMap<String, Integer>();
// add some entries
List<Entry<String,Integer>> entryList =
    new ArrayList<Map.Entry<String, Integer>>(map.entrySet());
Entry<String, Integer> lastEntry =
    entryList.get(entryList.size()-1);

both are native Java libs.

`TreeMap.lastEntry()` gives the entry with the largest/smallest key value. Iterating a `LinkedHashMap` backwards should do the trick. — Mick Mnemonic, Oct 11 '18 at 19:33

LuCio · Answer 3 · 2018-10-11T20:39:18.270

Since you want to get last items by date, thus the key of the Map<Date, Book> books you can do the following:

  protected static List<Book> getLastXBooks(Map<Date, Book> books, int x) {
    return books.entrySet().stream()
      .sorted(Comparator.<Entry<Date, Book>, Date> comparing(Entry::getKey).reversed())
      .limit(x)
      .map(Entry::getValue)
      .collect(Collectors.toList());
  }

  protected static List<Book> getBooksOfLastXSeconds(Map<Date, Book> books, int seconds) {
    long now = System.currentTimeMillis();
    long msAgo = System.currentTimeMillis() - seconds * 1000;
    return books.entrySet().stream()
      .filter(e -> e.getKey().getTime() <= now && e.getKey().getTime() >= msAgo)
      .sorted(Comparator.<Entry<Date, Book>, Date> comparing(Entry::getKey).reversed())
      .map(Entry::getValue)
      .collect(Collectors.toList());
  }

In getBooksOfLastXSeconds I added the sorting to make the result easy to compare. As of the question it isn't necessary.

Let's have an example:

  public static void main(String[] args) {
    Map<Date, Book> books = new HashMap<Date, Book>();
    for (int i = 0; i < 100; i++) {
      Book book = new Book("Book " + (100 - i));
      books.put(new Date(System.currentTimeMillis() - i * 100), book);
      System.out.println(book);
    }
    List<Book> last50 = getLastXBooks(books, 50);
    System.out.println(last50); // [Book: Book 100, Book: Book 99, ... Book 51, Book: Book 50]
    List<Book> booksOfLast2Seconds = getBooksOfLastXSeconds(books, 2);
    System.out.println(booksOfLast2Seconds); // [Book: Book 100, Book: Book 99, ... Book 82, Book: Book 81]
  }

EDIT
What's the most efficient way I can do that?
The most efficient way would be, to have the books already ordered by insertion date. Then it's not necessary to compare all books (do the sort above) to get the last 50 books. You could use a LinkedHashMap to preserve the insertion order. The insertion order has to be the natural order of Date thus the chronological order.

I want to maximize throughput and minimize latency.I want to run on the JVM and minimize heap footprint. — Kshitij Roshan, Oct 11 '18 at 19:12

retrieve last n items from map of items java

3 Answers3