Có triển khai Danh sách không trùng lặp không?

Question

Tôi biết về SortedSet, nhưng trong trường hợp của tôi, tôi cần một cái gì đó triển khai List và không phải Set. Vì vậy, có một thực hiện ra khỏi đó, trong API hoặc ở nơi khác?

Không khó để thực hiện bản thân mình, nhưng tôi đã tìm ra lý do tại sao không hỏi mọi người ở đây trước?

Answer 1

Không có bộ sưu tập Java nào trong thư viện chuẩn để thực hiện việc này. Tuy nhiên, LinkedHashSet<E> giữ nguyên thứ tự tương tự như List, vì vậy nếu bạn quấn bộ của mình thành List khi bạn muốn sử dụng nó làm List bạn sẽ nhận được ngữ nghĩa bạn muốn.

Ngoài ra, Commons Collections (hoặc commons-collections4, cho phiên bản generic) có một List mà làm những gì bạn muốn đã: SetUniqueList/SetUniqueList<E>.

Answer 2

Tại sao không gói gọn một bộ với một danh sách, sắp xếp như sau:

new ArrayList(new LinkedHashSet()) 

này khiến việc thực hiện khác cho những người là một bậc thầy thực sự của bộ sưu tập ;-)

Answer 3

Các documentation for collection interfaces nói:

Đặt - bộ sưu tập không thể chứa các phần tử trùng lặp.
Danh sách - bộ sưu tập được sắp xếp (đôi khi được gọi là chuỗi). Danh sách có thể chứa các phần tử trùng lặp.

Vì vậy, nếu bạn không muốn trùng lặp, có thể bạn không nên sử dụng danh sách.

Answer 4

Tắt đầu của tôi, danh sách cho phép trùng lặp. Bạn có thể nhanh chóng triển khai UniqueArrayList và ghi đè tất cả các chức năng add/insert để kiểm tra trước khi bạn gọi các phương thức được kế thừa. Để sử dụng cá nhân, bạn chỉ có thể thực hiện phương thức add mà bạn sử dụng và ghi đè lên những người khác để ném ngoại lệ trong trường hợp các lập trình viên trong tương lai cố sử dụng danh sách theo cách khác.

Answer 5

Vì vậy, đây là những gì tôi đã làm cuối cùng. Tôi mong điều này giúp được người nào khác.

class NoDuplicatesList<E> extends LinkedList<E> { 
    @Override 
    public boolean add(E e) { 
     if (this.contains(e)) { 
      return false; 
     } 
     else { 
      return super.add(e); 
     } 
    } 

    @Override 
    public boolean addAll(Collection<? extends E> collection) { 
     Collection<E> copy = new LinkedList<E>(collection); 
     copy.removeAll(this); 
     return super.addAll(copy); 
    } 

    @Override 
    public boolean addAll(int index, Collection<? extends E> collection) { 
     Collection<E> copy = new LinkedList<E>(collection); 
     copy.removeAll(this); 
     return super.addAll(index, copy); 
    } 

    @Override 
    public void add(int index, E element) { 
     if (this.contains(element)) { 
      return; 
     } 
     else { 
      super.add(index, element); 
     } 
    } 
} 

Answer 6

Bạn nên nghiêm túc xem xét câu trả lời dhiller của:

1. Thay vì lo lắng về việc thêm các đối tượng thành một danh sách trùng lặp-ít hơn, thêm chúng vào một Set (bất kỳ thực hiện), mà sẽ bằng cách lọc tự nhiên ra các bản sao.
2. Khi bạn cần gọi phương thức yêu cầu Danh sách, hãy bọc nó theo số new ArrayList(set) (hoặc new LinkedList(set), bất cứ điều gì).

Tôi nghĩ rằng giải pháp bạn được đăng với NoDuplicatesList có một số vấn đề, chủ yếu là với phương pháp , cộng với lớp học của bạn không xử lý kiểm tra các bản sao trong bộ sưu tập truyền cho phương pháp addAll() của bạn.

Answer 7

Tôi cần một cái gì đó như vậy, vì vậy tôi đã đi đến bộ sưu tập commons và sử dụng SetUniqueList, nhưng khi tôi chạy một số thử nghiệm hiệu suất, tôi thấy rằng nó có vẻ không được tối ưu hóa so với trường hợp nếu tôi muốn sử dụng một Set và một mảng bằng cách sử dụng phương thức Set.toArray(), SetUniqueTest mất 20: 1 thời gian để điền và sau đó đi qua 100.000 chuỗi so với triển khai khác, đó là một sự khác biệt lớn, vì vậy Nếu bạn lo lắng về hiệu suất, tôi khuyên bạn nên sử dụng Set và có được một mảng thay vì sử dụng SetUniqueList, trừ khi bạn thực sự cần logic của SetUniqueList, sau đó bạn cần phải kiểm tra các giải pháp khác ...

việc thử nghiệm phương pháp mã chính:

public static void main (String [] args) {

SetUniqueList pq = SetUniqueList.decorate(new ArrayList()); 
Set s = new TreeSet(); 

long t1 = 0L; 
long t2 = 0L; 
String t; 


t1 = System.nanoTime(); 
for (int i = 0; i < 200000; i++) { 
    pq.add("a" + Math.random()); 
} 
while (!pq.isEmpty()) { 
    t = (String) pq.remove(0); 
} 
t1 = System.nanoTime() - t1; 

t2 = System.nanoTime(); 
for (int i = 0; i < 200000; i++) { 
    s.add("a" + Math.random()); 
} 

s.clear(); 
String[] d = (String[]) s.toArray(new String[0]); 
s.clear(); 
for (int i = 0; i < d.length; i++) { 
    t = d[i]; 

} 
t2 = System.nanoTime() - t2; 

System.out.println((double)t1/1000/1000/1000); //seconds 
System.out.println((double)t2/1000/1000/1000); //seconds 
System.out.println(((double) t1)/t2);  //comparing results 

}

Trân Mohammed Sleem http://abusleem.net/blog

Answer 8

Tôi chỉ cần thực hiện UniqueList của riêng tôi trong thư viện nhỏ cho riêng mình như thế này:

package com.bprog.collections;//my own little set of useful utilities and classes 

import java.util.HashSet; 
import java.util.ArrayList; 
import java.util.List; 
/** 
* 
* @author Jonathan 
*/ 
public class UniqueList { 

private HashSet masterSet = new HashSet(); 
private ArrayList growableUniques; 
private Object[] returnable; 

public UniqueList() { 
    growableUniques = new ArrayList(); 
} 

public UniqueList(int size) { 
    growableUniques = new ArrayList(size); 
} 

public void add(Object thing) { 
    if (!masterSet.contains(thing)) { 
     masterSet.add(thing); 
     growableUniques.add(thing); 
    } 
} 

/** 
* Casts to an ArrayList of unique values 
* @return 
*/ 
public List getList(){ 
    return growableUniques; 
} 

public Object get(int index) { 
    return growableUniques.get(index); 
} 

public Object[] toObjectArray() { 
    int size = growableUniques.size(); 
    returnable = new Object[size]; 
    for (int i = 0; i < size; i++) { 
     returnable[i] = growableUniques.get(i); 
    } 
    return returnable; 
    } 
} 

Tôi có lớp TestCollections trông giống như sau:

package com.bprog.collections; 
import com.bprog.out.Out; 
/** 
* 
* @author Jonathan 
*/ 
public class TestCollections { 
    public static void main(String[] args){ 
     UniqueList ul = new UniqueList(); 
     ul.add("Test"); 
     ul.add("Test"); 
     ul.add("Not a copy"); 
     ul.add("Test"); 
     //should only contain two things 
     Object[] content = ul.toObjectArray(); 
     Out.pl("Array Content",content); 
    } 
} 

Hoạt động tốt. Tất cả nó làm là nó thêm vào một bộ nếu nó không có nó đã có và có một Arraylist đó là trả về, cũng như một mảng đối tượng.

Answer 9

trong phương thức add, tại sao không sử dụng HashSet.add() để kiểm tra trùng lặp thay vì HashSet.consist(). HashSet.add() sẽ trả về true nếu không có trùng lặp và false nếu không.

Answer 10

Đây là những gì tôi đã làm và nó hoạt động.

Giả sử tôi có ArrayList để làm việc với điều đầu tiên tôi làm đã được tạo mới LinkedHashMap.

LinkedHashSet<E> hashSet = new LinkedHashSet<E>() 

Sau đó, tôi cố thêm phần tử mới vào LinkedHashSet. Phương thức thêm không thay đổi LinkedHasSet và trả về false nếu phần tử mới trùng lặp. Vì vậy, điều này trở thành một điều kiện tôi có thể kiểm tra trước khi thêm vào ArrayList.

if (hashSet.add(E)) arrayList.add(E); 

Đây là cách đơn giản và thanh lịch để ngăn trùng lặp được thêm vào danh sách mảng. Nếu bạn muốn, bạn có thể gói gọn và ghi đè phương thức thêm vào trong một lớp mở rộng ArrayList. Chỉ cần nhớ xử lý addAll bằng cách lặp qua các phần tử và gọi phương thức thêm.

Answer 11

LƯU Ý: không mất danh sách phụ thực hiện.

import java.util.ArrayList; 
import java.util.Collection; 
import java.util.HashSet; 
import java.util.Set; 

public class UniqueList<T> extends ArrayList<T> { 

    private static final long serialVersionUID = 1L; 

    /** Unique elements SET */ 
    private final Set<T> set=new HashSet(); 

    /** Used by addAll methods */ 
    private Collection<T> addUnique(Collection<? extends T> col) { 
     Collection<T> unique=new ArrayList(); 
     for(T e: col){ 
      if (set.add(e)) unique.add(e); 
     } 
     return unique; 
    } 

    @Override 
    public boolean add(T e) { 
     return set.add(e) ? super.add(e) : false; 
    } 

    @Override 
    public boolean addAll(Collection<? extends T> col) { 
     return super.addAll(addUnique(col)); 
    } 

    @Override 
    public void add(int index, T e) { 
     if (set.add(e)) super.add(index, e); 
    } 

    @Override 
    public boolean addAll(int index, Collection<? extends T> col) { 
     return super.addAll(index, addUnique(col)); 
    } 

}