Существуют ли какие-либо структуры данных, которые сохраняют порядок итераций, а также отбрасывают старые записи?

Question

У меня есть прецедент, когда я хочу заполнять записи в структуре данных из нескольких потоков, поэтому он должен быть потокобезопасным и после достижения определенного размера начинает отбрасывать старые записи. И я также хочу перебрать структуру данных в том же порядке, что и Insertion.

Итак, я решил использовать Guava Cache, но, к моему удивлению, метод Guava asMap() не возвращает элементы в каком-либо конкретном порядке.

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()); 
} 

Выход:

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

общие структуры данных, сохраняющее порядок итерации являются

• очередь
• deque
• связанный список и т. Д.

однако, решение, которое наилучшим образом соответствует вашим потребностям будет использовать Deque, который предлагает несколько встроенных функций, таких как,

add(element): Добавляет элемент в хвост.

addFirst(element): Добавляет элемент в голову.

addLast(element): Добавляет элемент в хвост.

offer(element): Добавляет элемент в хвост и возвращает логическое значение, чтобы объяснить, была ли вставка успешной.

offerFirst(element): Добавляет элемент в голову и возвращает логическое значение в , если вставка прошла успешно.

offerLast(element): Добавляет элемент в хвост и возвращает логическое значение, чтобы объяснить, была ли вставка успешной.

iterator(): Returna итератор для этого deque.

descendingIterator(): Возвращает итератор, имеющий обратный порядок для этого дека.

push(element): Добавляет элемент в голову.

pop(element): Удаляет элемент из головы и возвращает его.

removeFirst(): Удаляет элемент по головке.

removeLast(): Удаляет элемент у хвоста.

Более подробную информацию о дека: https://examples.javacodegeeks.com/core-java/util/deque-util/java-util-deque-example/

Answer 2

Учитывая, что вы показываете 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 3

Вы можете сделать это с помощью простого подкласса java.util.LinkedHashMap, отменяющий removeEldestEntry(), как описано в его Javadoc ,

Answer 4

Для Java 7 вы можете использовать Caffeine «s предшественника 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 для более подробной информации.