java - HashSet vs ArrayList CPU 使用率高

Question

我有 104k 个字符串值，其中 89k 个是唯一的。我想检查这个列表中是否存在一个字符串。

这是我的类及其保存所有这些记录的方法。

public class TestClass {
    private static TestClass singletonObj = null;
    private List<String> stringList= null;

    public static synchronized TestClass getInstance() {
        if(singletonObj == null) {
            singletonObj = new TestClass();
        }
        return singletonObj;
    }


    public boolean isValidString(String token) {
        if(stringList == null) {
            init();
        }
        if(stringList != null && token != null && !token.isEmpty())
            return stringList.contains(token.toLowerCase());
        return false;
    }

    private init() {
     stringList = new ArrayList<String>();
     // put all 104k values in this data structure.
    }
}

我的应用程序尝试同时使用此 isValidString() 方法，每秒大约有 20 个请求。这工作正常，但是当我尝试将数据结构更改为 HashSet 时，CPU 使用率非常高。根据我的理解，Hashset 应该比 ArrayList[o(n)] 表现得更好[o(1)]。任何人都可以向我解释为什么会这样吗？

Answer 1

我创建了一个简单的类来生成 20 个线程，按照这篇文章的底部每秒访问您的字典检查器。

我无法复制您的结果 - 但这可能是因为我有权访问输入数据。我使用了您的 TestClass 实现，从英语开放单词列表 (EOWL) 中导入了约 130,000 个单词。对于 ArrayList 或 HashSet 作为 stringList 的类型，没有看到持续的高 CPU 使用率。

我的猜测是您的问题是由于您的输入数据造成的。我尝试添加我的输入字典两次以创建重复 - 显然使用 ArrayList 这只会使列表长两倍，但是使用 HashSet，这意味着代码被抛出重复。您注意到大约 1/5 的输入数据是重复的。在我的测试中有 1/2 的重复项，我确实看到 轻微 CPU 增加了大约 2 秒，然后在 stringList 已初始化。

如果您输入的字符串比我使用的单个单词更复杂，这个“信号”可能会持续更长时间。所以也许那是你的问题。或者 - 也许您有一些其他代码来包装这部分占用 CPU 的部分。

N.B. 我会提醒您，因为其他人在对您的 init 实现发表评论时。在我的实验中，我看到许多线程可以在字典完全初始化之前调用字典检查，从而为相同的测试单词提供不一致的结果。如果它是一个单例对象，为什么不从你的构造函数中调用它呢？

代码 list

带有一些输入数据代码的测试类:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class TestClass {
    private static TestClass singletonObj = null;
    //private List<String> stringList = null;

    private HashSet<String> stringList = null;

    public static synchronized TestClass getInstance() {
        if (singletonObj == null) {
            singletonObj = new TestClass();
        }
        return singletonObj;
    }

    public boolean isValidString(String token) {
        if (stringList == null) {
            init();
        }
        if (stringList != null && token != null && !token.isEmpty())
            return stringList.contains(token.toLowerCase());
        return false;
    }

    private void init() {
        String dictDir = "C:\\Users\\Richard\\Documents\\EOWL_CSVs";
        File[] csvs = (new File(dictDir)).listFiles();
        stringList = new HashSet<String>();
        Scanner inFile = null;

        for (File f : csvs) {
            try {
                inFile = new Scanner(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
                System.exit(1);
            }

            while (inFile.hasNext()) {
                stringList.add(inFile.next().toLowerCase()
                        .replaceAll("[^a-zA-Z ]", ""));
            }
            inFile.close();
        }

        System.out.println("Dictionary initialised with " + stringList.size()
                + " members");
    }
}

访问它的线程:

import java.io.FileNotFoundException;

public class DictChecker extends Thread {

    TestClass t = null;
    public static int classId = 0;
    String className = null;
    
    
    public void doWork()
    {
        String testString = "Baby";
        if (t.isValidString(testString))
        {
            System.out.println("Got a valid string " + testString + " in class " + className);
        }
        else
        {
            System.out.println(testString + " not in the dictionary");
        }
    }
    
    public void run()
    {
        while (true)
        {
            try {
                DictChecker.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            doWork();
        }
    }
    
    public DictChecker()
    {
        t = TestClass.getInstance();
        className = "dChecker" + classId;
        classId += 1;
        System.out.println("Initialised " + className + " in thread " + this.getName());
    }
    
    public static void main(String[] args) throws FileNotFoundException
    {
        for (int i = 0; i < 20; i++)
        {
             (new DictChecker()).start();
             try {
                DictChecker.sleep(50);//simply to distribute load over the second
            } catch (InterruptedException e) {
                e.printStackTrace();
            } 
        }
    }
}