遍歷方法的實現(xiàn)原理
-
1唆迁、傳統(tǒng)的for循環(huán)遍歷退敦，基于計數(shù)器的：
遍歷者自己在集合外部維護一個計數(shù)器反惕，然后依次讀取每一個位置的元素，當(dāng)讀取到最后一個元素后趁桃，停止。主要就是需要按元素的位置來讀取元素入宦。 -
2帅腌、迭代器遍歷，Iterator：
每一個具體實現(xiàn)的數(shù)據(jù)集合遮糖，一般都需要提供相應(yīng)的Iterator绣的。相比于傳統(tǒng)for循環(huán)，Iterator取締了顯式的遍歷計數(shù)器。所以基于順序存儲集合的Iterator可以直接按位置訪問數(shù)據(jù)被辑。而基于鏈?zhǔn)酱鎯系腎terator，正常的實現(xiàn)敬惦，都是需要保存當(dāng)前遍歷的位置盼理。然后根據(jù)當(dāng)前位置來向前或者向后移動指針。 -
3俄删、foreach循環(huán)遍歷：
根據(jù)反編譯的字節(jié)碼可以發(fā)現(xiàn)宏怔，foreach內(nèi)部也是采用了Iterator的方式實現(xiàn)，只不過Java編譯器幫我們生成了這些代碼畴椰。
各遍歷方式對于不同的存儲方式臊诊，性能如何？
- 1斜脂、傳統(tǒng)的for循環(huán)遍歷抓艳，基于計數(shù)器的：
因為是基于元素的位置，按位置讀取帚戳。所以我們可以知道玷或，對于順序存儲，因為讀取特定位置元素的平均時間復(fù)雜度是O(1)片任，所以遍歷整個集合的平均時間復(fù)雜度為O(n)偏友。而對于鏈?zhǔn)酱鎯Γ驗樽x取特定位置元素的平均時間復(fù)雜度是O(n)对供，所以遍歷整個集合的平均時間復(fù)雜度為O(n2)（n的平方）位他。
ArrayList按位置讀取的代碼：直接按元素位置讀取。
LinkedList按位置讀取的代碼：每次都需要從第0個元素開始向后讀取产场。其實它內(nèi)部也做了小小的優(yōu)化鹅髓。 - 2、迭代器遍歷京景，Iterator：
那么對于RandomAccess類型的集合來說迈勋，沒有太多意義，反而因為一些額外的操作醋粟，還會增加額外的運行時間靡菇。但是對于Sequential Access的集合來說，就有很重大的意義了米愿，因為Iterator內(nèi)部維護了當(dāng)前遍歷的位置厦凤，所以每次遍歷，讀取下一個位置并不需要從集合的第一個元素開始查找育苟，只要把指針向后移一位就行了较鼓，這樣一來，遍歷整個集合的時間復(fù)雜度就降低為O(n)；
（這里只用LinkedList做例子）LinkedList的迭代器博烂，內(nèi)部實現(xiàn)香椎，就是維護當(dāng)前遍歷的位置，然后操作指針移動就可以了： - 3禽篱、foreach循環(huán)遍歷：
分析Java字節(jié)碼可知畜伐，foreach內(nèi)部實現(xiàn)原理，也是通過Iterator實現(xiàn)的躺率，只不過這個Iterator是Java編譯器幫我們生成的玛界，所以我們不需要再手動去編寫。但是因為每次都要做類型轉(zhuǎn)換檢查悼吱，所以花費的時間比Iterator略長慎框。時間復(fù)雜度和Iterator一樣。
各遍歷方式的適用于什么場合后添？
- 1笨枯、傳統(tǒng)的for循環(huán)遍歷，基于計數(shù)器的：
順序存儲：讀取性能比較高遇西。適用于遍歷順序存儲集合猎醇。
鏈?zhǔn)酱鎯Γ簳r間復(fù)雜度太大，不適用于遍歷鏈?zhǔn)酱鎯Φ募稀?/li> - 2努溃、迭代器遍歷硫嘶，Iterator：
順序存儲：如果不是太在意時間，推薦選擇此方式梧税，畢竟代碼更加簡潔沦疾，也防止了Off-By-One的問題。
鏈?zhǔn)酱鎯Γ阂饬x就重大了第队，平均時間復(fù)雜度降為O(n)哮塞，還是挺誘人的，所以推薦此種遍歷方式凳谦。 - 3忆畅、foreach循環(huán)遍歷：
foreach只是讓代碼更加簡潔了，但是他有一些缺點尸执，就是遍歷過程中不能操作數(shù)據(jù)集合（刪除等）家凯，所以有些場合不使用。而且它本身就是基于Iterator實現(xiàn)的如失，但是由于類型轉(zhuǎn)換的問題绊诲，所以會比直接使用Iterator慢一點，但是還好褪贵，時間復(fù)雜度都是一樣的掂之。所以怎么選擇抗俄，參考上面兩種方式，做一個折中的選擇世舰。
Java遍歷集合的最佳實踐是什么动雹？
Java數(shù)據(jù)集合框架中，提供了一個RandomAccess接口跟压，該接口沒有方法胰蝠，只是一個標(biāo)記。通常被List接口的實現(xiàn)使用裆馒，用來標(biāo)記該List的實現(xiàn)是否支持Random Access。
一個數(shù)據(jù)集合實現(xiàn)了該接口丐怯，就意味著它支持Random Access喷好，按位置讀取元素的平均時間復(fù)雜度為O(1)。比如ArrayList读跷。
而沒有實現(xiàn)該接口的梗搅，就表示不支持Random Access。比如LinkedList效览。
所以看來JDK開發(fā)者也是注意到這個問題的无切，那么推薦的做法就是，如果想要遍歷一個List丐枉，那么先判斷是否支持Random Access哆键，也就是 list instanceof RandomAccess。
比如：
if (list instanceof RandomAccess) {
//使用傳統(tǒng)的for循環(huán)遍歷瘦锹。
} else {
//使用Iterator或者foreach籍嘹。
}
