|
序言：許多人看完，ArrayList源碼后，自我感覺(jué)良好，一問(wèn) RandomAccess 這玩意干嘛的，一臉懵，
所以今天來(lái)盤(pán)盤(pán)這個(gè)接口
RandomAccess接口的作用
咱先看看官方怎么介紹這個(gè)接口的，摘自注釋
譯：這個(gè)接口是被用來(lái)List實(shí)現(xiàn)的標(biāo)記接口，支持快速隨機(jī)訪問(wèn)，且只要你實(shí)現(xiàn)了它，你使用for循環(huán)遍歷，效率會(huì)高于迭代器的遍歷（說(shuō)明一下，這里說(shuō)的 for 循環(huán)是普通循環(huán),而 增強(qiáng) for-each 本質(zhì)就等同于 迭代器遍歷）
//避免自動(dòng)裝箱拆箱影響,不聲明泛型
List list = new ArrayList<>();
int total = 40000000;
for (int i = 0; i<total; i++){
list.add(i);
}
//1.使用普通for循環(huán)的效率
long start1 = System.currentTimeMillis();
for(int i = 0; i < total; i++){
Object temp = list.get(i);
}
long end1 = System.currentTimeMillis();
System.out.println("普通循環(huán)的時(shí)間效率:" + (end1 - start1));
//2.使用迭代器的循環(huán)效率
long start2 = System.currentTimeMillis();
Iterator iterator = list.iterator();
while(iterator.hasNext()){
Object temp = iterator.next();
}
long end2 = System.currentTimeMillis();
System.out.println("迭代器循環(huán)的時(shí)間效率:" + (end2 - start2));
//3.使用增強(qiáng)for循環(huán)（其實(shí)底層也是用迭代器玩的）
long start3 = System.currentTimeMillis();
for(Object num: list){
Object temp = num;
}
long end3 = System.currentTimeMillis();
System.out.println("增強(qiáng)for循環(huán)的時(shí)間效率:" + (end3 - start3));
這里的隨機(jī)訪問(wèn)，就是能夠隨機(jī)的訪問(wèn) List 中的任何一個(gè)元素，不要想多
雖然所有的 List 實(shí)現(xiàn) 都支持隨機(jī)訪問(wèn)，只是由于數(shù)據(jù)結(jié)構(gòu)不同，導(dǎo)致訪問(wèn)效率不同。但是這里的快速隨機(jī)訪問(wèn)，不是所有 List 集合能干的。
- ArrayList，底層為數(shù)組，有下標(biāo)，指哪打哪，隨機(jī)訪問(wèn)效率 O(1)
- LinkedList，底層為鏈表，訪問(wèn)一個(gè)元素，需要遍歷，隨機(jī)訪問(wèn)效率 O(n)
所以 ArrayList 實(shí)現(xiàn)了 RandomAccess，LinkedList 則沒(méi)有
實(shí)現(xiàn)了 RandomAccess 的接口有：
- ArrayList
- Vector
- CopyOnWriteArrayList
- RandomAccessSubList
- UnmodifiableArrayList
可能你看到這，又有疑問(wèn)了，我知道這個(gè)接口是標(biāo)志接口了，實(shí)現(xiàn)了它就能快速隨機(jī)訪問(wèn)，所以它有什么用 ？
在上文中，我們通過(guò)測(cè)試發(fā)現(xiàn)只要實(shí)現(xiàn)了這個(gè)接口，普通 for 循環(huán)的 效率要高于迭代器，所以你可能會(huì)說(shuō)在追求效率的時(shí)候我全用 普通 for循環(huán) 就行了，這個(gè)接口的作用還是沒(méi)有凸顯出來(lái)。
那么下面我們看這樣一個(gè)測(cè)試, 這次測(cè)試對(duì)象為 LinkedList。
//注意這次我們使用雙線鏈表LinkedList
List list = new LinkedList();
int total = 100000;
for (int i = 0; i<total; i++){
list.add(i);
}
//1.使用普通for循環(huán)的效率
long start1 = System.currentTimeMillis();
for(int i = 0; i < total; i++){
Object temp = list.get(i);
}
long end1 = System.currentTimeMillis();
System.out.println("普通循環(huán)的時(shí)間效率:" + (end1 - start1));
//2.使用迭代器的循環(huán)效率
long start2 = System.currentTimeMillis();
Iterator iterator = list.iterator();
while(iterator.hasNext()){
Object temp = iterator.next();
}
long end2 = System.currentTimeMillis();
System.out.println("迭代器循環(huán)的時(shí)間效率:" + (end2 - start2));
明白了不，不同 List 集合 使用不同的遍歷方式，效率完完全全不一樣，不是使用誰(shuí)效率就一定高，得看對(duì)象是誰(shuí)
所以如果你有這么個(gè)訴求，你有個(gè)List 對(duì)象 A，但是它可能是 LinkedList，可能是ArrayList，也可能是 CopyOnWriteArrayList，但是你就想它是以最高效率去遍歷的，這個(gè)時(shí)候你可以根據(jù)這個(gè)RandomAccess 去決定以哪種方式去遍歷
if(A instanceof RandomAccess){
//使用普通for循環(huán)遍歷
} else {
//使用迭代器遍歷
}
算法的差異
上文我們提到有沒(méi)有實(shí)現(xiàn) RandomAccess接口，會(huì)導(dǎo)致不同的集合采取不同的遍歷方式，會(huì)有不一樣的訪問(wèn)效率。但是為什么會(huì)這樣呢，底層是怎么做的
我們看一下 java.util.Collections#binarySearch
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
我們可以看到，在進(jìn)行二分查找時(shí)，會(huì)進(jìn)行判斷是否實(shí)現(xiàn)了 RandomAccess接口 從而采取不一樣的遍歷方式
所以看到這你應(yīng)該明白了，數(shù)據(jù)結(jié)構(gòu)決定了算法的根本，RandomAccess接口 僅僅是個(gè)標(biāo)志接口
不僅是二分查找，底層的普通遍歷也會(huì)根據(jù)其數(shù)據(jù)結(jié)構(gòu)選擇相應(yīng)的執(zhí)行策略，選對(duì)了和數(shù)據(jù)結(jié)構(gòu)相性匹配的策略當(dāng)然就快了
總結(jié)：數(shù)據(jù)結(jié)構(gòu)決定算法
|
