Java HashSet的Removals()方法註意事項

Posted on by

前言

我有一個集合，實際上是一個HashSet。我想從中刪除一些item…其中許多item可能不存在。事實上，在我們的測試用例中，“removals”集合中的所有項都不在原始集合中。這聽起來——實際上也是——非常容易編碼。畢竟，我們已經準備好瞭。removeAll來幫助我們，對嗎？

讓我們把它變成一個小測試。我們在命令行上指定“source”set的大小和“removals”集合的大小，並構建它們。source set合隻包含非負整數；刪除集僅包含負整數。我們使用系統測量刪除所有元素所需的時間System.currentTimeMillis()，它不是世界上最精確的秒表，但在這種情況下就足夠瞭，正如您將看到的那樣。

代碼如下：

import java.util.*;
public class Test
{
    public static void main(String[] args)
    {
        int sourceSize = Integer.parseInt(args[0]);
        int <a href="https://javakk.com/tag/removals" rel="external nofollow"  rel="external nofollow"  target="_blank" >removals</a>Size = Integer.parseInt(args[1]);
        
        Set<Integer> source = new HashSet<Integer>();
        Collection<Integer> <a href="https://javakk.com/tag/removals" rel="external nofollow"  rel="external nofollow"  target="_blank" >removals</a> = new ArrayList<Integer>();
        
        for (int i = 0; i < sourceSize; i++)
        {
            source.add(i);
        }
        for (int i = 1; i <= removalsSize; i++)
        {
            removals.add(-i);
        }
        
        long start = System.currentTimeMillis();
        source.removeAll(removals);
        long end = System.currentTimeMillis();
        System.out.println("Time taken: " + (end – start) + "ms");
    }
}

首先，讓我們給它一個簡單的工作：一個包含100個items的source set，以及要刪除的100個items：

c:UsersJonTest>java Test 100 100
Time taken: 1ms

好吧，所以我們沒想到會很慢……很明顯，我們可以把速度提高一點。一百萬件items和300000件items的來源如何？

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

嗯，看起來還是挺快的。現在我覺得我有點殘忍，要求它做所有這些移除。讓我們讓它變得更簡單一些–300000個source items和300000個刪除：

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

快三分鐘瞭？哎呀！當然，從一個較小的集合中刪除items應該比我們在38ms內管理的集合更容易？嗯，最終這一切都是有道理的。HashSet擴展瞭AbstractSet，它在removeAll方法的文檔中包含此代碼段：

https://docs.oracle.com/javase/6/docs/api/java/util/AbstractSet.html

此實現通過調用每個集合上的size方法來確定此集合和指定集合中的較小者。如果此集合的元素較少，則實現將迭代此集合，依次檢查迭代器返回的每個元素，以查看它是否包含在指定的集合中。如果它是這樣包含的，則使用迭代器的remove方法將其從該集中移除。如果指定集合的元素較少，那麼實現將迭代指定集合，使用該集合的remove方法從該集合中刪除迭代器返回的每個元素。

從表面上看，這聽起來很合理——遍歷較小的集合，檢查較大集合中是否存在。然而，這就是抽象存在漏洞的地方。僅僅因為我們可以要求一個item出現在一個大的集合中，並不意味著它會很快出現。在我們的例子中，集合的大小是相同的，但是檢查哈希集中是否存在項是O（1），而在ArrayList中檢查是O（N）…而每個集合的迭代成本是相同的。基本上，通過選擇遍歷HashSet並檢查ArrayList中是否存在，我們得到瞭一個O（M*N）解決方案，而不是O（N）解決方案。removeAll方法基於在這種情況下無效的假設進行“優化”。

那麼如何解決？

有兩種簡單的方法可以解決這個問題。首先，隻需更改要從中刪除的集合的類型。隻需將ArrayList<Integer>更改為HashSet<Integer>，我們就可以回到34ms的范圍。我們甚至不需要更改聲明的刪除類型。

第二種方法是更改我們使用的API：如果我們知道要迭代刪除並在源代碼中執行查找，那麼很容易做到：

for (Integer value : removals)
{
    source.remove(value);
}

事實上，在我的機器上，它的性能略優於removeAll–它不需要在每次迭代時檢查remove的返回值，removeAll這樣做是為瞭返回是否刪除瞭任何項。以上運行時間約為28ms。（我已經用相當大的數據集對其進行瞭測試，它確實比雙哈希集方法更快。）

然而，這兩種方法都需要在源代碼中添加註釋，以解釋為什麼我們沒有使用最明顯的代碼（列表和刪除）。我不能抱怨這裡的文檔——它確切地說明瞭它將做什麼。在你遇到這樣的問題之前，你根本不需要擔心它。

那麼，實現應該做什麼呢？可以說，它真的需要知道它所處理的每一個集合中什麼是便宜的。在決定策略之前探索性能特征的想法對於清理我們喜歡在Java集合之類的框架中考慮的抽象是完全不可取的……但在這種情況下，這可能是一個好主意。

到此這篇關於Java HashSet的Removals()方法註意事項的文章就介紹到這瞭,更多相關Java HashSet 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：