Java集合面試總結
★★★★★集合架構:用于存儲資料的容器。
特點:
1:對象封裝資料,對象多了也需要存儲。集合用于存儲對象。
2:對象的個數确定可以使用數組,但是不确定怎麼辦?可以用集合。因為集合是可變長度的。
集合和數組的差別:
1:數組是固定長度的;集合可變長度的。
2:數組可以存儲基本資料類型,也可以存儲引用資料類型;集合隻能存儲引用資料類型。
3:數組存儲的元素必須是同一個資料類型;集合存儲的對象可以是不同資料類型。
資料結構:就是容器中存儲資料的方式。
對于集合容器,有很多種。因為每一個容器的自身特點不同,其實原理在于每個容器的内部資料結構不同。
集合容器在不斷向上抽取過程中。出現了集合體系。
在使用一個體系時,原則:參閱頂層内容。建立底層對象。
1 Iterator接口
1.1 Iterator
< java.util >-- 疊代器:是一個接口—Iterator接口,其作用:用于取集合中的元素。
在Iterator接口中定義了三個方法:
| hasNext 如果仍有元素可以疊代,則傳回true。 |
E | next 傳回疊代的下一個元素。 |
| remove 從疊代器指向的 collection 中移除疊代器傳回的最後一個元素(可選操作)。 |
每一個集合都有自己的資料結構(就是容器中存儲資料的方式),都有特定的取出自己内部元素的方式。為了便于操作所有的容器,取出元素。将容器内部的取出方式按照一個統一的規則向外提供,這個規則就是Iterator接口,使得對容器的周遊操作與其具體的底層實作相隔離,達到解耦的效果。
也就說,隻要通過該接口就可以取出Collection集合中的元素,至于每一個具體的容器依據自己的資料結構,如何實作的具體取出細節,這個不用關心,這樣就降低了取出元素和具體集合的耦合性。
Iterator it = coll.iterator();//擷取容器中的疊代器對象,至于這個對象是是什麼不重要。這對象肯定符合一個規則Iterator接口。
[java] view plain copy
- public static voidmain(String[] args) {
- Collection coll = new ArrayList();
- coll.add("abc0");
- coll.add("abc1");
- coll.add("abc2");
- //--------------方式1----------------------
- Iterator it = coll.iterator();
- while(it.hasNext()){
- System.out.println(it.next());
- }
- //---------------方式2用此種----------------------
- for(Iterator it =coll.iterator();it.hasNext(); ){
- System.out.println(it.next());
- }
- }
使用Iterator疊代器來進行删除,則不會出現并發修改異常。
因為:在執行remove操作時,同樣先執行checkForComodification(),然後會執行ArrayList的remove()方法,該方法會将modCount值加1,這裡我們将expectedModCount=modCount,使之保持統一。
1.2 ListIterator
上面可以看到,Iterator隻提供了删除元素的方法remove,如果我們想要在周遊的時候添加元素怎麼辦?
ListIterator接口繼承了Iterator接口,它允許程式員按照任一方向周遊清單,疊代期間修改清單,并獲得疊代器在清單中的目前位置。
使用ListIterator來對list進行邊周遊邊添加元素操作:
[java] view plain copy
- public static void main(String[] args)
- {
- ArrayList<String> aList = new ArrayList<String>();
- aList.add("bbc");
- aList.add("abc");
- aList.add("ysc");
- aList.add("saa");
- System.out.println("移除前:" + aList);
- ListIterator<String> listIt = aList.listIterator();
- while(listIt.hasNext())
- {
- if("abc".equals(listIt.next()))
- {
- listIt.add("haha");
- }
- }
- System.out.println("移除後:" + aList);
- }
2 Collection接口
--< java.util >--Collection接口:
Collection:
|--List:有序(元素存入集合的順序和取出的順序一緻),元素都有索引。元素可以重複。
|--Set:無序(存入和取出順序有可能不一緻),不可以存儲重複元素。必須保證元素唯一性。
1.添加:
add(object):添加一個元素
addAll(Collection) :添加一個集合中的所有元素。
2.删除:
clear():将集合中的元素全删除,清空集合。
remove(obj) :删除集合中指定的對象。注意:删除成功,集合的長度會改變。
removeAll(collection) :删除部分元素。部分元素和傳入Collection一緻。
3.判斷:
boolean contains(obj) :集合中是否包含指定元素 。
boolean containsAll(Collection) :集合中是否包含指定的多個元素。
boolean isEmpty():集合中是否有元素。
4.擷取:
int size():集合中有幾個元素。
5.取交集:
boolean retainAll(Collection) :對目前集合中保留和指定集合中的相同的元素。如果兩個集合元素相同,傳回flase;如果retainAll修改了目前集合,傳回true。
6.擷取集合中所有元素:
Iterator iterator():疊代器
7.将集合變成數組:
toArray();
2.1 List接口
--< java.util >-- List接口:
List本身是Collection接口的子接口,具備了Collection的所有方法。現在學習List體系特有的共性方法,查閱方法發現List的特有方法都有索引,這是該集合最大的特點。
List:有序(元素存入集合的順序和取出的順序一緻)元素都有索引。元素可以重複。(有序可重複)
|--ArrayList:底層的資料結構是數組,線程不同步,ArrayList替代了Vector,查詢元素的速度非常快。預設大小10,1.5倍長度擴容。
|--LinkedList:底層的資料結構是連結清單,線程不同步,增删元素的速度非常快。
|--Vector:底層的資料結構就是數組,線程同步,Vector無論查詢和增删都巨慢。預設大 小10,2倍長度擴容。
1.添加:
add(index,element) :在指定的索引位插入元素。
addAll(index,collection) :在指定的索引位插入一堆元素。
2.删除:
remove(index) :删除指定索引位的元素。 傳回被删的元素。
3.擷取:
Object get(index) :通過索引擷取指定元素。
int indexOf(obj):擷取指定元素第一次出現的索引位,如果該元素不存在傳回-1;
是以,通過-1,可以判斷一個元素是否存在。
int lastIndexOf(Object o) :反向索引指定元素的位置。
List subList(start,end):擷取子清單。
4.修改:
Object set(index,element) :對指定索引位進行元素的修改。
5.擷取所有元素:
ListIterator listIterator():list集合特有的疊代器。
List集合支援對元素的增、删、改、查。
List集合因為角标有了自己的擷取元素的方式: 周遊。
for(int x=0;x<list.size(); x++){
sop("get:"+list.get(x));
}
在進行list清單元素疊代的時候,如果想要在疊代過程中,想要對元素進行操作的時候,比如滿足條件添加新元素。會發生.ConcurrentModificationException并發修改異常。
導緻的原因是:
集合引用和疊代器引用在同時操作元素,通過集合擷取到對應的疊代器後,在疊代中,進行集合引用的元素添加,疊代器并不知道,是以會出現異常情況。
如何解決呢?
既然是在疊代中對元素進行操作,找疊代器的方法最為合适.可是Iterator中隻有hasNext,next,remove方法.通過查閱的它的子接口,ListIterator,發現該清單疊代器接口具備了對元素的增、删、改、查的動作。
ListIterator是List集合特有的疊代器。
ListIterator it =list.listIterator;//取代Iterator it = list.iterator;
方法摘要 | |
| add E 将指定的元素插入清單(可選操作)。 |
| hasNext 以正向周遊清單時,如果清單疊代器有多個元素,則傳回true(換句話說,如果 next 傳回一個元素而不是抛出異常,則傳回 true)。 |
| hasPrevious 如果以逆向周遊清單,清單疊代器有多個元素,則傳回true。 |
E | next 傳回清單中的下一個元素。 |
| nextIndex 傳回對 next 的後續調用所傳回元素的索引。 |
E | previous 傳回清單中的前一個元素。 |
| previousIndex 傳回對previous 的後續調用所傳回元素的索引。 |
| remove 從清單中移除由 next 或 previous 傳回的最後一個元素(可選操作)。 |
| set E 用指定元素替換 next 或 previous 傳回的最後一個元素(可選操作)。 |
可變長度數組的原理:
當元素超出數組長度,會産生一個新數組,将原數組的資料複制到新數組中,再将新的元素添加到新數組中。
ArrayList:是按照原數組的50%延長。構造一個初始容量為 10 的空清單。
Vector:是按照原數組的100%延長。
注意:對于list集合,底層判斷元素是否相同,其實用的是元素自身的equals方法完成的。是以建議元素都要複寫equals方法,建立元素對象自己的比較相同的條件依據。
LinkedList:的特有方法。
addFirst();
addLast();
在jdk1.6以後。
offerFirst();
offerLast();
getFirst():擷取連結清單中的第一個元素。如果連結清單為空,抛出NoSuchElementException;
getLast();擷取連結清單中的最後一個元素。如果連結清單為空,抛出NoSuchElementException;
在jdk1.6以後。
peekFirst();擷取連結清單中的第一個元素。如果連結清單為空,傳回null。
peekLast();
removeFirst():擷取連結清單中的第一個元素,但是會删除連結清單中的第一個元素。如果連結清單為空,抛出NoSuchElementException
removeLast();
在jdk1.6以後。
pollFirst();擷取連結清單中的第一個元素,但是會删除連結清單中的第一個元素。如果連結清單為空,傳回null。
pollLast();
2.2 Set接口
< java.util >-- Set集合無序,add()相同元素則添加失敗,傳回flase。:
資料結構:資料的存儲方式;
Set接口中的方法和Collection中方法一緻的。Set接口取出方式隻有一種,疊代器。
|--HashSet:底層資料結構是哈希表,HashSet是集合,無序,高效,線程不同步。
|--LinkedHashSet:存取順序一緻(用連結清單維護),線程不同步,是hashset的子類。
|--TreeSet:元素唯一,有序(按照元素自身執行順序),線程不同步(不按原有數組的順序)。TreeSet底層的資料結構就是二叉樹(平衡二叉排序樹)。
|--EnumSet 隻能儲存同一類型元素。
HashSet、TreeSet、LinkedHashSet的差別:HashSet隻去重,TreeSet去重并排序,LinkedHashSet去重并保留插入順序
===HashSet 哈希表原理===
采用哈希表存儲結構。
1:對對象元素中的關鍵字進行雜湊演算法運算,得結果為哈希值(也是這個元素的位置)。
2:存儲哈希值的結構,我們稱為哈希表,在哈希表中查找對應的哈希值對應位置,
3:如果哈希值出現沖突,再次判斷這個關鍵字對應的對象是否相同:
如果對象相同,就不存儲,因為元素重複;
如果對象不同,就存儲,在原來對象的哈希值基礎 +1順延。
4:既然哈希表根據哈希值存儲,為提高效率,最好保證對象關鍵字的唯一性。 可盡量少的判斷關鍵字對應的對象是否相同,提高了哈希表的操作效率。
高效:保證關鍵字唯一性,即為上述第三步所述,也可以用以下叙述:
HashSet集合保證元素唯一性:通過元素的hashCode()和equals()完成的。
當元素的hashCode值相同時,才繼續判斷元素的equals是否為true。
如果為true,那麼視為相同元素,不存。如果為false,那麼存儲。
如果hashCode值不同,那麼不判斷equals,進而提高對象比較的速度。
對于ArrayList集合,判斷元素是否存在,或者删元素底層依據都是equals方法。
對于HashSet集合,判斷元素是否存在,或者删除元素,底層依據的是hashCode方法和equals方法。
===TreeSet原理===
采用二叉樹(二叉平衡排序樹)存儲結構 (或紅黑樹)
TreeSet用于對Set集合進行元素的指定順序排序,要依據元素自身的比較性( 如果元素不具備比較性,在運作時會發生ClassCastException異常)是以需要元素實作Comparable接口,複寫compareTo方法(根據指定需求),強制讓對象元素具備比較性,否則比較時引發ClassCastException異常。
TreeSet支援兩種排序方法:自然排序和定制排序;預設采用自然排序。
原理:當把一個對象添(必須實作Comparable接口)加進TreeSet時,TreeSet調用該對象的compareTo(Objectobj)方法與容器中的其他對象比較大小,然後根據紅黑樹算法決定它的存儲位置。 如果兩個對象通過compareTo(Object obj)比較相等,return0,視為兩對象重複,不存儲。(通過此方法保證了對象的唯一性)
注意:在進行比較時,如果判斷元素不唯一,比如,同姓名,同年齡,才視為同一個人。
在判斷時,需要分主要、次要條件,當主要條件相同時,再判斷次要條件,按照次要條件排序。
TreeSet集合排序有兩種方式,Comparable和Comparator差別:
1:讓元素自身具備比較性,需要元素對象實作Comparable接口,覆寫compareTo方法。
2:讓集合自身具備比較性,需要定義一個實作了Comparator接口的比較器,并覆寫compare方法,并将該類對象作為實際參數傳遞給TreeSet集合的構造函數。第二種方式較為靈活。
3 Map接口
Map
|--Hashtable:底層是哈希散清單資料結構,線程同步。不可以存儲null鍵,null值。不可序列化,使用bucket結構體表示單個元素,使用雙重散列法(閉散列法)解決沖突(二度哈希,size>length時要進行模運算)。
|--HashMap:底層是哈希表資料結構(鍊位址法解決沖突),線程不同步。可存一個null鍵和多個null值。替代了Hashtable. 但可通過Map m = Collections.synchronizeMap(hashMap)實作同步;
|--LinkedHashMap,采用雙向連結清單資料結構連接配接起來所有的entry,保證了存入和取出順序一緻,即連結清單有序;線程不同步。
|--TreeMap:底層是二叉樹結構(平衡二叉排序樹),可以對map集合中的鍵進行指定順序的排序。
Map集合存儲和Collection有着很大不同:
Collection一次存一個元素,是單列集合;
Map一次存一對元素,是雙列集合。Map存儲的一對元素:鍵--值,鍵(key)與值(value)間有對應(映射)關系。
特點:要保證Map中鍵的唯一性。
1:添加。
put(key,value):當存儲的鍵相同時,新的值會替換老的值,并将老值傳回。如果鍵沒有重複,傳回null。
void putAll(Map);
2:删除。
void clear():清空
value remove(key) :删除指定鍵。
3:判斷。
boolean isEmpty():
boolean containsKey(key):是否包含key
boolean containsValue(value):是否包含value
4:取出。
int size():傳回長度
value get(key) :通過指定鍵擷取對應的值。如果傳回null,可以判斷該鍵不存在。當然有特殊情況,就是在hashmap集合中,是可以存儲null鍵null值的。
Collection values():擷取map集合中的所有的值。
5:想要擷取map中的所有元素
原理:map沒有疊代器,collection具備疊代器,隻要将map轉成Set集合,就可使用疊代器。之是以轉成set,是因為map集合具備鍵的唯一性,其實set集合就來自于map,set集合底層其實用的就是map的方法。
★ 把map集合轉成set的方法:(決定了兩種周遊方式)
Set keySet();
Set entrySet();//取的是鍵和值的映射關系。
Entry就是Map接口中的内部接口;
為什麼要定義在map内部呢?entry是通路鍵值關系的入口,是map的入口,通路的是map中的鍵值對。
---------------------------------------------------------
取出map集合中所有元素的方式一:keySet()方法。
可以将map集合中的鍵都取出存放到set集合中。對set集合進行疊代。疊代完成,再通過get方法對擷取到的鍵進行值的擷取。
[java] view plain copy
- Set keySet = map.keySet();
- Iterator it = keySet.iterator();
- while(it.hasNext()) {
- Object key = it.next();
- Objectvalue = map.get(key);
- System.out.println(key+":"+value); }
取出map集合中所有元素的方式二:entrySet()方法。
[java] view plain copy
- Set entrySet = map.entrySet();
- Iterator it =entrySet.iterator();
- while(it.hasNext()) {
- Map.Entry me =(Map.Entry)it.next();
- System.out.println(me.getKey()+"::::"+me.getValue());
- }
使用集合的技巧:
看到Array就是數組結構,有角标,查詢速度很快。
看到link就是連結清單結構:增删速度快,而且有特有方法。addFirst; addLast;removeFirst(); removeLast();getFirst();getLast();
看到hash就是哈希表,就要想要哈希值,就要想到唯一性,就要想到存入到該結構中的元素必須覆寫hashCode和equals方法。
看到tree就是二叉樹,就要想到排序,就想要用到比較。
比較的兩種方式:
一個是Comparable:覆寫compareTo方法;
一個是Comparator:覆寫compare方法。
LinkedHashSet,LinkedHashMap:這兩個集合可以保證哈希表有存入順序和取出順序一緻,保證哈希表有序。
集合使用場景?
當存儲一個元素時,用Collection。當存儲對象之間存在着映射關系時,用Map集合。
保證唯一,就用Set。不保證唯一,就用List。
4 綜合總結
4.1 集合工具Collections
Collections:集合工具類,它的出現給集合操作提供了更多的功能。這個類不需要建立對象,内部提供的都是靜态方法。
靜态方法:
Collections.sort(list);//list集合進行元素的自然順序排序。
Collections.sort(list,new ComparatorByLen());//按指定的比較器方法排序。
class ComparatorByLen implements Comparator<String>{
public int compare(String s1,String s2){
int temp = s1.length()-s2.length();
return temp==0?s1.compareTo(s2):temp;
}
}
Collections.max(list);//傳回list中字典順序最大的元素。
int index = Collections.binarySearch(list,"zz");//二分查找,傳回角标。
Collections.reverseOrder();//逆向反轉排序。
Collections.shuffle(list);//随機對list中的元素進行位置的置換。
将非同步集合轉成同步集合的方法:Collections中的 XXX synchronizedXXX(XXX);
List synchronizedList(list);
Map synchronizedMap(map);
原理:定義一個類,将集合所有的方法加同一把鎖後傳回。
Collection 和 Collections的差別:
Collections是個java.util下的類,是針對集合類的一個工具類,提供一系列靜态方法,實作對集合的查找、排序、替換、線程安全化(将非同步的集合轉換成同步的)等操作。
Collection是個java.util下的接口,它是各種集合結構的父接口,繼承于它的接口主要有Set和List,提供了關于集合的一些操作,如插入、删除、判斷一個元素是否其成員、周遊等。
4.2 數組 Arrays
用于操作數組對象的工具類,裡面都是靜态方法。
數組=》集合:asList方法,将數組轉換成list集合。
String[] arr ={"abc","kk","qq"};
List<String> list =Arrays.asList(arr);//将arr數組轉成list集合。
将數組轉換成集合,有什麼好處呢?用aslist方法,将數組變成集合;
可以通過list集合中的方法來操作數組中的元素:isEmpty()、contains、indexOf、set;
注意(局限性):數組是固定長度,不可以使用集合對象增加或者删除等,會改變數組長度的功能方法。比如add、remove、clear。(會報不支援操作異常UnsupportedOperationException);
如果數組中存儲的引用資料類型,直接作為集合的元素可以直接用集合方法操作。
如果數組中存儲的是基本資料類型,asList會将數組實體作為集合元素存在。
集合=》數組:用的是Collection接口中的toArray()方法;
如果給toArray傳遞的指定類型的資料長度小于了集合的size,那麼toArray方法,會自定再建立一個該類型的資料,長度為集合的size。
如果傳遞的指定的類型的數組的長度大于了集合的size,那麼toArray方法,就不會建立新數組,直接使用該數組即可,并将集合中的元素存儲到數組中,其他為存儲元素的位置預設值null。
是以,在傳遞指定類型數組時,最好的方式就是指定的長度和size相等的數組。
将集合變成數組後有什麼好處?限定了對集合中的元素進行增删操作,隻要擷取這些元素即可。
4.3 LinkedHashSet和LinkedHashMap比較
兩者實作相同,隻是前者對後者做了一層包裝,即LinkedHashSet裡面有一個LinkedHashMap(擴充卡模式)。下面說其實作。
LinkedHashMap,可存null鍵null值,從名字上可以看出是linkedlist和HashMap的混合體,同時滿足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增強的HashMap。
事實上LinkedHashMap是HashMap的直接子類,LinkedHashMap在HashMap的基礎上采用雙向連結清單(doubly-linked list)的形式将所有entry連接配接起來,保證元素的疊代順序跟插入順序相同。
除了疊代順序不變,還有一個好處:疊代時不需要周遊整個table,隻需要直接周遊header指針指向的雙向連結清單即可,(LinkedHashMap的疊代時間就隻跟entry的個數相關,而跟table的大小無關。)
有兩個參數可以影響LinkedHashMap的性能:初始容量(initalcapacity)和負載系數(load factor)。初始容量指定了初始table的大小,負載系數用來指定自動擴容的臨界值。當entry的數量超過capacity*load_factor時,容器将自動擴容并重新哈希。對于插入元素較多的場景,将初始容量設大可以減少重新哈希的次數。
向LinkedHashMap或LinkedHashSet添加對象時,需要關心兩個方法:hashCode()方法決定了對象會被放到哪個bucket裡,當多個對象的哈希值沖突時,equals()方法決定了這些對象是否是“同一個對象”。此時需要将自定義的對象 *@Override*hashCode()和equals()方法。
5 Java集合常見題目
1.Java集合類架構的基本接口有哪些?
Java集合類提供了一套設計良好的支援對一組對象進行操作的接口和類。Java集合類裡面最基本的接口有:
Collection:代表一組對象,每一個對象都是它的子元素。
Set:不包含重複元素的Collection。
List:有順序的collection,并且可以包含重複元素。
Map:可以把鍵(key)映射到值(value)的對象,鍵不能重複。
2.為什麼集合類沒有實作Cloneable和Serializable接口?
集合類接口指定了一組叫做元素的對象。集合類接口的每一種具體的實作類都可以選擇以它自己的方式對元素進行儲存和排序。有的集合類允許重複的鍵,有些不允許。
克隆(cloning)或者是序列化(serialization)的語義和含義是跟具體的實作相關的。是以,應該由集合類的具體實作來決定如何被克隆或者是序列化。
3.什麼是疊代器(Iterator)?
Iterator接口提供了很多對集合元素進行疊代的方法。每一個集合類都包含了可以傳回疊代器執行個體的疊代方法。疊代器可以在疊代的過程中删除底層集合的元素,安全。
4.Iterator和ListIterator的差別是什麼?
=》Iterator可用來周遊Set和List集合,但是ListIterator隻能用來周遊List。
=》Iterator對集合隻能是前向周遊,ListIterator既可以前向也可以後向。
=》ListIterator實作了Iterator接口,并包含其他的功能,比如:增加元素,替換元素,擷取前一個和後一個元素的索引,等等。
5.快速失敗(fail-fast)和安全失敗(fail-safe)的差別是什麼?
Iterator的安全失敗是基于對底層集合做拷貝,是以,它不受源集合上修改的影響。java.util包下面的所有的集合類都是快速失敗的,而java.util.concurrent包下面的所有的類都是安全失敗的。快速失敗的疊代器會抛出ConcurrentModificationException異常,而安全失敗的疊代器永遠不會抛出這樣的異常。
6.Java中的HashMap的工作原理是什麼?
Java中的HashMap是以鍵值對(key-value)的形式存儲元素的。HashMap需要一個hash函數,它使用hashCode()和equals()方法來向集合/從集合添加和檢索元素。
當調用put()方法的時候,HashMap會計算key的hash值,然後把鍵值對存儲在集合中合适的索引上。如果key已經存在了,value會被更新成新值。HashMap的一些重要的特性是它的容量(capacity),負載因子(load factor)和擴容極限(threshold resizing)。
擴容牽扯到rehash的過程:增加1倍,然後重新計算hash值并且搬運元素到新的哈希表當中。
get()方法,同樣是……
7. hashCode()和equals()方法的重要性展現在什麼地方?
Java中的HashMap使用hashCode()和equals()方法來确定鍵值對的索引,當根據鍵擷取值的時候也會用到這兩個方法。如果沒有正确的實作這兩個方法,兩個不同的鍵可能會有相同的hash值,是以,可能會被集合認為是相等的。而且,這兩個方法也用來發現重複元素。是以這兩個方法的實作對HashMap的精确性和正确性是至關重要的。
8.HashMap和Hashtable有什麼差別?
HashMap和Hashtable都實作了Map接口,很多特性相似。但有不同點:
HashMap允許鍵和值是null,而Hashtable不允許鍵或者值是null。
Hashtable是同步的,而HashMap不是。是以,HashMap更适合于單線程環境,而Hashtable适合于多線程環境。
HashMap提供了可供應用疊代的鍵的集合keySet(),是以,HashMap是快速失敗fast-fail的。
另一方面,Hashtable提供了對鍵的列舉(Enumeration)。一般認為Hashtable是一個遺留的類。
9.數組(Array)和清單(ArrayList)有什麼差別?什麼時候應該使用Array而不是ArrayList?
不同點:
定義上:Array可以包含基本類型和對象類型,ArrayList隻能包含對象類型。
容量上:Array大小固定,ArrayList的大小是動态變化的。
操作上:ArrayList提供更多的方法和特性,如:addAll(),removeAll(),iterator()等等。
使用基本資料類型或者知道資料元素數量的時候可以考慮Array;
ArrayList處理固定數量的基本類型資料類型時會自動裝箱來減少編碼工作量,但是相對較慢。
10.ArrayList和LinkedList有什麼差別?
兩者都實作了List接口,他們有以下不同點:
資料結構上:
ArrayList是基于索引的數組形式,可随機通路元素, 時間複雜度O(1);
LinkedList是元素清單的形式存儲它的資料,每一個元素都和它的前一個和後一個元素連結在一起,在這種情況下,查找某個元素的時間複雜度是O(n)。
操作上:
ArrayList添加,删除操作比較慢,重新計算大小或者是更新索引。
LinkedList的插入,添加,删除操作速度更快,不需要更新索引。
記憶體上:
LinkedList比ArrayList更占記憶體,因為LinkedList為每一個節點存儲了兩個引用,一個指向前一個元素,一個指向下一個元素。
11.Comparable和Comparator接口是幹什麼的?列出它們的差別。
Java提供了隻包含一個compareTo()方法的Comparable接口。這個方法可以個給兩個對象排序。具體來說,它傳回負數,0,正數來表明輸入對象小于,等于,大于已經存在的對象。
Java提供了包含compare()和equals()兩個方法的Comparator接口。compare()方法用來給兩個輸入參數排序,傳回負數,0,正數表明第一個參數是小于,等于,大于第二個參數。equals()方法需要一個對象作為參數,它用來決定輸入參數是否和comparator相等。隻有當輸入參數也是一個comparator并且輸入參數和目前comparator的排序結果是相同的時候,這個方法才傳回true。
12.什麼是Java優先級隊列(Priority Queue)?
PriorityQueue是一個基于優先級堆的無界有序隊列,它的元素是按照自然順序(natural order)排序的。在建立的時候,我們可以給它提供一個負責給元素排序的比較器。PriorityQueue不允許null值,因為他們沒有自然順序,或者說他們沒有任何的相關聯的比較器。最後,PriorityQueue不是線程安全的,入隊和出隊的時間複雜度是O(log(n))。
13.你了解大O符号(big-O notation)麼?你能給出不同資料結構的例子麼?
大O:描述了當資料結構裡面的元素增加的時候,算法的規模或者是性能在最壞的場景下有多麼好。
大O符号也可用來描述其他的行為,比如:記憶體消耗。因為集合類實際上是資料結構,我們一般使用大O符号基于時間,記憶體和性能來選擇最好的實作。大O符号可以對大量資料的性能給出一個很好的說明。
14.如何權衡是使用無序的數組還是有序的數組?
有序數組最大的好處在于查找的時間複雜度是O(log n),而無序數組是O(n)。有序數組的缺點是插入操作的時間複雜度是O(n),因為值大的元素需要往後移動來給新元素騰位置。相反,無序數組的插入時間複雜度是常量O(1)。
是以,查找操作多的時候,使用有序;增删操作多的使用無序的即可。
15.Java集合類架構的最佳實踐有哪些?
根據應用的需要正确選擇要使用的集合的類型對性能非常重要,比如:假如元素的大小是固定的,而且能事先知道,我們就應該用Array而不是ArrayList。
有些集合類允許指定初始容量。是以,如果我們能估計出存儲的元素的數目,我們可以設定初始容量來避免重新計算hash值或者是擴容。
為了類型安全,可讀性和健壯性的原因總是要使用泛型。同時,使用泛型還可以避免運作時的ClassCastException。
使用JDK提供的不變類(immutable class)作為Map的鍵可以避免為我們自己的類實作hashCode()和equals()方法。
程式設計的時候接口優于實作。
底層的集合實際上是空的情況下,傳回長度是0的集合或者是數組,不要傳回null。
16.Enumeration接口和Iterator接口的差別有哪些?
Enumeration速度是Iterator的2倍,同時占用更少的記憶體。
但是,Iterator遠遠比Enumeration安全,因為其他線程不能夠修改正在被iterator周遊的集合裡面的對象。同時,Iterator允許調用者删除底層集合裡面的元素,這對Enumeration來說是不可能的。
17.HashSet和TreeSet有什麼差別?
HashSet是由一個哈希表來實作的,元素無,add(),remove(),contains()方法的時間複雜度是O(1)。
另一方面,TreeSet是由一個樹形結構(平衡二叉排序樹)來實作的,它裡面的元素是有序的。是以,add(),remove(),contains()方法的時間複雜度是O(logn)。
5.1集合架構基礎
1.Java集合架構是什麼?說出一些集合架構的優點?
每種程式設計語言中都有集合,最初的Java版本包含幾種集合類:Vector、Stack、HashTable和Array。随着集合的廣泛使用,Java1.2提出了囊括所有集合接口、實作和算法的集合架構。在保證線程安全的情況下使用泛型和并發集合類,Java已經經曆了很久。它還包括在Java并發包中,阻塞接口以及它們的實作。集合架構的部分優點如下:
(1)使用核心集合類降低開發成本,而非實作我們自己的集合類。
(2)随着使用經過嚴格測試的集合架構類,代碼品質會得到提高。
(3)通過使用JDK附帶的集合類,可以降低代碼維護成本。
(4)複用性和可操作性。
2.集合架構中的泛型有什麼優點?
Java1.5引入了泛型,所有的集合接口和實作都大量地使用它。
泛型允許我們為集合提供一個可以容納的對象類型,是以,如果你添加其它類型的任何元素,它會在編譯時報錯。這避免了在運作時出現ClassCastException,因為你将會在編譯時得到報錯資訊。泛型也使得代碼整潔,我們不需要使用顯式轉換和instanceOf操作符。
它也給運作時帶來好處,因為不會産生類型檢查的位元組碼指令。
3.Java集合架構的基礎接口有哪些?
Collection為集合層級的根接口。一個集合代表一組對象,這些對象即為它的元素。Java平台不提供這個接口任何直接的實作。
Set是一個不能包含重複元素的集合。這個接口對數學集合抽象進行模組化,被用來代表集合,就如一副牌。
List是一個有序集合,可以包含重複元素。你可以通過它的索引來通路任何元素。List更像長度動态變換的數組。
Map是一個将key映射到value的對象.一個Map不能包含重複的key:每個key最多隻能映射一個value。
一些其它的接口有Queue、Dequeue、SortedSet、SortedMap和ListIterator。
4.為何Collection不從Cloneable和Serializable接口繼承?
Collection接口指定一組對象,對象即為它的元素。如何維護這些元素由Collection的具體實作決定。例如,一些如List的Collection實作允許重複的元素,而其它的如Set就不允許。很多Collection實作有一個公有的clone方法。然而,把它放到集合的所有實作中也是沒有意義的。這是
因為Collection是一個抽象表現,而重要的是實作。
當與具體實作打交道的時候,克隆或序列化的語義和含義才發揮作用。是以,具體實作應該決定如何對它進行克隆或序列化,或它是否可以被克隆或序列化。
在所有的實作中授權克隆和序列化,最終導緻更少的靈活性和更多的限制。特定的實作應該決定它是否可以被克隆和序列化。
5.為何Map接口不繼承Collection接口?
盡管Map接口和它的實作也是集合架構的一部分,但Map不是集合,集合也不是Map。是以,Map繼承Collection無論誰繼承誰都毫無意義。
如果Map繼承Collection接口,那麼元素去哪兒?Map包含key-value對,它提供抽取key或value清單集合的方法,但是它不适合“一組對象”規範。
5.2 Iterator
6.Iterator是什麼?
Iterator接口提供周遊任何Collection的接口。我們可以從一個Collection中使用疊代器方法來擷取疊代器執行個體。疊代器取代了Java集合架構中的Enumeration。疊代器允許調用者在疊代過程中移除元素。
7.Enumeration和Iterator接口的差別?
Enumeration的速度是Iterator的兩倍,使用更少的記憶體。Enumeration是非常基礎的,也滿足了基礎的需要。但是,Iterator更加安全,因為當一個集合正在被周遊的時候,它會阻止其它線程去修改集合。
疊代器取代了Java集合架構中的Enumeration,并允許調用者從集合中移除元素,而Enumeration不能做到。為了使它的功能更加清晰,疊代器方法名已經經過改善。
8.為何沒有像Iterator.add()這樣的方法,向集合中添加元素?
語義不明,已知的是,Iterator的協定不能確定疊代的次序。然而要注意,ListIterator沒有提供一個add操作,它要確定疊代的順序。
9.為何疊代器沒有一個方法可以直接擷取下一個元素,而不需要移動遊标?
它可以在目前Iterator的頂層實作,但是它用得很少,如果将它加到接口中,每個繼承都要去實作它,這沒有意義。
10.Iterater和ListIterator之間有什麼差別?
(1)我們可以使用Iterator來周遊Set和List集合,而ListIterator隻能周遊List。
(2)Iterator隻可以向前周遊,而ListIterator可以雙向周遊。
(3)ListIterator從Iterator接口繼承,然後添加了一些額外的功能,比如添加一個元素、替換一個元素、擷取前面或後面元素的索引位置。
11.周遊一個List有哪些不同的方式?
[java] view plain copy使用疊代器更加線程安全,因為它可以確定,在目前周遊的集合元素被更改的時候,它會抛出ConcurrentModificationException。
- List<String> strList = new ArrayList<>();
- //使用for-each循環
- for(String obj : strList){
- System.out.println(obj);
- }
- //using iterator
- Iterator<String> it = strList.iterator();
- while(it.hasNext()){
- String obj = it.next();
- System.out.println(obj);
- }
12.通過疊代器fail-fast屬性,你明白了什麼?
每次嘗試擷取下一個元素時,Iterator fail-fast屬性檢查目前集合結構裡的任何改動。如有改動,則抛出異常ConcurrentModificationException。Collection中所有Iterator的實作都是按fail-fast來設計的(ConcurrentHashMap和CopyOnWriteArrayList這類并發集合類除外)。
13.fail-fast與fail-safe有什麼差別?
(1)Java.util包中的所有集合類都被設計為fail-fast的,而java.util.concurrent中的集合類都為fail-safe的。
(2)fail-fast檢測集合結構改變的原理,Iterator直接通路集合的資料結構,它保留一個标志”mods”,在Iterator每次調用hasNext()或者是next()方法時,首先檢測”mods”狀态,如果結構已經改變,則抛出異常。
fail-safe Iterator的實作原理是,先将原集合拷貝一份,在拷貝上開展周遊,是以不會引起ConcurrentModification異常。是以,Fail Safe Iterator存在兩個缺陷: 額外的空間開銷 和周遊資料不一定是最新的。
14.在疊代一個集合的時候,如何避免ConcurrentModificationException?
在周遊一個集合的時候,我們可以使用并發集合類來避免ConcurrentModificationException,比如使用CopyOnWriteArrayList,而不是ArrayList。
即使用java.uitl.concurrenet中的集合類代替java.util包下的集合類。
15.為何Iterator接口沒有具體的實作?
Iterator接口定義了周遊集合的方法,但它的實作則是集合實作類的責任。每個能夠傳回用于周遊的Iterator的集合類都有它自己的Iterator實作内部類。
這就允許集合類去選擇疊代器是fail-fast還是fail-safe的。比如,ArrayList疊代器是fail-fast的,而CopyOnWriteArrayList疊代器是fail-safe的。
16.UnsupportedOperationException是什麼?
UnsupportedOperationException是用于表明操作不支援的異常。在JDK類中已被大量運用,在集合架構java.util.Collections.UnmodifiableCollection将會在所有add和remove操作中抛出這個異常。
5.3 Map/List/Set/Queue/Stack
17.在Java中,HashMap是如何工作的?
HashMap在Map.Entry靜态内部類實作中存儲key-value鍵值對。使用“數組和連結清單”的存儲結構,總體使用“鍊位址法”來解決哈希沖突。
HashMap使用雜湊演算法,在put和get方法中,它都使用了hashCode()和equals()方法。
put()方法:首先,HashMap使用Key hashCode()和雜湊演算法來找出存儲key-value對的索引。Entry存儲在LinkedList中,是以如果存在entry,它使用equals()方法來檢查傳遞的key是否已經存在,如果存在,它會覆寫value,如果不存在,它會建立一個新的entry然後儲存。
get()方法:當我們通過傳遞key調用get方法時,它再次使用hashCode()來找到數組中的索引,然後使用equals()方法找出正确的Entry,然後傳回它的值。
其它關于HashMap比較重要的問題是容量、負荷系數和閥值調整。HashMap預設的初始容量是32,負荷系數是0.75。閥值是為負荷系數乘以容量,無論何時我們嘗試添加一個entry,如果map的大小比閥值大的時候,HashMap會對map的内容進行重新哈希Rehash,且使用更大的容量。容量總是2的幂,是以如果你知道你需要存儲大量的key-value對,比如緩存從資料庫裡面拉取的資料,使用正确的容量和負荷系數對HashMap進行初始化是個不錯的做法。
Rehash算法:如果哈希位址不夠,要對hash表進行擴容,擴容為原來的2倍,然後将原來hash表中的所有計算好hash位址的元素重新計算hashCode,并且搬到擴容後的hash表後的LinkedList連結清單中。
18.hashCode()和equals()方法有何重要性?
HashMap使用Key對象的hashCode()和equals()方法去決定key-value對的索引。當我們試着從HashMap中擷取值的時候,這些方法也會被用到。如果這些方法沒有被正确地實作,在這種情況下,兩個不同Key也許會産生相同的hashCode()和equals()輸出,HashMap将會認為它們是相同的,然後覆寫它們,而非把它們存儲到不同的地方。同樣的,所有不允許存儲重複資料的集合類都使用hashCode()和equals()去查找重複,是以正确實作它們非常重要。equals()和hashCode()的實作應該遵循以下規則:
(1)如果o1.equals(o2),那麼o1.hashCode() == o2.hashCode()總是為true的。
(2)如果o1.hashCode() == o2.hashCode(),并不意味着o1.equals(o2)會為true。
19.我們能否使用任何類作為Map的key?
我們可以使用任何類作為Map的key,然而在使用它們之前,需要考慮以下幾點:
(1)如果類重寫了equals()方法,它也應該重寫hashCode()方法。
(2)類的所有執行個體需要遵循與equals()和hashCode()相關的規則。(請參考之前提到的這些規則)
(3)如果一個類沒有使用equals(),你不應該在hashCode()中使用它。
(4)使用者自定義key類的最佳實踐是使之為不可變的,這樣,hashCode()值可以被緩存起來,擁有更好的性能。不可變的類也可以確定hashCode()和equals()在未來不會改變,這樣就會解決與可變相關的問題了。
比如,我有一個類MyKey,在HashMap中使用它。
[java] view plain copy那就是為何String和Integer這些不可變類被作為HashMap的key大量使用(原因就是防止可變類的修改導緻再次利用key查找索引的時候不可複現原來的索引,即查找索引失敗)。
- //傳遞給MyKey的name參數被用于equals()和hashCode()中
- MyKey key = new MyKey('Pankaj'); //assume hashCode=1234
- myHashMap.put(key, 'Value');
- // 以下的代碼會改變key的hashCode()和equals()值
- key.setName('Amit'); //assume new hashCode=7890
- //下面會傳回null,因為HashMap會嘗試查找存儲同樣索引的key,而key已被改變了,比對失敗,傳回null
- myHashMap.get(new MyKey('Pankaj'));
20.Map接口提供了哪些不同的集合視圖?
Map接口提供三個集合視圖:
(1)Set keyset():傳回map中包含的所有key的一個Set視圖。集合是受map支援的,map的變化會在集合中反映出來,反之亦然。當一個疊代器正在周遊一個集合時,若map被修改了(除疊代器自身的移除操作以外),疊代器的結果會變為未定義。集合支援通過Iterator的Remove、Set.remove、removeAll、retainAll和clear操作進行元素移除,從map中移除對應的映射。它不支援add和addAll操作。
(2)Collectionvalues():傳回一個map中包含的所有value的一個Collection視圖。這個collection受map支援的,map的變化會在collection中反映出來,反之亦然。當一個疊代器正在周遊一個collection時,若map被修改了(除疊代器自身的移除操作以外),疊代器的結果會變為未定義。集合支援通過Iterator的Remove、Set.remove、removeAll、retainAll和clear操作進行元素移除,從map中移除對應的映射。它不支援add和addAll操作。
(3)Set<Map.Entry<K,V>>entrySet():傳回一個map鐘包含的所有映射的一個集合視圖。這個集合受map支援的,map的變化會在collection中反映出來,反之亦然。當一個疊代器正在周遊一個集合時,若map被修改了(除疊代器自身的移除操作,以及對疊代器傳回的entry進行setValue外),疊代器的結果會變為未定義。集合支援通過Iterator的Remove、Set.remove、removeAll、retainAll和clear操作進行元素移除,從map中移除對應的映射。它不支援add和addAll操作。
21.HashMap和HashTable有何不同?
(1)HashMap允許key和value為null,而HashTable不允許。
(2)HashTable是同步的、線程安全的,而HashMap是線程不安全的;是以HashMap适合單線程環境,HashTable适合多線程環境。
(3)在Java1.4中引入了LinkedHashMap,HashMap的一個子類,假如你想要周遊順序,你很容易從HashMap轉向LinkedHashMap,但是HashTable不是這樣的,它的順序是不可預知的。
(4)HashMap提供對key的Set進行周遊,是以它是fail-fast的,但HashTable提供對key的Enumeration進行周遊,它不支援fail-fast。
(5)HashTable被認為是個遺留的類,如果你尋求在疊代的時候修改Map,你應該使用CocurrentHashMap。
22.如何決定選用HashMap還是TreeMap?
在Map中,插入、删除和定位元素等操作,選擇HashMap;如要有序周遊key集合,選擇TreeMap。
基于你的collection的大小,也許向HashMap中添加元素會更快,将map換為TreeMap進行有序key的周遊。
23.ArrayList和Vector有何異同點?
相同點:
(1)兩者都是基于索引的,都是基于數組的。
(2)兩者都維護插入順序,我們可以根據插入順序來擷取元素。
(3)ArrayList和Vector的疊代器實作都是fail-fast的。
(4)ArrayList和Vector兩者允許null值,也可以使用索引值對元素進行随機通路。
不同點:
(1)Vector是同步,線程安全,而ArrayList非同步,線程不安全。對于ArrayList,如果疊代時改變清單,應該使用CopyOnWriteArrayList。
(2)但是,ArrayList比Vector要快,它因為有同步,不會過載。
(3)在使用上,ArrayList更加通用,因為Collections工具類容易擷取同步清單和隻讀清單。
24.Array和ArrayList有何差別?什麼時候更适合用Array?
Array不如ArrayList的地方:
Array容納基本類型和對象,而ArrayList隻能容納對象。
Array是大小指定後被固定了,而ArrayList大小是固定的。
Array沒有提供ArrayList那麼多功能,比如addAll、removeAll和iterator等。
但有時候Array比較好用:
(1)如果清單的大小已經指定,大部分情況下是存儲和周遊它們。
(2)對于周遊基本資料類型,盡管Collections使用自動裝箱來減輕編碼任務,在指定大小的基本類型的清單上工作也會變得很慢。
(3)如果你要使用多元數組,使用[][]比List<List<>>更容易。
25.ArrayList和LinkedList有何差別?
兩者都實作了List接口,但有不同之處:
(1)ArrayList是一個基于Array和索引的資料結構的實作,在周遊上:可随機通路元素,複雜度為O(1);
LinkedList是一個基于連結清單的資料結構的實作,存儲的節點資料都隻與前一個和下一個節點相連接配接。在周遊上:盡管可以利用索引擷取元素,但是内部實作依舊是從起始點開始周遊,周遊到索引的節點然後傳回元素,時間複雜度為O(n),速度上比ArrayList要慢。
(2)與ArrayList相比,在LinkedList中插入、添加和删除一個元素會更快,因為在一個元素被插入到中間的時候,不會涉及改變數組的大小和更新索引(資料元素的移動)。
(3)LinkedList比ArrayList消耗更多的記憶體,因為LinkedList中的每個節點存儲了前後節點的引用;并且LinkedList空間使用率也低于ArrayList,這是基于他們的資料結構的。
26.哪些集合類提供對元素的随機通路?
ArrayList、HashMap、TreeMap和HashTable類提供對元素的随機通路。
27.EnumSet是什麼?
java.util.EnumSet是使用枚舉類型的集合實作。當集合建立時,枚舉集合中的所有元素必須來自單個指定的枚舉類型,可以是顯示的或隐示的。EnumSet是不同步的,不允許值為null的元素。它也提供了一些有用的方法,比如copyOf(Collection c)、of(E first,E…rest)和complementOf(EnumSet s)。
28.哪些集合類是線程安全的?
Vector、HashTable、Properties和Stack是同步類,線程安全的,可以在多線程環境下使用。Java1.5并發API包括一些集合類,允許疊代時修改,因為它們都工作在集合的克隆上,是以它們在多線程環境中是安全的。
29.并發集合類是什麼?
Java1.5并發包(java.util.concurrent)包含線程安全集合類,允許在疊代時修改集合。疊代器被設計為fail-fast的,會抛出ConcurrentModificationException。一部分類為:CopyOnWriteArrayList、 ConcurrentHashMap、CopyOnWriteArraySet。
30.BlockingQueue是什麼?
Java.util.concurrent.BlockingQueue是一個隊列,該接口是Java集合架構的一部分,主要用于實作生産者-消費者模式:檢索或移除元素時,會等待隊列變為非空;添加元素時,會等待隊列中可用空間。
我們不需要擔心等待生産者有可用的空間,或消費者有可用的對象,因為它都在BlockingQueue的實作類中被處理了。
Java提供了集中BlockingQueue的實作,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。
31.隊列和棧是什麼,列出它們的差別?
棧和隊列兩者都被用來預存儲資料。
隊列:java.util.Queue是一個接口,它的實作類在Java并發包中,允許先進先出(FIFO)檢索元素,但并非總是這樣。Deque接口允許從兩端檢索元素。
棧Stack:是一個擴充自Vector的類,但它允許對元素進行後進先出(LIFO)進行檢索。
而Queue是一個接口。
32.Collections類是什麼?
Java.util.Collections是一個工具類僅包含靜态方法,它們操作或傳回集合。它包含操作集合的多态算法,傳回一個由指定集合支援的新集合和其它一些内容。
這個類包含集合架構算法的方法,比如折半搜尋、排序、混編和逆序等。
5.4排序
33.Comparable和Comparator接口是什麼?
Comparable接口:使用Array或Collection的排序方法時,自定義類需要實作Java提供Comparable接口的compareTo(TOBJ)方法,它被排序方法所使用,應該重寫這個方法,如果“this”對象比傳遞的對象參數更小、相等或更大時,它傳回一個負整數、0或正整數。
使用Comparator接口的情景:在大多數實際情況下,我們想根據不同參數進行排序。比如,作為一個CEO,我想對雇員基于薪資進行排序,一個HR想基于年齡對他們進行排序。這就是我們需要使用Comparator接口的情景。因為Comparable.compareTo(Object o)方法實作隻能基于一個字段進行排序,不能根據需要選擇對象字段來對對象進行排序。
Comparator接口:可以實作兩個對象的特定字段的比較(比如,比較員工這個對象的年齡),該接口的compare(Objecto1, Object o2)方法的實作需要傳遞兩個對象參數,若第一個參數小于、等于、大于第二個參數,傳回負整數、0、正整數。
34.Comparable和Comparator接口有何差別?
Comparable和Comparator接口被用來對對象集合或者數組進行排序。
Comparable接口被用來提供對象的自然排序,可使用它來提供基于單個邏輯的排序。
Comparator接口被用來提供不同的排序算法,可根據制定字段選擇需要使用的Comparator來對指定的對象集合進行排序。
35.我們如何對一組對象進行排序?
對對象數組排序,可使用Arrays.sort()方法;
對對象清單排序,可使用Collection.sort()方法。
這兩個類都有用于自然排序(使用Comparable)或基于标準的排序(使用Comparator)的重載方法sort()。Collections内部使用數組排序方法,所有它們兩者都有相同的性能,隻是Collections需要花時間将清單轉換為數組。
36.當一個集合被作為參數傳遞給一個函數時,如何才可以確定函數不能修改它?
集合作為參數傳遞之前,可使用Collections.unmodifiableCollection(Collectionc)方法來建立為隻讀集合,将確定修改集合時抛出不支援修改操作的異常UnsupportedOperationException。
37.如何從給定集合那裡建立一個synchronized的集合?
我們可以使用Collections.synchronizedCollection(Collectionc)根據指定集合來擷取一個synchronized(線程安全的)集合。
38.集合架構裡實作的通用算法有哪些?
Java集合架構提供常用的算法實作,比如排序和檢索,Collections類包含這些方法實作。大部分算法是操作List的,但一部分對所有類型的集合都是可用的。部分算法有排序、搜尋、混編、最大最小值。
39.大寫的O是什麼?舉幾個例子?
大寫的O描述的是,就資料結構中的一系列元素而言,一個算法的性能。Collection類就是實際的資料結構,我們通常基于時間、記憶體和性能,使用大寫的O來選擇集合實作。
比如:例子1:ArrayList的get(index i)是一個常量時間操作,它不依賴list中元素的數量。是以它的性能是O(1)。例子2:一個對于數組或清單的線性搜尋的性能是O(n),因為我們需要周遊所有的元素來查找需要的元素。
40.與Java集合架構相關的有哪些最好的實踐?
(1)根據需要選擇正确的集合類型。若指定大小,選用Array而非ArrayList;若要根據插入順序周遊一個Map,使用TreeMap。若不需要重複元素,應該使用Set。
(2)一些集合類允許指定初始容量,是以如果我們能夠估計到存儲元素的數量,我們可以使用它,就避免了重新哈希或大小調整。
(3)基于接口程式設計,而非基于實作程式設計,它允許我們後來輕易地改變實作。
(4)總是使用類型安全的泛型,避免在運作時出現ClassCastException。
(5)使用JDK提供的不可變類作為Map的key,可以避免自己實作hashCode()和equals()。
(6)盡可能使用Collections工具類,或者擷取隻讀、同步或空的集合,而非編寫自己的實作。它将會提供代碼重用性,它有着更好的穩定性和可維護性。