Java:超越 HashSet.contains() 的性能优化？

Question

对于以下代码，我得到的平均计算时间为 50 毫秒。我该如何优化

filter(u -> myStrings.contains(u.getName())

获得更快的计算时间？

list size 3000000, averaged 100 times
LongSummaryStatistics{count=100, sum=5135, min=46, average=51,350000, max=147}

备注: User2 类还包含其他属性(加上 getter、setter)。

代码:

public class Temp2 {
    static HashSet<String> myStrings = new HashSet<>();
    static long test1(List<User2> user2s) {
        long time1 = System.currentTimeMillis();
        ArrayList<User2> collect = user2s.stream()
                .filter(u -> myStrings.contains(u.getName()))
                .collect(Collectors.toCollection(ArrayList::new));
        long time2 = System.currentTimeMillis();
        return time2 - time1;
    }
    static class User2 {
        String name;
        public User2(String name) {this.name = name;}
        public String getName() {return name;}
        public void setName(String name) {this.name = name;}
    }
    public static void main(String... args) {
        for (int i = 0; i < 15; i++) {myStrings.add(getRandomString());}

        int size = 3_000_000;
        List<User2> user2s = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            user2s.add(new User2(getRandomString()));
        }
        repeat("test:", user2s, Temp2::test1, 100);
    }
    private static void repeat(String name, List<User2> user2s, ToLongFunction<List<User2>> test, int iterations) {
        System.out.println("list size " + user2s.size() + ", averaged " + iterations + " times");
        System.out.println(
                IntStream.range(0, iterations)
                        .mapToLong(i -> test.applyAsLong(user2s))
                        .summaryStatistics());
    }
    private static String getRandomString() {
        SecureRandom random = new SecureRandom();
        return (new BigInteger(130, random).toString(32)).substring(0,12);
    }
}

Answer 1

正如其他 stackoverflower 指出的那样 - 瓶颈是 hashCode方法。

特别是对于 String - 计算hashCode你需要遍历字符串。所以越长String是 - 假设您有很多独特的字符串，情况会变得更糟。幸运的是，在您的示例中，它们非常短 - 只有 12 个字符。

根据我的机器(Core-i3 6100U 2.3 GHz)上的 JMH 微基准判断，这里是 contains 的不同实现的每个单个操作的时序。 :

• 58ns - HashSet<String>
• 47ns - HashSet<Integer>
• 35ns - BitSet

就你的情况而言，这意味着对于 3000000 个列表，在我的机器上分别需要大约 174 毫秒、148 毫秒和 105 毫秒。因此，通过更改比较方法，您可以获得约 1.5 倍的速度提升。

所以，如果您在 User2 中添加额外的字段， ，这将保存 name 的转换表示形式这可能适合与 HashSet<String> 不同的东西- 你可以从中受益。考虑到您只有 15 myStrings - 一个BitSet那里可能很合适。

除此之外，parallelStream确实使性能翻倍 - 所以如果您有核心可供使用 - 这将是最好的选择。

附注基准代码:

import org.openjdk.jmh.annotations.*;

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.*;
import java.util.concurrent.TimeUnit;

@State(Scope.Benchmark)
public class ProperBench {

    private HashSet<String> myStrings;
    private String randomName;

    private HashSet<Integer> myInts;
    private Integer randomInt;

    private BitSet myBits;
    private int randomBit;

    List<User2> user2s = new ArrayList<>();

    private static final int MY_STRINGS_SIZE = 15;

    private class User2 {
        String name;
        public User2(String name) {this.name = name;}
        public String getName() {return name;}
        public void setName(String name) {this.name = name;}
    }


    private String getRandomString() {
        SecureRandom random = new SecureRandom();
        return (new BigInteger(130, random).toString(32)).substring(0,12);
    }


    @Setup(Level.Invocation)
    public void setUpIteration() {
        myStrings = new HashSet<>();
        myInts = new HashSet<>();
        myBits = new BitSet(MY_STRINGS_SIZE);

        SecureRandom random = new SecureRandom();

        for (int i = 0; i < MY_STRINGS_SIZE; i++) {
            String aString = getRandomString();
            myStrings.add(aString);
            myInts.add(aString.hashCode());
            if (random.nextBoolean()) myBits.set(i);
        }

        randomName = getRandomString();
        randomInt = randomName.hashCode();
        randomBit = random.nextInt(MY_STRINGS_SIZE);
    }

    @Benchmark
    @BenchmarkMode(Mode.SampleTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public boolean test1() {
        return myStrings.contains(randomName);
    }

    @Benchmark
    @BenchmarkMode(Mode.SampleTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public boolean test2() {
        return myInts.contains(randomInt);
    }

    @Benchmark
    @BenchmarkMode(Mode.SampleTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public boolean test3() {
        return myBits.get(randomBit);
    }

}