HashSet与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.
    }
}

我的应用程序尝试以每秒大约20个请求的并发方式使用此isValidString()方法。这很好运行，但当我尝试将数据结构更改为HashSet时，CPU使用率变得非常高。据我理解，Hashset应该比ArrayList[o(n)]更快[o(1)]。有人能解释一下这是为什么吗？

- Sthita

---

同意@Codebender的观点。如果您的调用是单例模式，那么可以在getInstance()方法中创建它，我相信它将始终只有一个列表或集合。 - Ankit Katiyar

@Sthita - 你的 isValidString() 应该有一个同步块，确保 init(); 只被调用一次。此外，你需要检查 null 两次。 - TheLostMind

@ankitkatiyar91，如果你让inValidString()方法同步，那么就失去了多线程的目的，你只需要让if(stringList==null)这个条件同步即可。 - Codebender

@TheLostMind 实现初始容量似乎是个好主意，但我仍然觉得对于长期来看不会有明显的改善。 - Sthita

有一个延迟初始化的单例对象，其中包含一个延迟加载的stringList。但是这样做有什么意义呢？在查询列表之前必须先加载集合，因此并不能实现并行处理。那么为什么不在构造函数中初始化呢？ - Chris Martin

Answer 1

我创建了一个简单的类来生成20个线程，每秒访问您的字典检查器，如本帖底部所述。

我无法复制您的结果 - 但这可能是因为我可以访问的输入数据。我使用了您的TestClass实现，从英语开放词汇列表（EOWL）导入了约130,000个单词。无论stringList的类型是ArrayList还是HashSet，都没有看到持续的高CPU使用。

我猜您的问题是由于输入数据引起的。我尝试添加两次我的输入字典以创建重复项 - 显然，对于ArrayList，这只是使列表变长两倍，但对于HashSet，它意味着代码正在丢弃重复项。您指出大约1/5的输入数据是重复的。在我的测试中，有1/2的重复项，我确实看到了轻微的 CPU增加，大约持续2秒，然后一旦初始化stringList，它就几乎不会消耗任何资源。

如果您的输入字符串比我使用的单个单词更复杂，这个“波动”可能会更长。所以也许这就是您的问题。另外 - 也许您有一些包装这部分代码的其他代码正在独占CPU。

N.B. 我像其他人在评论中那样警告您关于init的实现。在我的实验中，我看到许多线程可以在字典完全初始化之前调用字典检查，导致相同测试单词的不一致结果。如果它是一个单例对象，为什么不从构造函数中调用它呢？

代码列表

您的TestClass与一些输入数据代码：

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();
            } 
        }
    }
}

- J Richard Snape

---

@J Richard Snape 是的，我正在构造函数中初始化它，目前是一个具有初始大小的 HashSet，在目前看来很不错。 - Sthita

@sthita，很高兴你已经按照自己的想法使它工作了 :) - J Richard Snape

Answer 2

我猜测，由于HashSet是基于哈希的结构，它会在插入每个字符串时计算hashCode，即在init方法中。这可能是CPU高峰期，这也是我们为迭代结构的值而获得更好吞吐量的代价之一。

如果我的猜测正确，当init方法结束后，CPU应该会降下来，程序速度应该会大幅提升，这就是使用HashSet的好处。

顺便说一句：优化的一个确定方式是预设大小：

• ArrayList的初始大小应等于将包含的元素的最大数量。
• HashSet的初始大小应比最大值大1.7倍。

顺便提一下：String.hash 的标准哈希算法会计算字符串中的所有字符。也许你可以只计算前100个字符，例如（当然这取决于你正在处理的数据的性质）。然后，你可以将你的字符串封装到自己的类中，用你自己的哈希算法重写 hashCode 方法，并重写 equals 方法以执行严格比较。

- Little Santi

---

不，CPU使用率根本没有下降，如果我使用HashSet，一段时间后应用程序就会停止响应。我正在使用ArrayList并给出了初始大小。 - Sthita

你是否使用了具有初始大小的HashSet？如果没有，那可能是问题的原因：一个小的哈希结构会变得过满，从而变得低效，因为它会变成一组长列表。 - Little Santi

@Sthita - 检查一下 GC 是否也在起作用。 - TheLostMind

@LittleSanti 设置初始大小的 HashSet 看起来很不错，而且对我来说也很有效。我会继续监控我的应用程序，并观察其影响。谢谢。 - Sthita

Answer 3

JDK的HashSet是建立在HashMap<T，Object>之上的，其中值是单例的“present”对象。这意味着HashSet的内存消耗与HashMap相同：为了存储SIZE个值，您需要32 * SIZE + 4 * CAPACITY字节（加上您的值的大小）。

对于ArrayList，它是java.util.ArrayList的容量乘以引用大小（32位上为4字节，64位上为8字节）+ [对象头+一个int和一个引用]。

因此，HashSet绝对不是一个内存友好的集合。

这取决于您使用的是32位还是64位 VM。话虽如此，HashSet受到8字节引用的影响比ArrayList更严重--根据链接的内存消耗图表，每个引用增加额外的4字节，将ArrayList提高到每个元素~12字节，而HashSet提高到每个元素~52字节。)

ArrayList是使用对象数组实现的。下面的图展示了32位Java运行时中ArrayList的内存使用和布局：

32位Java运行时中ArrayList的内存使用和布局

上图显示，当创建一个ArrayList时，结果是一个使用32字节内存的ArrayList对象，以及一个默认大小为10的Object数组，对于一个空的ArrayList，总共使用88字节内存。这意味着ArrayList的大小不是准确的，因此具有默认容量，这恰好是10个条目。

ArrayList的属性

默认容量 - 10

空大小 - 88字节

开销 - 48字节加每个条目4字节

10K个元素的集合的开销 - 约为40K

搜索/插入/删除性能 - O(n) - 时间复杂度与元素数量成线性关系

HashSet比HashMap功能更少，它不能包含多个空条目，也不能有重复的条目。实现是一个HashMap的包装器，HashSet对象管理允许放入HashMap对象的内容。限制HashMap功能的附加函数意味着HashSets具有稍高的内存开销。

32位Java运行时的HashSet的内存使用和布局

上图显示了java.util.HashSet对象的浅堆（单个对象的内存使用）和保留堆（单个对象及其子对象的内存使用）的字节数。浅堆大小为16字节，保留堆大小为144字节。当创建HashSet时，其默认容量-可以放入集合中的条目数为16个条目。当以默认容量创建HashSet并且没有将任何条目放入集合中时，它占用144字节。这比HashMap的内存使用多出16字节。

下表显示了HashSet的属性：

HashSet的属性

默认容量 -16个条目

空大小 -144字节

开销 -16字节加上HashMap开销

10K集合的开销 -16字节加上HashMap开销

查找/插入/删除性能 - O(1) - 所需时间是常数时间，不受元素数量影响（假设没有哈希冲突）

- My God

---

参考资料显示迭代的性能更好，而我们只是想比较/检查列表/集合中令牌的可用性。 - Sthita

如果您不关心... contains方法的性能，但是在这里我们调用contains方法最频繁，对吗？ - Chris Martin

@Sthita - 请参考引用2中的容量和上面arrayList的添加容量。 - My God

OP在谈论CPU使用率，而不是内存。他们显然确实关心contains的性能。 - J Richard Snape