一、集合類 集合的由來: 面向對象語言對事物都是以對象的形式來體現,為了方便對多個對象的操作,就需要將對象進行存儲,集合就是存儲對象最常用的一種方式。 集合特點: 1,用於存儲對象的容器。(容器本身就是一個對象,存在於堆記憶體中,裡面存的是對象的地址)2,集合的長度是可變的。3,集合中不可以存儲基本數 ...
一、集合類
集合的由來:
面向對象語言對事物都是以對象的形式來體現,為了方便對多個對象的操作,就需要將對象進行存儲,集合就是存儲對象最常用的一種方式。
集合特點:
1,用於存儲對象的容器。(容器本身就是一個對象,存在於堆記憶體中,裡面存的是對象的地址)
2,集合的長度是可變的。
3,集合中不可以存儲基本數據類型值。 (只能存對象)
小問題:想用集合存基本數據類型怎麼辦?
裝箱、拆箱。 例:al.add(5); // 相當於al.add(new Integer(5));
集合和數組的區別:
數組雖然也可以存儲對象,但長度是固定的,集合長度是可變的。
數組中可以存儲基本數據類型,集合只能存儲對象。
集合框架的構成及分類:(虛線為介面)
下麵分別整理集合框架中的幾個頂層介面。
二、 Collection介面
Collection子介面以及常用實現類:
Collection介面
|--List介面:有序(存入和取出的順序一致),元素都有索引(角標),元素可以重覆。
|--Vector:內部是 數組 數據結構,是同步的。增刪,查詢都很慢!100%延長(幾乎不用了)
|--ArrayList:內部是 數組 數據結構,是不同步的。替代了Vector,查詢的速度快,增刪速度慢。50%延長。(查詢時是從容器的第一個元素往後找,由於數組的記憶體空間是連續的,所以查詢快;增刪的話所有元素記憶體地址都要改變,所以增刪慢。)
|--LinkedList:內部是 鏈表 數據結構,是不同步的。增刪元素的速度很快。(同理,鏈表的記憶體空間是不連續的,所以查詢慢;增刪時只需改變單個指針的指向,所以快;)
|--Set介面:無序,元素不能重覆。Set介面中的方法和Collection一致。
|--HashSet: 內部數據結構是哈希表 ,是不同步的。
|--LinkedHashSet:內部數據結構是哈希表和鏈表,是有順序的HashSet。
|--TreeSet:內部數據結構是有序的二叉樹,它的作用是提供有序的Set集合,是不同步的。
List介面:
有一個最大的共性特點就是都可以操作角標,所以LinkedList也是有索引的。list集合可以完成對元素的增刪改查。
Set和List的區別:
1. Set 介面實例存儲的是無序的,不重覆的數據。List 介面實例存儲的是有序的,可以重覆的元素 <最本質區別>。
2. Set檢索效率低下,刪除和插入效率高,插入和刪除不會引起元素位置改變 。
3. List和數組類似,可以動態增長,根據實際存儲的數據的長度自動增長List的長度。查找元素效率高,插入刪除效率低,因為會引起其他元素位置改變 。
ArryList和Vector可變長度數組的原理:
當預設長度的數組不夠存儲時,會建立一個新數組。將原來數組的內容拷貝到新的數組當中,並將新增加的元素追加到拷貝完的數組尾,如果仍然不夠重覆上述動作。其中,ArryList的增加是以原來50%長度進行增加,而Vector是按照100%延長。
ArryList是線程不安全的,Vector是安全的:
由於是否有鎖的判斷將影響效率,故Arrylist效率遠遠高於Vector。而且只要是常用的容器就不是同步的,因為同步效率比較低。
ArryList存取對象的一個小例子:
Person p1 = new Person("lisi1",21); ArrayList al = new ArrayList(); al.add(p1); al.add(new Person("lisi2",22)); al.add(new Person("lisi3",23)); al.add(new Person("lisi4",24)); Iterator it = al.iterator(); while(it.hasNext()){ // System.out.println(((Person) it.next()).getName()+"::"+((Person) it.next()).getAge()); //錯誤方式:不能這樣取,next()一次指針會移動一次,會輸出“lisi1::22 lisi3::24” // 正確方式:拿到一個Person對象,然後取屬性。 Person p = (Person) it.next(); System.out.println(p.getName()+"--"+p.getAge()); }
HashSet之覆蓋hashCode方法和equals方法來保證元素唯一性
如何保證HashSet的元素唯一性呢?
是通過對象的hashCode和equals方法來完成對象唯一性的:
->如果對象的hashCode值不同,那麼不用判斷equals方法,就直接存儲到哈希表中。
->如果對象的hashCode值相同,那麼要再次判斷對象的equals方法是否為true:
如果為true,視為相同元素,不存;如果為false,那麼視為不同元素,就進行存儲。
記住:如果對象要存儲到HashSet集合中,該對象必須覆蓋hashCode方法和equals方法。
一般情況下,如果定義的類會產生很多對象,比如人,學生,書,通常都需要覆蓋equals,hashCode方法,以建立對象判斷是否相同的依據。
例:往HashSet集合中存儲Person對象。如果姓名和年齡相同,視為同一個人,視為相同元素。
import java.util.HashSet; import java.util.Iterator; class Person { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public int hashCode() { // System.out.println(this+".......hashCode"); return name.hashCode() + age * 27; // 乘以一個任意數,防止加了年齡以後HashCode仍相同 } @Override public boolean equals(Object obj) { // 健壯性判斷 if (this == obj) return true; if (!(obj instanceof Person)) throw new ClassCastException("類型錯誤"); // System.out.println(this+"....equals....."+obj); Person p = (Person) obj; return this.name.equals(p.name) && this.age == p.age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public String toString() { return name + ":" + age; } } public class HashSetTest { public static void main(String[] args) { HashSet hs = new HashSet(); /* * HashSet集合數據結構是哈希表,所以存儲元素的時候, * 使用的元素的hashCode方法來確定位置,如果位置相同,在通過元素的equals來確定是否相同。 * */ hs.add(new Person("lisi4", 24)); hs.add(new Person("lisi7", 27)); hs.add(new Person("lisi1", 21)); hs.add(new Person("lisi9", 29)); hs.add(new Person("lisi7", 27)); Iterator it = hs.iterator(); while (it.hasNext()) { Person p = (Person) it.next(); System.out.println(p); } } }
運行結果:
lisi1:21 lisi9:29 lisi4:24 lisi7:27
TreeSet之判斷元素唯一性的兩種方式(如何排序)
TreeSet預設判斷元素唯一性的方式:
根據Conpare介面的比較方法conpareTo的返回結果是否是0,是0,就是相同元素,不存。
下麵,我們給出兩種自定義判斷元素唯一性的方式:
方式一:
讓元素自身具備比較功能,即根據元素中的屬性來比較。採用這種方式需要元素實現Comparable介面,覆蓋compareTo方法。
例:往TreeSet集合中存儲Person對象。如果姓名和年齡相同,視為同一個人,視為相同元素。
import java.util.Iterator; import java.util.TreeSet; class Person implements Comparable { public String name; public int age; public Person() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } public String toString() { return name + ":" + age; } @Override public int compareTo(Object o) { Person p = (Person) o; /* 敲黑板劃重點,代碼簡潔方式 */ int temp = this.age - p.age; return temp == 0 ? this.name.compareTo(p.name) : temp; // 上面這兩句相當於底下這一段的簡潔形式 // if (this.age > p.age) // return 1; // if (this.age < p.age) // return -1; // else { // return this.name.compareTo(p.name); // } } public static void main(String[] args) { TreeSet<Person> ts = new TreeSet<Person>(); ts.add(new Person("zhangsan", 22)); ts.add(new Person("lisi", 27)); ts.add(new Person("wangermazi", 21)); ts.add(new Person("zhaosi", 25)); Iterator it = ts.iterator(); while (it.hasNext()) { Person person = (Person) it.next(); System.out.println(person.toString()); } } }
運行結果:
wangermazi:21 zhangsan:22 zhaosi:25 lisi:27
可以看到,覆寫compareTo方法後,元素根據age這個屬性進行了排序。
方式二:(開發用這個,掌握比較器的用法)
讓集合自身具備比較功能。自己寫一個比較器,先定義一個類實現Comparator介面,覆蓋compare方法。然後將該類對象作為參數傳遞給TreeSet集合的構造函數。
不再需要元素實現Conparable介面。
step1-新建比較器類ComparedByName.java,覆蓋compare方法:
import java.util.Comparator; public class ComparedByName implements Comparator { @Override public int compare(Object o1, Object o2) { // TODO Auto-generated method stub Person p1 = (Person) o1; Person p2 = (Person) o2; int temp = p1.name.compareTo(p2.name); return temp == 0 ? p1.age - p2.age : temp; } }
step2-將比較器類類對象作為參數傳遞給TreeSet集合的構造函數:
import java.util.Iterator; import java.util.TreeSet; class Person implements Comparable { public String name; public int age; public Person() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } public String toString() { return name + ":" + age; } @Override public int compareTo(Object o) { Person p = (Person) o; /* 敲黑板劃重點,代碼簡潔方式 */ int temp = this.age - p.age; return temp == 0 ? this.name.compareTo(p.name) : temp; // 上面這兩句相當於底下這一段的簡潔形式 // if (this.age > p.age) // return 1; // if (this.age < p.age) // return -1; // else { // return this.name.compareTo(p.name); // } } public static void main(String[] args) { TreeSet<Person> ts = new TreeSet<Person>(new ComparedByName()); ts.add(new Person("zhangsan", 22)); ts.add(new Person("lisi", 27)); ts.add(new Person("wangermazi", 21)); ts.add(new Person("zhaosi", 25)); Iterator it = ts.iterator(); while (it.hasNext()) { Person person = (Person) it.next(); System.out.println(person.toString()); } } }
運行結果:
lisi:27 wangermazi:21 zhangsan:22 zhaosi:25
這次我們的比較器是根據元素屬性name進行排序的,覆寫的compareTo方法是根據age進行排序的。
可以看到,當兩種方法同時存在時,是按照比較器的方法來排序的。
思考:如何通過這種方式實現先進先出和先進後出?
讓比較器直接返回1或-1即可。
三、Iterator介面
對 Collection 進行迭代的迭代器,即對所有的Collection容器進行元素取出的公共介面。
該迭代器對象依賴於具體容器,因為每一個容器的數據結構都不同,所以該迭代器對象是在具體容器中進行內部實現的。(內部類,可以看具體容器的源碼)
對於使用容器者而言,具體的實現方法不重要,只要通過具體容器獲取到該實現的迭代器的對象即可,也就是iterator()方法,而不用new。(Iterator<String> ite=list.iterator();)
小知識點:使用迭代器過程中while和for的區別
1 第一種
2 Iterator<String> ite=list.iterator();
3 while(ite.hasNext())//判斷下一個元素之後有值
4 {
5 System.out.println(ite.next());
6 }
7 第二種
8 Iterator<String> ite=list.iterator();
9 for(Iterator it = coll.iterator(); it.hasNext(); ){
10 System.out.println(it.next());
11 }
第一種方法while迴圈結束後迭代器對象還在記憶體中存在,還能繼續使用迭代器對象。
第二種方法for迴圈結束後迭代器對象就消失了,清理了記憶體,開發中第二種常用。
Iterator的一個子介面
|--ListIterator介面(列表迭代器)
應用場景:
顧名思義,只能用於List的迭代器。
在使用迭代器迭代的過程中需要使用集合中的方法操作元素,出現ConcurrentModificationException異常時,具體看下麵的例子。
出現異常情況代碼:
Iterator it = list.iterator(); while(it.hasNext()){ Object obj = it.next();//java.util.ConcurrentModificationException //在使用迭代器的過程中使用集合中的方法add()操作元素,出現異常。 //可以使用Iterator介面的子介面ListIterator來完成在迭代中對元素進行更多的操作。 if(obj.equals("abc2")){ list.add("abc9"); } else System.out.println("next:"+obj); } System.out.println(list);
解決辦法代碼:
public static void main(String[] args) { List list = new ArrayList(); list.add("abc1"); list.add("abc2"); list.add("abc3"); System.out.println("list:"+list); ListIterator it = list.listIterator();//獲取列表迭代器對象 //它可以實現在迭代過程中完成對元素的增刪改查。 //註意:只有list集合具備該迭代功能. while(it.hasNext()){ Object obj = it.next(); if(obj.equals("abc2")){ it.add("abc9"); //ListIterator提供了add方法 } }
四、Map介面
Map介面與Set類似,可以對照著來學,比如比較器在TreeMap中也適用。
Map: 一次添加一對元素,Collection 一次添加一個元素。
Map也稱為雙列集合,Collection集合也稱為單列集合。
其實map集合中存儲的就是鍵值對,map集合中必須保證鍵的唯一性。
常用方法:
1,添加
value put(key,value):返回前一個和key關聯的值,如果沒有返回null.
2,刪除
void clear():清空map集合。
value remove(key):根據指定的key翻出這個鍵值對。
3,判斷
boolean containsKey(key):是否包含該key
boolean containsValue(value):是否包含該value
boolean isEmpty();是否為空
4,獲取
value get(key):通過鍵獲取值,如果沒有該鍵返回null。當然,可以通過是否返回null,來判斷是否包含指定鍵。
int size(): 獲取鍵值對的個數。
Map常用的子類:(*HashMap與Hashtable的區別,面試常問*,詳見這個博客。)
|--Hashtable :內部結構是哈希表,是同步的。不允許null作為鍵,null作為值。
|--Properties:用來存儲鍵值對型的配置文件的信息,可以和IO技術相結合。
|--HashMap : 內部結構是哈希表,不是同步的。允許null作為鍵,null作為值。
|--TreeMap : 內部結構是二叉樹,不是同步的。可以對Map集合中的鍵進行排序。
Map的迭代方法:
Map本身沒有迭代器。
方法一:利用Map介面的values()方法,返回此映射中包含的值的 Collection
(值不唯一),
然後通過Collecion的迭代器進行迭代。(只需要Value,不需要Key的時候)
public class MapDemo { public static void main(String[] args) { Map<Integer,String> map = new HashMap<Integer,String>(); method_2(map); } public static void method_2(Map<Integer,String> map){ map.put(8,"zhaoliu"); map.put(2,"zhaoliu"); map.put(7,"xiaoqiang"); map.put(6,"wangcai"); Collection<String> values = map.values(); Iterator<String> it2 = values.iterator(); while(it2.hasNext()){ System.out.println(it2.next()); } } }
方法二:通過keySet方法獲取map中所有的鍵所在的Set集合(Key和Set的都具有唯一性),
再通過Set的迭代器獲取到每一個鍵,再對每一個鍵通過Map集合的get方法獲取其對應的值即可。
Set<Integer> keySet = map.keySet(); Iterator<Integer> it = keySet.iterator(); while(it.hasNext()){ Integer key = it.next(); String value = map.get(key); System.out.println(key+":"+value); }
方法三:利用Map的內部介面Map.EntrySet<K,V>使用iterator。
通過Map的entrySet()方法,將鍵和值的映射關係作為對象存儲到Set集合中
這個映射關係的類型就是Map.Entry類型(結婚證)。
再通過Map.Entry對象的getKey和getValue獲取其中的鍵和值。
Set<Map.Entry<Integer, String>> entrySet = map.entrySet(); Iterator<Map.Entry<Integer, String>> it = entrySet.iterator(); while(it.hasNext()){ Map.Entry<Integer, String> me = it.next(); Integer key = me.getKey(); String value = me.getValue(); System.out.println(key+":"+value); }
方法四:通過Map.entrySet<K,V>遍歷key和value(推薦,尤其是容量大時)
for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); }
五、集合框架工具類Collections和Arrays
Collections是集合框架的工具類,裡面的方法都是靜態的。
例1:根據字元串長度的正序和倒序排序。
用到比較器的地方都可以用Collections.reverseOrder()。
static void |
reverse(List<?> list) 反轉指定列表中元素的順序。 |
|
static
|
reverseOrder() 返回一個比較器,它強行逆轉實現了 Comparable 介面的對象 collection 的自然順序。 |
|
static
|
reverseOrder(Comparator<T> cmp) 返回一個比較器,它強行逆轉指定比較器的順序。 |
比較器ComparatorByLength.java:
import java.util.Comparator; public class ComparatorByLength implements Comparator<String> { @Override public int compare(String o1, String o2) { int temp = o1.length() - o2.length(); return temp==0?o1.compareTo(o2): temp; } }
Demo:
public static void demo_3() { // reverse實現原理 /* * TreeSet<String> ts = new TreeSet<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { int temp = o2.compareTo(o1); return temp; } }); */ TreeSet<String> treeset = new TreeSet<String>(new ComparatorByLength()); treeset.add("abc"); treeset.add("hahaha"); treeset.add("zzz"); treeset.add("aa"); treeset.add("cba"); System.out.println(treeset); TreeSet<String> ts = new TreeSet<String>(Collections.reverseOrder(new ComparatorByLength()));//都是靜態方法,直接類名調用 ts.add("abc"); ts.add("hahaha"); ts.add("zzz"); ts.add("aa"); ts.add("cba"); System.out.println("after reverse:\t" + ts); } public static void main(String[] args) { demo_3(); }
[aa, abc, cba, zzz, hahaha]
after reverse: [hahaha, zzz, cba, abc, aa]
運行結果
例2:用工具類Collections.sort()進行排序:
public static void demo_2() { List<String> list = new ArrayList<String>(); list.add("abcde"); list.add("cba"); list.add("aa"); list.add("zzz"); list.add("cba"); list.add("nbaa"); System.out.println(list); Collections.sort(list); System.out.println("after sort:\n" + list); Collections.sort(list, Collections.reverseOrder()); System.out.println("after reverse sort:\n" + list); int index = Collections.binarySearch(list, "cba"); System.out.println("index=" + index); // 獲取最大值。 String max = Collections.max(list, new ComparatorByLength()); System.out.println("maxLength=" + max); } public static void main(String[] args) { demo_2(); }
[abcde, cba, aa, zzz, cba, nbaa] after sort: [aa, abcde, cba, cba, nbaa, zzz] after reverse sort: [zzz, nbaa, cba, cba, abcde, aa] index=2 maxLength=abcde運行結果
例3:給非同步的集合加鎖,方法太多就不一一列舉了,自己查看API。(掌握,面試會問到)
static
|
synchronizedCollection(Collection<T> c) 返回指定 collection 支持的同步(線程安全的)collection。 |
|
static
|
synchronizedList(List<T> list) 返回指定列表支持的同步(線程安全的)列表。 |
|
static
|
synchronizedMap(Map<K,V> m) 返回由指定映射支持的同步(線程安全的)映射。 |
|
static
|
synchronizedSet(Set<T> s) 返回指定 set 支持的同步(線程安全的)set。 |
簡單說一下給集合加鎖的思想。
List list = new ArrayList();// 非同步的list。 list=MyCollections.synList(list);// 返回一個同步的list. class MyCollections{ /** * 返回一個加鎖的List * */ public static List synList(List list){ return new MyList(list); } // 內部類 private class MyList implements List{ private List list; private static final Object lock = new Object(); MyList(List list){ this.list = list; } public boolean add(Object obj){ synchronized(lock) { return list.add(obj); } } public boolean remove(Object obj){ synchronized(lock) { return list.remove(obj); } } } }
例4:將集合轉成數組,Arrays.asList()方法 (掌握)
應用場景:數組方法有限,需要使用集合中的方法操作數組元素時。
註意1:
數組的長度是固定的,所以對於集合的增刪方法(add()和remove())是不能使用的。
Demo:
public static void demo_1() { String[] arr = { "abc", "haha", "xixi" }; List<String> list = Arrays.asList(arr); boolean b1 = list.contains("xixi"); System.out.println("list contains:" + b1); // list.add("hiahia");//引發UnsupportedOperationException System.out.println(list); }運行結果
list contains:true [abc, haha, xixi]
註意2:
如果數組中的元素是對象(包裝器類型),那麼轉成集合時,直接將數組中的元素作為集合中的元素進行集合存儲。(比如上面那個Demo)
如果數組中的元素是基本數據類型,那麼會將該*數組*作為集合中的元素進行存儲。(比如下麵這個Demo)
Demo:
public static void demo_2() { /* * 如果數組中的元素是對象,那麼轉成集合時,直接將數組中的元素作為集合中的元素進行集合存儲。 * * 如果數組中的元素是基本類型數值,那麼會將該數組作為集合中的元素進行存儲。 * */ int[] arr = { 31, 11, 51, 61 }; List<int[]> list = Arrays.asList(arr); System.out.println(list); System.out.println("數組的長度為:" + list.size()); }運行結果
[[I@659e0bfd]
數組的長度為:1
由結果可以看出,當數組中的元素時int類型時,集合中存的元素是整個數組,集合的長度為1而不是4。
例5:將數組轉成集合,List.toArray()方法
Object[] |
toArray()
Returns an array containing all of the elements in this list in proper sequence (from first to last element).
|
<T> T[] |
toArray(T[] a)
Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
|
應用場景:對集合中的元素操作的方法進行限定,不允許對其進行增刪時。
註意:toArray方法需要傳入一個指定類型的數組,數組的長度如何定義呢?
如果定義的數組長度小於集合的size,那麼該方法會創建一個同類型並和集合相同size的數組。
如果定義的數組長度大於集合的size,那麼該方法就會使用指定的數組,存儲集合中的元素,其他位置預設為null。
所以,一般將數組的長度定義為集合的size。
Demo:
public class ToArray { public static void main(String[] args) { List<String> list = new ArrayList<String>(); list.add("abc1"); list.add("abc2"); list.add("abc3"); String[] arr = list.toArray(new String[list.size()]); System.out.println(Arrays.toString(arr)); } }
例6:foreach語句
應用場景:遍曆數組或Collection單列集合。
對數組的遍歷如果僅僅是獲取數組中的元素用foreach可以簡化代碼,如果要對數組的角標進行操作建議使用傳統for迴圈。
格式:
for(類型 變數 :Collection集合|數組)
{}
Demo:
public class ForEachDemo { public static void main(String[] args) { // 遍曆數組 int[] arr = { 3, 1, 5, 7, 4 }; for (int i : arr) { System.out.println(i); } //遍歷List List<String> list = new ArrayList<String>(); list.add("abc1"); list.add("abc2"); list.add("abc3"); for (String s : list) { System.out.println(s); } // 遍歷map // 可以使用高級for遍歷map集合嗎?不能直接用,但是將map轉成單列的set,就可以用了。 Map<Integer, String> map = new HashMap<Integer, String>(); map.put(3, "zhagsan"); map.put(1, "wangyi"); map.put(7, "wagnwu"); map.put(4, "zhagsansan"); for (Integer key : map.keySet()) { String value = map.get(key); System.out.println(key + "::" + value); } for (Map.Entry<Integer, String> me : map.entrySet()) { Integer key = me.getKey(); String value = me.getValue(); System.out.println(key + ":" + value); } // 老式的迭代器寫法 Iterator<String> it = list.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } }