CODEWITHSUNDEEP
javadictionarydata-structures
Kshitij Roshan
Kshitij Roshan

Reputation: 31

retrieve last n items from map of items java

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.

Upvotes: 3

Views: 1916

Answers (3)

LuCio
LuCio

Reputation: 5173

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.

Upvotes: 1

suvojit_007
suvojit_007

Reputation: 1728

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.

Upvotes: 2

Joschy
Joschy

Reputation: 36

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.

Upvotes: 1

Related Questions