java中ArrayList與HashSet的contains方法性能比較

這篇文章主要介紹“java中ArrayList與HashSet的contains方法性能比較”，在日常操作中，相信很多人在java中ArrayList與HashSet的contains方法性能比較問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”java中ArrayList與HashSet的contains方法性能比較”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

1 簡(jiǎn)介

在日常開發(fā)中，ArrayList和HashSet都是Java中很常用的集合類。

• ArrayList是List接口最常用的實(shí)現(xiàn)類；

• HashSet則是保存唯一元素Set的實(shí)現(xiàn)。

本文主要對(duì)兩者共有的方法contains()做一個(gè)簡(jiǎn)單的討論，主要是性能上的對(duì)比，并用JMH(ava Microbenchmark Harness)進(jìn)行測(cè)試比較。

2 先看JMH測(cè)試結(jié)果

我們使用一個(gè)由OpenJDK/Oracle里面開發(fā)了Java編譯器的大牛們所開發(fā)的Micro Benchmark Framework來(lái)測(cè)試。下面簡(jiǎn)單展示一下使用過(guò)程。

2.1 Maven導(dǎo)入相關(guān)依賴

導(dǎo)入JMH的相關(guān)依賴，可以去官網(wǎng)查看最新版本：

<dependencies>
  <dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>${openjdk.jmh.version}</version>
  </dependency>
  <dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>${openjdk.jmh.version}</version>
  </dependency>
</dependencies>

<properties>
  <openjdk.jmh.version>1.19</openjdk.jmh.version>
</properties>

2.2 創(chuàng)建測(cè)試相關(guān)的類

2.2.1 集合儲(chǔ)存對(duì)象的類

因?yàn)橐獪y(cè)試集合類的方法，所以我們創(chuàng)建一個(gè)類來(lái)表示集合所儲(chǔ)存的對(duì)象。如下：

@Data
@AllArgsConstructor(staticName = "of")
public class Student {
    private Long id;
    private String name;
}

2.2.2 JMH測(cè)試類

接下來(lái)我們就來(lái)寫測(cè)試性能對(duì)比的類，代碼如下：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ContainsPerformanceTest {
    @State(Scope.Thread)
    public static class MyState {
        private Set<Student> studentSet = new HashSet<>();
        private List<Student> studentList = new ArrayList<>();
        private Student targetStudent = Student.of(99L, "Larry");

        @Setup(Level.Trial)
        public void prepare() {
            long MAX_COUNT = 10000;
            for (long i = 0; i < MAX_COUNT; i++) {
                studentSet.add(Student.of(i, "MQ"));
                studentList.add(Student.of(i, "MQ"));
            }
            studentList.add(targetStudent);
            studentSet.add(targetStudent);
        }
    }

    @Benchmark
    public boolean arrayList(MyState state) {
        return state.studentList.contains(state.targetStudent);
    }

    @Benchmark
    public boolean hashSet(MyState state) {
        return state.studentSet.contains(state.targetStudent);
    }

    public static void main(String[] args) throws Exception {
        Options options = new OptionsBuilder()
                .include(ContainsPerformanceTest.class.getSimpleName())
                .threads(6)
                .forks(1)
                .warmupIterations(3)
                .measurementIterations(6)
                .shouldFailOnError(true)
                .shouldDoGC(true)
                .build();
        new Runner(options).run();
    }
}

測(cè)試類注解說(shuō)明：

• @BenchmarkMode：表示進(jìn)行Benchmark時(shí)使用的模式；AverageTime表示測(cè)試調(diào)用的平均時(shí)間。

• @OutputTimeUnit：測(cè)試的度量時(shí)間單位；NANOSECONDS表示使用納秒為單位。

• @State：接受一個(gè)Scope參數(shù)表示狀態(tài)的共享范圍；Scope.Thread表示每個(gè)線程獨(dú)享。

• @Setup：執(zhí)行Benchmark前執(zhí)行，類似于JUnit的@BeforeAll。

• @Benchmark：進(jìn)行Benchmark的對(duì)象，類似于JUnit的@Test。

測(cè)試類啟動(dòng)參數(shù)Options說(shuō)明：

• include：benchmark所在的類名；

• threads：每個(gè)進(jìn)程中的測(cè)試線程數(shù)；

• fork：進(jìn)程數(shù)，如果為3，則JMH會(huì)fork出3個(gè)進(jìn)程來(lái)測(cè)試；

• warmupIterations：預(yù)熱的迭代次數(shù)，

• measurementIterations：實(shí)際測(cè)量的迭代次數(shù)。

2.3 測(cè)試結(jié)果

設(shè)置好參數(shù)后，就可以跑測(cè)試了。測(cè)試結(jié)果如下：

# Benchmark: ContainsPerformanceTest.arrayList

# Run progress: 0.00% complete, ETA 00:00:18
# Fork: 1 of 1
# Warmup Iteration   1: 42530.408 ±(99.9%) 2723.999 ns/op
# Warmup Iteration   2: 17841.988 ±(99.9%) 1882.026 ns/op
# Warmup Iteration   3: 18561.513 ±(99.9%) 2021.506 ns/op
Iteration   1: 18499.568 ±(99.9%) 2126.172 ns/op
Iteration   2: 18975.407 ±(99.9%) 2004.509 ns/op
Iteration   3: 19386.851 ±(99.9%) 2248.536 ns/op
Iteration   4: 19279.722 ±(99.9%) 2102.846 ns/op
Iteration   5: 19796.495 ±(99.9%) 1974.987 ns/op
Iteration   6: 21363.962 ±(99.9%) 2175.961 ns/op


Result "ContainsPerformanceTest.arrayList":
  19550.334 ±(99.9%) 2771.595 ns/op [Average]
  (min, avg, max) = (18499.568, 19550.334, 21363.962), stdev = 988.377
  CI (99.9%): [16778.739, 22321.929] (assumes normal distribution)


# Benchmark: ContainsPerformanceTest.hashSet

# Run progress: 50.00% complete, ETA 00:00:16
# Fork: 1 of 1
# Warmup Iteration   1: 10.662 ±(99.9%) 0.209 ns/op
# Warmup Iteration   2: 11.177 ±(99.9%) 1.077 ns/op
# Warmup Iteration   3: 9.467 ±(99.9%) 1.462 ns/op
Iteration   1: 9.540 ±(99.9%) 0.535 ns/op
Iteration   2: 9.388 ±(99.9%) 0.365 ns/op
Iteration   3: 10.604 ±(99.9%) 1.008 ns/op
Iteration   4: 9.361 ±(99.9%) 0.154 ns/op
Iteration   5: 9.366 ±(99.9%) 0.458 ns/op
Iteration   6: 9.274 ±(99.9%) 0.237 ns/op


Result "ContainsPerformanceTest.hashSet":
  9.589 ±(99.9%) 1.415 ns/op [Average]
  (min, avg, max) = (9.274, 9.589, 10.604), stdev = 0.505
  CI (99.9%): [8.174, 11.004] (assumes normal distribution)


# Run complete. Total time: 00:00:32

Benchmark                          Mode  Cnt      Score      Error  Units
ContainsPerformanceTest.arrayList  avgt    6  19550.334 ± 2771.595  ns/op
ContainsPerformanceTest.hashSet    avgt    6      9.589 ±    1.415  ns/op

經(jīng)過(guò)測(cè)試，發(fā)現(xiàn)兩者耗時(shí)差異極大，ArrayList大概是20K納秒，而HashSet則10納秒左右。兩者完全不在一個(gè)數(shù)量級(jí)上。

3 源碼分析

通過(guò)測(cè)試得知兩者差異極大，就小窺一下源碼分析分析。

3.1 ArrayList的contains()

ArrayList的底層使用數(shù)組作為數(shù)據(jù)存儲(chǔ)，當(dāng)給定一個(gè)Object去判斷是否存在，需要去遍歷數(shù)組，與每個(gè)元素對(duì)比。

public boolean contains(Object o) {
  return indexOf(o) >= 0;
}
public int indexOf(Object o) {
  if (o == null) {
    for (int i = 0; i < size; i++)
      if (elementData[i]==null)
        return i;
  } else {
    for (int i = 0; i < size; i++)
      if (o.equals(elementData[i]))
        return i;
  }
  return -1;
}

從源碼可以發(fā)現(xiàn)，contains()方法是通過(guò)調(diào)用indexOf()來(lái)判斷的，而后者就是需要遍歷數(shù)組，直到找到那個(gè)與入?yún)⑾嗟鹊脑夭艜?huì)停止。因?yàn)椋?code>ArrayList的contains()方法的時(shí)間復(fù)雜度為O(n)，也就是說(shuō)，時(shí)間取決于長(zhǎng)度，而且是正比的關(guān)系。

3.2 HashSet的contains()

HashSet底層是通過(guò)HashMap來(lái)實(shí)現(xiàn)的，而HashMap的底層結(jié)構(gòu)為數(shù)組+鏈表，JDK 8后改為數(shù)組+鏈表+紅黑樹。

HashMap的相關(guān)代碼如下：

public boolean containsKey(Object key) {
  return getNode(hash(key), key) != null;
}
final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    if ((e = first.next) != null) {
      if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while ((e = e.next) != null);
    }
  }
  return null;
}

首先通過(guò)獲取Hash值來(lái)找，如果Hash值相等且對(duì)象也相等，則找到。一般來(lái)說(shuō)，在hashCode()方法實(shí)現(xiàn)沒問(wèn)題的情況下，發(fā)生Hash沖突的情況是比較少。所以可以認(rèn)為，大部分情況下，contains()的時(shí)間復(fù)雜度為O(1)，元素個(gè)數(shù)不影響其速度。如果發(fā)生Hash沖突，在鏈表長(zhǎng)度小于8時(shí)，時(shí)間復(fù)雜度為O(n)；在鏈表大于8時(shí)，轉(zhuǎn)化為紅黑樹，時(shí)間復(fù)雜度為O(logn)。

一般地，我們認(rèn)為，HashSet/HashMap的查找的時(shí)間復(fù)雜度為O(1)。

4 總結(jié)

通過(guò)JMH測(cè)試我們發(fā)現(xiàn)ArrayList和HashSet的contains()方法性能差異很大。經(jīng)過(guò)源碼分析得知，ArrayList對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n)，而HashSet的時(shí)間度為O(1)。

到此，關(guān)于“java中ArrayList與HashSet的contains方法性能比較”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！