Как реализовать параллельный набор, который поддерживает порядок вставки - PullRequest
Новая
       40

Как реализовать параллельный набор, который поддерживает порядок вставки

3 голосов
/ 23 июня 2011


Мне нужна реализация Set, которая позволила бы мне поддерживать порядок вставки и все еще быть изменяемой непрерывно (как в исключении ConcurrentModificationException).

Я пытался использовать ConcurrentSkipListSet с моим собственным компаратором - пример кода: 

public static void main(String[] str){
        ConcurrentSkipListSet set  = new ConcurrentSkipListSet(new Comparator() {

            public int compare(Object o1, Object o2) {
                if(o1.equals(o2)){
                    return 0;
                }
                return -1;
            }
        });
        set.add("d");
        set.add("b");
        set.add("a");
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        set.add("c");
        set.add("b");

        System.out.println(set);
        set.remove("b");
        System.out.println(set);
    }

Но, похоже, этот компаратор #fail, потому что набор выводит:
[b, c, a, b, d]. Его нет, если b там дважды.
Есть ли другие альтернативы, на которые я должен обратить внимание?

Ответы [ 3 ]

3 голосов
/ 23 июня 2011

Вы определили компаратор, который не соответствует свойству total order . Для двух объектов один из них должен быть меньше другого, а другой - меньше первого.

В вашем случае, если объекты не равны, то каждый из них меньше другого.

Поскольку вы создаете экземпляр ConcurrentSkipListSet без каких-либо параметров типа, указывающих тип элементов в коллекции, у вас будут проблемы с определением компаратора, если вы не используете приведение. Но если вы создадите new ConcurrentSkipListSet<String>, вам будет легче определить компаратор, так как вы будете знать, что ваши объекты являются строками.

1 голос
/ 24 июня 2011

Вы можете определить компаратор, который будет сохранять порядок вставки строк и использовать его, это будет не красиво, но так как компаратор всегда вызывается для каждого нового элемента, все, что вам нужно сделать, это что-то вроде этого: 

public void testInsertionOrderSkipListSet() {
  Comparator<String> insertionOrderComparator = new Comparator<String>() {

    private final ConcurrentHashMap<String, Integer> order = new ConcurrentHashMap<String, Integer>();
    @Override
    public int compare(String o1, String o2) {
      if (!order.contains(o2)) //only happens on second insert
        order.put(o2, 0);
      if (order.containsKey(o1))
        return order.get(o1).compareTo(order.get(o2));
      order.put(o1, order.size());
      return 1;
    }
  };
  ConcurrentSkipListSet<String> set = new ConcurrentSkipListSet<String>(insertionOrderComparator);

  set.add("a");
  set.add("c");
  set.add("e");
  set.add("b");
  set.add("d");
  set.add("c");
  assertArrayEquals(new String[] { "a", "c", "e", "b", "d"}, set.toArray(new String[]{}));
}

Эй, я сказал, что это было не красиво ...

0 голосов
/ 24 июня 2011

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

class ConcurrentInsertionOrderSet extends ConcurrentSkipListSet{
        Map<Object, Integer> orderMap;
        final AtomicInteger increment = new AtomicInteger();
        public ConcurrentInsertionOrderSet(final Map<Object, Integer> orderMap) {
            super(new Comparator<Object>() {      
                public int compare(Object o1, Object o2) {
                    return (orderMap.get(o1).compareTo(orderMap.get(o2)));
                }
            });
            this.orderMap = orderMap;
        }

        @Override
        public boolean add(Object o) {
            if (!orderMap.containsKey(o)) 
                orderMap.put(o, increment.incrementAndGet());
            return super.add(o);
        }
        @Override
        public boolean remove(Object o) {
            boolean b = super.remove(o);
            if(b)
                orderMap.remove(o);
            return b;
        }
    }

И для теста: 

public static void main(String[] str){
        ConcurrentSkipListSet set  = new ConcurrentInsertionOrderSet(new ConcurrentHashMap());
        set.add("d");
        set.add("b");
        set.add("a");
        set.add("c");
        set.add("b");
        set.add("c");
        set.add("g");
        System.out.println(set);
        set.remove("b");
        System.out.println(set);
        set.remove("c");
        set.add("c");
        System.out.println(set);
    }

Вывод хороший и последовательный:
[д, б, а, с, г]
[д, а, с, г]
[д, а, г, с]

Но я полагаю, что беспокойство @ axel22 по поводу состояния гонки сохраняется.

...