如何在列表中添加新的唯一元素

Question

我有一個100000個對象列表。它的獨特名單。我想要添加一個新的對象。但是要添加的條件是它應該是唯一的含義，如果新元素已經在列表中，不應該添加到列表中並且應該拋出異常。請讓我知道是否有想法。

Answer 1

您可以使用一套，它只包含唯一的結果http://docs.oracle.com/javase/7/docs/api/java/util/Set.html。

感謝

Answer 2

你還是使用Set而List。

但是，儘管你可以得到它 -

List<Object> list =...; 
public boolean add(Object obj){ 
    Set<Object> set = new HashSet<>(list); 
    return set.add(obj); 
} 

Answer 3

您需要使用Set數據結構爲您的要求。但是，如果您嘗試添加新的重複項，它不會引發異常。

如果你已經有名單，那麼你可以使用

Set<YourType> foo = new HashSet<YourType>(yourList); 

Answer 4

使用Set，而不是List創建Set。如果你真的想要一個List，請考慮下面的例子。

List<String> myList=new ArrayList<>(); 
    myList.add("asd"); 
    myList.add("asf"); 
    myList.add("asf"); 
    Set<String> set=new HashSet<>(); 
    set.addAll(myList); 
    set.add("newString"); 
    myList.clear(); 
    myList.addAll(set); 

Answer 5

如果插入順序是重要的，使用LinkedHashSet代替，這基本上是一組，但也跟蹤一個列表內的元件，以允許迭代過以相同的順序中的元素，因爲它們插入（與列表）。

至於例外嘗試添加重複的元素時，你可以檢查，如果被驗證添加的元素，該add(..)方法返回true並拋出一個Exception否則，或通過創建一個專門的子類，做這個檢查：

public class UniqueItemList <E> extends LinkedHashSet<E> { 

    @Override 
    public boolean add (E e) { 
     checkContains(e); 
     return super.add(e); 
    }; 

    @Override 
    public boolean addAll (Collection<? extends E> collection) { 
     for (E e : collection) { 
      add(e); 
     } 
     return !collection.isEmpty(); 
    } 

    private void checkContains (E e) { 
     if (contains(e)) { 
      throw new IllegalArgumentException("Element was already added"); 
     } 
    } 
} 

Answer 6

如果你有一個很好的理由使用List，例如，因爲爲了事宜你，只是用contains檢查您要添加的元素是否已在列表中：

public void addUnique(Object element) throws NotUniqueException { 
    if (list.contains(element)) { 
     throw new NotUniqueException(list, element); 
    } else { 
     list.add(element); 
    } 
} 

但是，對於100,000個對象，contains會很慢，因爲它必須執行線性搜索。

另一種方法是如果您的列表按照某種自然順序存儲對象，例如，可以用java.util.Comparator來描述的訂單。在這種情況下，而不是使用contains，你可以使用二進制搜索，以減少從O（n）與澳搜索（的log（n））：

public void addUnique(Object element) throws NotUniqueException { 
    int index = Collections.binarySearch(list, element, comparator); 
    if (index >= 0) { 
     throw new NotUniqueException(list, element); 
    } else { 
     list.add(index, element); 
    } 
} 

但是，缺點是您add現在變得更加昂貴，因爲爲了保持列表排序，必須移動一些元素以爲新元素騰出空間。這使得你的add是一個線性操作。

一個數據結構，爲您提供訂單和快速contains和快速add是一個排序樹，所以你可能想要評估這是否是一個選項。

最後，你可以用List結合了Set，即存儲在這兩個的每一個元素：一組爲您提供了快速contains而列表保留元素的順序。通過這種方法，你不僅限於由Comparator定義的順序，但你可以簡單地使用插入的順序：

public void addUnique(Object element) throws NotUniqueException { 
    if (set.contains(element)) { 
     throw new NotUniqueException(list, element); 
    } else { 
     list.add(element); 
     set.add(element); 
    } 
} 

這基本上就是LinkedHashSet爲你做 - 也看到彼得瓦爾澤的答案。