Are there any data structures that preserve the iteration order and also discard old records?

Question

I have a use case when I want to fill records in a data structure from several threads, so it should be thread safe and after reaching a certain size it starts discarding old records. And I also want to iterate over the data structure in the same order as Insertion.

So, I decided to use it Guava Cachehere, but, to my surprise, the Guava method asMap()does not return elements in any particular order.

private final Cache<Integer, Integer> cache =
      CacheBuilder.newBuilder().maximumSize(10)
          .removalListener(
              RemovalListeners.asynchronous(new CustomListener(), executorService)
          ).build();

cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
cache.put(5, 5);
cache.put(6, 6);

for (Entry<Integer, Integer> entry : cache.asMap().entrySet()) {
  System.out.println(entry.getKey() + "=" + entry.getValue());
}

Conclusion:

2=2
6=6
1=1
4=4
3=3
5=5

, , , , , , ?

. Java 7 Java 8.

- , :

1=1
2=2
3=3
4=4
5=5
6=6

Answer 1

Java 7 Caffeine , ConcurrentLinkedHashMap:

ConcurrentMap<Integer, Integer> cache =
        new ConcurrentLinkedHashMap.Builder<Integer, Integer>()
                .maximumWeightedCapacity(10)
                .build();

cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
cache.put(5, 5);
cache.put(6, 6);

for (Entry<Integer, Integer> entry : cache.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

1=1
2=2
3=3
4=4
5=5
6=6

. ExampleUsage · ben-manes/concurrentlinkedhashmap Wiki.

Answer 2

, ,

• queue
• deque
• ..

, , deque, ,

add(element): .

addFirst(element): .

addLast(element): .

offer(element): , , .

offerFirst(element): , .

offerLast(element): , , .

iterator(): deque.

descendingIterator(): , deque.

push(element): .

pop(element): .

removeFirst(): .

removeLast(): .

deque: https://examples.javacodegeeks.com/core-java/util/deque-util/java-util-deque-example/

Answer 3

, put(k, v) , , , .

LikedHashMap, Collection.synchronized, removeEldest. , . , entryRemoved BoundedMap:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Collections;

class BoundedMap<K, V> extends LinkedHashMap<K, V> {
  private final int capacity;

  public BoundedMap(int capacity) {
    this.capacity = capacity;
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest){
    if(size() > capacity) {
      remove(eldest.getKey());
      entryRemoved(eldest);
    }
    return false;
  }

  public void entryRemoved(Map.Entry<K,V> entry) {
  }
}

public class Test {
  public static void main(String[] args) {
    Map<Integer, Integer> m = Collections.synchronizedMap(
      new BoundedMap<Integer, Integer>(5) {
        @Override
        public void entryRemoved(Map.Entry entry) {
          System.out.println(entry);
        }
    });
    System.out.println("--- adding");
    for (int i=0; i<8; i++) {
      m.put(i, -i);
    }
    System.out.println("-- iterating");
    for(Map.Entry<Integer, Integer> entry : m.entrySet()) {
      System.out.println(entry);
    }
  }
}

Answer 4

You can do this with a simple subclass java.util.LinkedHashMapthat overrides removeEldestEntry(), as described in the Javadoc .