Hàng đợi đảm bảo tính duy nhất của các yếu tố?

Question

Tôi đang tìm kiếm triển khai thực hiện java.util.Queue hoặc một thứ gì đó trong bộ sưu tập của Google hoạt động như một Hàng đợi, nhưng cũng đảm bảo rằng mỗi phần tử của hàng đợi là duy nhất. (tất cả chèn thêm sẽ không có hiệu lực)

Có thể, hoặc tôi sẽ phải làm điều đó bằng tay?

Hiện tại tôi đang sử dụng Hàng đợi, với triển khai LinkedList và tôi kiểm tra tính duy nhất trước khi chèn. (Tôi sử dụng một Bản đồ bên để thực hiện việc này, thêm/xóa phần tử khỏi bản đồ bên trước/sau hàng đợi). Tôi không thích nó quá nhiều.

Mọi đầu vào đều được chào đón. Nếu nó không nằm trong gói java.util, thì có lẽ đó là một ý tưởng tồi?

Answer 1

Làm thế nào về một LinkedHashSet? Trình lặp của nó duy trì thứ tự chèn, nhưng vì nó là một Set, các phần tử của nó là duy nhất.

Là tài liệu hướng dẫn của nó nói,

Lưu ý rằng thứ tự chèn là không bị ảnh hưởng nếu một yếu tố là tái chèn vào các thiết lập.

Để loại bỏ một cách hiệu quả các yếu tố từ người đứng đầu này "đợi", đi qua iterator của nó:

Iterator<?> i = queue.iterator(); 
... 
Object next = i.next(); 
i.remove(); 

Answer 2

Tôi muốn bị giữ lại HashSet chứa khóa xác định duy nhất các mục trong hàng đợi song song với nó. Sau đó, chỉ cần kiểm tra HashSet để xem mục có nằm trong hàng đợi hay không trước khi thêm nó. Khi bạn xóa một mục khỏi Hàng đợi, chỉ cần xóa khóa khỏi HashSet.

Answer 3

này không tồn tại như xa như tôi biết, nhưng sẽ là khá đơn giản để thực hiện sử dụng một LinkedList kết hợp với một Set:

/** 
* Thread unsafe implementation of UniqueQueue. 
*/ 
public class UniqueQueue<T> implements Queue<T> { 
    private final Queue<T> queue = new LinkedList<T>(); 
    private final Set<T> set = new HashSet<T>(); 

    public boolean add(T t) { 
    // Only add element to queue if the set does not contain the specified element. 
    if (set.add(t)) { 
     queue.add(t); 
    } 

    return true; // Must always return true as per API def. 
    } 

    public T remove() throws NoSuchElementException { 
    T ret = queue.remove(); 
    set.remove(ret); 
    return ret; 
    } 

    // TODO: Implement other Queue methods. 
} 

Answer 4

Kiểm tra tính độc đáo dĩ nhiên có một chi phí (hoặc trong không gian hoặc thời gian). Dường như nó có thể là thú vị để làm việc từ một cái gì đó giống như một PriorityQueue mà sẽ duy trì một đống được sắp xếp bởi Comparator của các yếu tố. Bạn có thể tận dụng điều đó để kiểm tra hiệu quả hơn (O (log n)) kiểm tra sự tồn tại mà không cần duy trì một bản đồ bên.

Nếu bạn muốn gói Hàng đợi bằng trình kiểm tra tính duy nhất, tôi thực sự khuyên bạn nên sử dụng Bộ sưu tập của Google ForwardingQueue để tạo một thứ như vậy.

Answer 5

Đây là một câu hỏi rất hay. Không có giải pháp đơn giản nào. Tôi sẽ đào lên một số mã tôi đã viết một lúc trở lại đã cố gắng để làm điều này, và quay trở lại và chỉnh sửa câu trả lời này.

EDIT: Tôi quay lại. Thật vậy, nếu bạn không cần đồng thời, bạn nên duy trì một Hàng đợi và Đặt riêng rẽ. Đối với những gì tôi đã làm, đồng thời là một mục tiêu, nhưng giải pháp tốt nhất tôi có thể đưa ra cho rằng hạn chế là vấn đề; về cơ bản, vì nó sử dụng ConcurrentHashMap, bạn càng loại bỏ phần tử "head" khỏi hàng đợi (một điều cơ bản để làm với một hàng đợi), bảng băm không cân bằng sẽ trở nên theo thời gian. Tôi vẫn có thể chia sẻ mã này với bạn, nhưng tôi nghi ngờ bạn thực sự muốn nó.

EDIT: Đối với trường hợp đồng thời yêu cầu tôi đưa cho câu trả lời này: Concurrent Set Queue

Answer 6

TreeSet. Đó là Tập hợp đã sắp xếp và Set ngụ ý "không có phần tử trùng lặp".

Answer 7

Chỉ cần để hoàn thành Adamski của câu trả lời:

/** 
* A queue that keeps each element only once. 
* If you try to add an element that already exists - nothing will happen. 
* 
* @author Adamski http://stackoverflow.com/a/2319156/827927 
* @NotThreadSafe 
*/ 
public class UniqueQueue<T> implements Queue<T> { 

private final Queue<T> queue = new LinkedList<T>(); 
private final Set<T> set = new HashSet<T>(); 

@Override public boolean add(T t) { 
    // Only add element to queue if the set does not contain the specified element. 
    if (set.add(t)) 
     queue.add(t); 
    return true; // Must always return true as per API def. 
} 

@Override public boolean addAll(Collection<? extends T> arg0) { 
    boolean ret = false; 
    for (T t: arg0) 
     if (set.add(t)) { 
      queue.add(t); 
      ret = true; 
     } 
    return ret; 
} 

@Override public T remove() throws NoSuchElementException { 
    T ret = queue.remove(); 
    set.remove(ret); 
    return ret; 
} 

@Override public boolean remove(Object arg0) { 
    boolean ret = queue.remove(arg0); 
    set.remove(arg0); 
    return ret; 
} 

@Override public boolean removeAll(Collection<?> arg0) { 
    boolean ret = queue.removeAll(arg0); 
    set.removeAll(arg0); 
    return ret; 
} 

@Override public void clear() { 
    set.clear(); 
    queue.clear(); 
} 

@Override public boolean contains(Object arg0) { 
    return set.contains(arg0); 
} 

@Override public boolean containsAll(Collection<?> arg0) { 
    return set.containsAll(arg0); 
} 

@Override public boolean isEmpty() { 
    return set.isEmpty(); 
} 

@Override public Iterator<T> iterator() { 
    return queue.iterator(); 
} 

@Override public boolean retainAll(Collection<?> arg0) { 
    throw new UnsupportedOperationException(); 
} 

@Override public int size() { 
    return queue.size(); 
} 

@Override public Object[] toArray() { 
    return queue.toArray(); 
} 

@Override public <T> T[] toArray(T[] arg0) { 
    return queue.toArray(arg0); 
} 

@Override public T element() { 
    return queue.element(); 
} 

@Override public boolean offer(T e) { 
    return queue.offer(e); 
} 

@Override public T peek() { 
    return queue.peek(); 
} 

@Override public T poll() { 
    return queue.poll(); 
} 
} 

Answer 8

Đáng tiếc là nó không tồn tại. Vì tôi cần một Hàng đợi như vậy, tôi đã phát triển một Hàng đợi Chặn được hỗ trợ bởi một tập hợp, lấy cảm hứng từ java.util.concurrent.LinkedBlockingQueue.

Bạn có thể tìm thấy nó ở đây:

https://github.com/bvanalderweireldt/concurrent-unique-queue

Ví dụ:

final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1); 
queue.offer(new Integer(1)); //True 
queue.offer(new Integer(1)); //False 

Bạn có thể sử dụng nó với Maven:

<dependency> 
    <groupId>com.hybhub</groupId> 
    <artifactId>concurrent-util</artifactId> 
    <version>0.1</version> 
</dependency>