Структура данных Java

Question

Я ищу структуру данных, которая будет действовать как очередь, чтобы я мог иметь поведение «первым пришел - первым вышел», но в идеале я бы также мог видеть, существует ли элемент в этой очереди в постоянное время, как вы можете делать с HashMap, а не с линейным временем, которое вы получаете с LinkedList.

Я думал, что LinkedHashMap мог бы сделать эту работу, но хотя я мог бы сделать итератор и просто взять и затем удалить первый элемент итерации, чтобы создать метод poll (), мне интересно, есть ли лучший способ.

Большое спасибо заранее

Answer 1

Я не знаю, есть ли что-то там, но вы могли бы легко создать составной объект, состоящий из Queue и HashSet.Все операции модификации должны выполняться в обеих коллекциях одновременно, чтобы поддерживать их синхронизацию.Затем вы можете использовать набор для поиска, который должен быть очень быстрым.

Answer 2

Часто, когда вам нужно поведение двух коллекций, вам нужно поддерживать две коллекции.Простой подход состоит в том, чтобы иметь Очередь и HashSet, и всегда выполнять добавление к обоим и удалять из HashMap при удалении из Очереди.

Альтернативой является использование LinkedHashSet.Это сохраняет элементы порядка, которые были добавлены, и вы можете каждый раз удалять первый / самый старый элемент.

Третьим вариантом является использование только очереди.Хотя вам может потребоваться время поиска O (1), вы можете обнаружить, что оно достаточно быстрое, чтобы удовлетворить ваши требования, просто выполнив поиск по каждому элементу.Это может быть намного быстрее, чем вы ожидаете.т.е. 1000 элементов должны быть меньше 10 микросекунд.

РЕДАКТИРОВАТЬ: я согласен, что две коллекции лучше, когда вы не знаете длину.

Однако, чтобы показать вам поиск грубой силытоже может быть быстрымСамый медленный объект для поиска - это тот, которого там нет.(Так как он должен сравнивать каждый элемент)

Queue<Point> points = new ArrayBlockingQueue<Point>(1024);
for(int i=0;i<1000;i++)
  points.add(new Point(i,i));
Point missing = new Point(-1, -1);
int runs = 100 * 1000;
long start = System.nanoTime();
for(int i=0;i< runs;i++)
    points.contains(missing);
long time = System.nanoTime() - start;
System.out.printf("Average contains() took %.1f us%n", time/runs/1000.0);

Prints

Average contains() took 5.1 us

Возможно, вам придется проверить это для вашего типа данных, так как времена равных () и размеры очереди могут варьироваться, но вы можете быть удивлены тем, что вы можете сделать за 10 микросекунд, и это может быть достаточно быстрым.