Java - конкретная структура данных

Question

мне нужно выполнить следующие операции:

(1) проверить, если элементы существуют в O (1)

(2) добавить в O (1)

(3) удалить и вернуть в O (1)

Я думал о Set в java, но поддерживает только (1) и (2). Я знаю, что можно сделать что-то вроде этого set.iterator().next() и set.iterator().remove(), но в чем сложность этого решения?

EDIT

Я хочу что-то вроде этого:

Set<Integer> remaining = new HashSet<>(); 

// add values 

Queue<Integer> queue = new ArrayDeque<>(); 

while(!remaining.isEmpty()) { 
    int val = remaining.iterator().next(); // !!! 
    remaining.iterator().remove();   // !!! 
    queue.add(val); 

    while(!queue.isEmpty()) { 

     List<Integer> valuesToBeRemoved = getValues(); 
     // some logic 
     for(int value : valuesToBeRemoved) { 
       remaining.remove(value); 
     } 

    } 


} 

и мне интересно, если строки, помеченные // !!! являются оптимальными

Answer 1

HashSet имеет характеристики O (1) для add(E e) и contains(E e). Для того, чтобы получить какой-либо старый элемент из (и удалить его), вы можете написать

Iterator<Integer> i = set.iterator(); 
int a = i.next(); 
i.remove(); 

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

Если вы используете LinkedHashSet, а не HashSet, вы получите аналогичные показатели для add() и , но i.next() быстрее, потому что LinkedHashSet сохраняет ссылку на первый элемент. В общем, гораздо быстрее перебирать LinkedHashSet, чем HashSet, потому что вам просто нужно следовать цепочке ссылок. Обратите внимание, однако, что LinkedHashSet будет использовать больше памяти, чем HashSet, но если это ваша скорость, вас интересует, LinkedHashSet - хороший ответ.