乐趣区

关于java:Java性能优化之影响性能的那些细节三

jiezi

ArrayList 到 HashSet 的一次优化

一、前言

  最近共事分享了一次遍历 List 判断元素是否存在的优化技巧，亲自试验的一波，还是很 nb。

（一）本地试验后果

1. 环境信息

  • jdk1.8
  • 测试工具：JMH 1.22
  • 测试机器：mbp 16C32G

2. 测试后果

  在同样 10000 个元素数量的状况下进行蕴含判断，HashSet比 ArrayList 快了约 7660 多倍。尽管试验之前晓得 HashSet 必定比 ArrayList 性能快，然而后果还是有点超出预期。

 * 测试后果（依照吞吐量来测试）：* Benchmark                                                  Mode  Cnt       Score      Error   Units
 * perfTuning.TestListAndHashSet.checkArrayListWithContains  thrpt    5      24.929 ±    9.703  ops/ms
 * perfTuning.TestListAndHashSet.checkArrayListWithIndex     thrpt    5      25.505 ±    1.811  ops/ms
 * perfTuning.TestListAndHashSet.checkArrayListWithIterator  thrpt    5      23.496 ±    3.172  ops/ms
 * perfTuning.TestListAndHashSet.checkHashSet                thrpt    5  191505.153 ± 9573.444  ops/ms

二、测试代码

（一）测试源码

  • 这边思考了极其状况，待判断的元素默认放在了最初。
/**
 * @Author: allen
 * @Date: 2022/2/16 5:45 下午
 * @Description: 比照 ArrayList 和 HashSet 各种场景下判断元素是否存在的性能状况
 *
 * 测试后果：* Benchmark                                                  Mode  Cnt       Score      Error   Units
 * perfTuning.TestListAndHashSet.checkArrayListWithContains  thrpt    5      24.929 ±    9.703  ops/ms
 * perfTuning.TestListAndHashSet.checkArrayListWithIndex     thrpt    5      25.505 ±    1.811  ops/ms
 * perfTuning.TestListAndHashSet.checkArrayListWithIterator  thrpt    5      23.496 ±    3.172  ops/ms
 * perfTuning.TestListAndHashSet.checkHashSet                thrpt    5  191505.153 ± 9573.444  ops/ms
 */

@State(Scope.Benchmark)
public class TestListAndHashSet {public static final HashSet<String> hashSet = new HashSet<String>();
    public static final ArrayList<String> arrayList = new ArrayList<String>();

    /**
     * 构建测试汇合 HashSet 和 ArrayList，都寄存 10001 个元素，并将待判断元素增加至尾部
     */
    @Setup(Level.Trial)
    public void init() {for (int i = 0; i < 10000; i++) {hashSet.add(UuidUtil.getStrUuid());
        }
        hashSet.add("hashSet-test");

        for (int i = 0; i < 10000; i++) {arrayList.add(UuidUtil.getStrUuid());
        }
        arrayList.add("arrayList-test");
    }

    /**
     * HashSet 通过定位 key 的 hash 值进行查找，工夫复杂度 O(1)
     * @return Boolean
     */
    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Boolean checkHashSet() {return hashSet.contains("hashSet-test");
    }

    /**
     * 通过迭代器遍历 ArrayList 进行一一比对，工夫复杂度 O(n)
     * 能够查看编译之后的字节码，会应用迭代器进行遍历操作
     * @return Boolean
     */
    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Boolean checkArrayListWithIterator() {for (String s : arrayList) {if (s.equals("arrayList-test")) {return true;}
        }
        return false;
    }

    /**
     * 通过 index 手工遍历 ArrayList 进行一一比对，工夫复杂度 O(n)
     * @return Boolean
     */
    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Boolean checkArrayListWithIndex() {for (int i = 0; i < arrayList.size(); i++) {if (arrayList.get(i).equals("arrayList-test")) {return true;}
        }
        return false;
    }

    /**
     * ArrayList 的 contains 办法通过遍历 list 进行一一比对，工夫复杂度 O(n)
     * @return Boolean
     */
    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public Boolean checkArrayListWithContains() {return arrayList.contains("arrayList-test");
    }

    public static void main(String[] args) throws RunnerException {Options opt = new OptionsBuilder()
                .include(TestListAndHashSet.class.getSimpleName())
                .forks(1)
                .build();
        new Runner(opt).run();}
}

（二）简略记录下心得

  • 对于 ArrayList 这种底层应用数组实现的数据结构，应用数组 index 遍历会比应用 迭代器 遍历效率高一些，迭代器遍历更适宜链表类数据；
  • ArrayList的 contains 办法，源码中默认应用的就是 index 遍历，因而 contains 效率和我手动 index 遍历的效率差不多；
  • HashSet的 contains 办法，应用的是 hash 值定位，同 HashMap 的hash定位，工夫复杂度是 O(1)，效率远大于遍历操作；

  之后存在汇合蕴含判断的场景，HashSet就是大妙招。

《Java 性能优化之影响性能的那些细节》继续更新中 …

退出移动版