java中ArrayList與HashSet的contains方法性能比較
這篇文章主要介紹“java中ArrayList與HashSet的contains方法性能比較”，在日常操作中，相信很多人在java中ArrayList與HashSet的contains方法性能比較問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java中ArrayList與HashSet的contains方法性能比較”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
創(chuàng)新互聯(lián)建站長期為成百上千客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為修水企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計、成都做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)，修水網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。
1 簡介
在日常開發(fā)中，ArrayList和HashSet都是Java中很常用的集合類。
ArrayList是List接口最常用的實現(xiàn)類；HashSet則是保存唯一元素Set的實現(xiàn)。
本文主要對兩者共有的方法contains()做一個簡單的討論，主要是性能上的對比，并用JMH(ava Microbenchmark Harness)進行測試比較。
2 先看JMH測試結(jié)果
我們使用一個由OpenJDK/Oracle里面開發(fā)了Java編譯器的大牛們所開發(fā)的Micro Benchmark Framework來測試。下面簡單展示一下使用過程。
2.1 Maven導(dǎo)入相關(guān)依賴
導(dǎo)入JMH的相關(guān)依賴，可以去官網(wǎng)查看最新版本：
org.openjdk.jmh jmh-core ${openjdk.jmh.version} org.openjdk.jmh jmh-generator-annprocess ${openjdk.jmh.version} 1.19
2.2 創(chuàng)建測試相關(guān)的類
2.2.1 集合儲存對象的類
因為要測試集合類的方法，所以我們創(chuàng)建一個類來表示集合所儲存的對象。如下：
@Data
@AllArgsConstructor(staticName = "of")
public class Student {
private Long id;
private String name;
}2.2.2 JMH測試類
接下來我們就來寫測試性能對比的類，代碼如下：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ContainsPerformanceTest {
@State(Scope.Thread)
public static class MyState {
private Set studentSet = new HashSet<>();
private List 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();
}
} 測試類注解說明：
@BenchmarkMode：表示進行Benchmark時使用的模式；
AverageTime表示測試調(diào)用的平均時間。@OutputTimeUnit：測試的度量時間單位；
NANOSECONDS表示使用納秒為單位。@State：接受一個
Scope參數(shù)表示狀態(tài)的共享范圍；Scope.Thread表示每個線程獨享。@Setup：執(zhí)行Benchmark前執(zhí)行，類似于
JUnit的@BeforeAll。@Benchmark：進行Benchmark的對象，類似于
JUnit的@Test。
測試類啟動參數(shù)Options說明：
include：benchmark所在的類名；
threads：每個進程中的測試線程數(shù)；
fork：進程數(shù)，如果為3，則JMH會fork出3個進程來測試；
warmupIterations：預(yù)熱的迭代次數(shù)，
measurementIterations：實際測量的迭代次數(shù)。
2.3 測試結(jié)果
設(shè)置好參數(shù)后，就可以跑測試了。測試結(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)過測試，發(fā)現(xiàn)兩者耗時差異極大，ArrayList大概是20K納秒，而HashSet則10納秒左右。兩者完全不在一個數(shù)量級上。
3 源碼分析
通過測試得知兩者差異極大，就小窺一下源碼分析分析。
3.1 ArrayList的contains()
ArrayList的底層使用數(shù)組作為數(shù)據(jù)存儲，當(dāng)給定一個Object去判斷是否存在，需要去遍歷數(shù)組，與每個元素對比。
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()方法是通過調(diào)用indexOf()來判斷的，而后者就是需要遍歷數(shù)組，直到找到那個與入?yún)⑾嗟鹊脑夭艜Ｖ?。因為?code>ArrayList的contains()方法的時間復(fù)雜度為O(n)，也就是說，時間取決于長度，而且是正比的關(guān)系。
3.2 HashSet的contains()
HashSet底層是通過HashMap來實現(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 getNode(int hash, Object key) {
Node[] tab; Node 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)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;
} 首先通過獲取Hash值來找，如果Hash值相等且對象也相等，則找到。一般來說，在hashCode()方法實現(xiàn)沒問題的情況下，發(fā)生Hash沖突的情況是比較少。所以可以認(rèn)為，大部分情況下，contains()的時間復(fù)雜度為O(1)，元素個數(shù)不影響其速度。如果發(fā)生Hash沖突，在鏈表長度小于8時，時間復(fù)雜度為O(n)；在鏈表大于8時，轉(zhuǎn)化為紅黑樹，時間復(fù)雜度為O(logn)。
一般地，我們認(rèn)為，HashSet/HashMap的查找的時間復(fù)雜度為O(1)。
4 總結(jié)
通過JMH測試我們發(fā)現(xiàn)ArrayList和HashSet的contains()方法性能差異很大。經(jīng)過源碼分析得知，ArrayList對應(yīng)的時間復(fù)雜度為O(n)，而HashSet的時間度為O(1)。
到此，關(guān)于“java中ArrayList與HashSet的contains方法性能比較”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
分享名稱：java中ArrayList與HashSet的contains方法性能比較
URL標(biāo)題：http://m.jiaotiyi.com/article/iggdjh.html