為什么會出現(xiàn)集合類查邢？
我們都知道數(shù)組的弊端是長度固定。這樣一來我擂，數(shù)組就不能滿足變化的要求衬以。所以缓艳，Java就提供了集合供我們使用。
集合特點
- 集合長度是可變的
- 只能存儲對象（在JDK1.5自動裝箱拆箱特性后可以存儲基本數(shù)據(jù)類型）
- 可以存儲多種類型對象（JDK1.5泛型看峻，一般存儲是一種）
集合和數(shù)組的區(qū)別
長度問題：
- 數(shù)組固定
- 集合可變
存儲元素問題：
- 數(shù)組可以是基本數(shù)據(jù)類型阶淘，也可以是引用類型
- 集合在JDK1.5之前只能是引用類型
同一類型問題：
- 數(shù)組中元素類型必須是一樣的
- 集合中元素可以是不一樣的
功能問題：
- 數(shù)組只能對數(shù)據(jù)進行存取操作。
- 集合可以對數(shù)據(jù)進行增刪存取操作互妓。
元素數(shù)量判斷問題：
- 數(shù)組無法判斷其中實際存有多少元素溪窒，length只告訴了數(shù)組的容量；
- 而集合的size()可以確切知道元素的個數(shù) 冯勉。
集合體系的由來
集合是存儲多個元素的容器澈蚌，但是，由于數(shù)據(jù)結(jié)構(gòu)不同灼狰，Java就提供了多種集合類宛瞄。
為什么會出現(xiàn)這么多的容器呢？
因為每種容器對數(shù)據(jù)的存儲方式都有不同交胚，這個存儲方式稱之為：數(shù)據(jù)結(jié)構(gòu)份汗。
數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)存儲的方式。
而這多種集合類有共性的功能蝴簇，所以通過不斷的向上抽取杯活，最終形成集合體系結(jié)構(gòu)（集合框架）。
集合類繼承關(guān)系結(jié)構(gòu)圖
集合類的共性方法
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
}
集合類的迭代器
理解迭代器
什么是迭代器熬词？集合取出元素的方式（動作）旁钧。
由于每個容器的底層數(shù)據(jù)結(jié)構(gòu)都不一樣，它們對數(shù)據(jù)的存儲操作實現(xiàn)也不一樣荡澎。
集合都有取的操作均践，而取的操作不足以用一個方法來描述，比如說取之前判斷是否有元素摩幔，此時就涉及到多個功能彤委。那么此時我們把取出的操作封裝成一個對象。此對象封裝在集合的內(nèi)部作為內(nèi)部類或衡，這樣可以方便直接獲取元素焦影。而每一個容器的數(shù)據(jù)結(jié)構(gòu)不同，所以取出的動作細節(jié)也不一樣封断，但是都有共性內(nèi)容 判斷和取出斯辰，那么可以將寫共性抽取形成一個接口Iterator。
那么這些內(nèi)部類都符合一個規(guī)則坡疼，該規(guī)則是Iterator彬呻。如何獲取集合的取出對象（iterator的子類對象）呢？
通過一個對外提供的方法iterator()。iterator()作用闸氮，獲取容器中的內(nèi)部類對象剪况。
什么是Iterator？
定義了對集合元素操作的接口方法
Iterator主要方法：
public interface Iterator<E> {
boolean hasNext();
E next();
}
迭代器的使用
代碼示例：
public class CollectionDemo {
public static void main(String[] args) {
Collection collection = new ArrayList();
collection.add(1);
collection.add(2);
collection.add(1);
/*
* 迭代器使用方式1
*/
Iterator iterator = collection.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
/*
* 迭代器使用方式2
*/
for(Iterator i = collection.iterator();i.hasNext();){
System.out.println(i.next());
}
/*
* 兩種方式特點：
* 第二種方式 更加節(jié)省內(nèi)存蒲跨。因為iterator對象在for循環(huán)執(zhí)行完后就會被回收译断。
* 第一種 會一直停留在內(nèi)存當中。
*/
}
}
List類
List類共性方法
List：
特有方法或悲。凡是可以操作角標的方法都是該體系特有的方法孙咪。
增
add(index,element);
addAll(index,Collection);
刪
remove(index);
改
set(index,element);
查
get(index):
subList(from,to);
listIterator();
int indexOf(obj):獲取指定元素的位置。
ListIterator listIterator();
ListIterator---列表迭代器
public class ListDemo {
public static void main(String[] args) {
ArrayList al = new ArrayList();
al.add("java01");
al.add("java02");
al.add("java03");
sop(al);
//在迭代過程中巡语，準備添加或者刪除元素
Iterator it = al.iterator();
while(it.hasNext()){
Object obj = it.next();
if(obj.equals("java02")){
al.add("java08");
//it.remove();//將"java02"的引用從集合中刪除了
}
sop(obj);
}
sop(al);
}
public static void sop(Object object){
System.out.println(object);
}
}
以上代碼會產(chǎn)生以下異常：
原因分析：
在迭代時翎蹈，不可以通過集合對象的方法操作集合中的元素
解決方案：
使用List類提供的列表迭代器ListIterator。
引入列表迭代器ListIterator的原因是：
1.避免上方的異常
2.為迭代器添加更多的操作元素的方法捌臊，例如在迭代過程中添加元素杨蛋，修改元素等新功能
總之一句話，ListIterator可以在迭代的過程中理澎，集合中的元素進行增刪改查。
代碼體現(xiàn)：
public class ListIteratorDemo {
public static void main(String[] args) {
ArrayList al = new ArrayList();
al.add("java01");
al.add("java02");
al.add("java03");
sop(al);
ListIterator it = al.listIterator();
while(it.hasNext()){
Object obj = it.next();
if(obj.equals("java02")){
it.add("java08");
}
}
sop(al);
//反向迭代
while(it.hasPrevious()){
Object obj = it.previous();
if(obj.equals("java03")){
sop(obj);
it.set("javaee");
}
}
sop(al);
}
public static void sop(Object object){
System.out.println(object);
}
}
List的子類介紹
List:元素是有序的曙寡，可以重復(fù)糠爬。
- Vector:
- 底層是數(shù)組數(shù)據(jù)結(jié)構(gòu)。
- 線程同步举庶。
- 因為效率低执隧，被ArrayList替代了。
- 它還可以通過枚舉來取出元素户侥。
LinkedList在內(nèi)存中是以鏈表形式組織的镀琉，鏈表中的數(shù)據(jù)在內(nèi)存中是松散的，每一個節(jié)點都有一個指針指向下一個節(jié)點蕊唐，這樣查找起來就比較慢了屋摔。而插入刪除的時候就是斷開一個節(jié)點，然后插入刪除之后再接起來替梨。
ArrayList類
- ArrayList:
- 底層的數(shù)據(jù)結(jié)構(gòu)使用的是動態(tài)數(shù)組結(jié)構(gòu)钓试；
- 特點：查詢速度很快，但是增刪稍慢副瀑；
- 線程不同步弓熏。
可變長度數(shù)組(動態(tài)數(shù)組)其實就是當數(shù)組不夠時，創(chuàng)建一個新的長度更長的數(shù)組糠睡，然后把舊的數(shù)組內(nèi)容復(fù)制到新的數(shù)組中挽鞠。
- 數(shù)組的特點是其中的元素在內(nèi)存中的地址是連續(xù)的，所以ArrayList的優(yōu)點在于get、set的效率高信认，時間復(fù)雜度為常數(shù)串稀。
- ArrayList中插入和刪除效率較低，由于每插入/刪除一項狮杨，都需要移動后續(xù)所有項的位置母截，時間復(fù)雜度為O(N)。
List集合判斷元素是否相同橄教，依據(jù)是元素的equals方法清寇。
contains、indexOf等方法在執(zhí)行其核心邏輯時护蝶，都要對集合中元素進行判斷是否有此元素华烟，判斷的原理都是equals()。
如果不重寫equals方法持灰，則默認比較地址盔夜，這會導(dǎo)致contains將永遠返回false，indexOf堤魁、將永遠返回-1喂链。所以，我們需要重寫equals方法來自己判斷妥泉，例如可以通過比較對象中一個特征字段的值來比較兩個對象是否相等椭微。
LinkedList類
LinkedList特有方法
addFirst();
addLast();
getFirst();
getLast();
獲取元素，但不刪除元素盲链。如果集合中沒有元素蝇率，會出現(xiàn)NoSuchElementException
removeFirst();
removeLast();
獲取元素，但是元素被刪除刽沾。如果集合中沒有元素本慕，會出現(xiàn)NoSuchElementException
在JDK1.6出現(xiàn)了替代方法。
offerFirst();
offerLast();
peekFirst();
peekLast();
獲取元素侧漓，但不刪除元素锅尘。如果集合中沒有元素，會返回null火架。
pollFirst();
pollLast();
獲取元素鉴象，但是元素被刪除。如果集合中沒有元素何鸡，會返回null纺弊。
- LinkedList
- 底層使用的雙向鏈表結(jié)構(gòu)。
- 特點：增刪速度很快骡男，查詢稍慢淆游。
- 線程不同步。
雙向鏈表的特點，元素（結(jié)點）之間的地址不連續(xù)犹菱，通過引用找到當前結(jié)點的上一個結(jié)點和下一個結(jié)點拾稳，即插入和刪除效率較高，只需要常數(shù)時間腊脱，而get和set則較為低效访得，需要O(n)的時間。
LinkedList與ArrayList比較
LinkedList的方法和使用和ArrayList大致相同陕凹，由于LinkedList是鏈表實現(xiàn)的悍抑，所以額外提供了在頭部和尾部添加/刪除元素的方法，并且沒有ArrayList擴容的問題了杜耙。另外搜骡，ArrayList和LinkedList都可以實現(xiàn)棧、隊列等數(shù)據(jù)結(jié)構(gòu)佑女，但LinkedList本身實現(xiàn)了隊列的接口记靡，所以更推薦用LinkedList來實現(xiàn)隊列和棧。
一種數(shù)據(jù)結(jié)構(gòu)可能會基于另一種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)团驱，比如說隊列基于鏈表摸吠。
Vector類
通過以下代碼介紹
/*
枚舉就是Vector特有的取出方式。
發(fā)現(xiàn)枚舉和迭代器很像店茶。
其實枚舉和迭代是一樣的蜕便。
因為枚舉的名稱以及方法的名稱都過長。
所以被迭代器取代了贩幻。
枚舉郁郁而終了。
*/
class VectorDemo
{
public static void main(String[] args)
{
Vector v = new Vector();
v.add("java01");
v.add("java02");
v.add("java03");
v.add("java04");
Enumeration en = v.elements();
while(en.hasMoreElements())
{
System.out.println(en.nextElement());
}
}
}
Vector類與ArrayList類比較
- Vector和ArrayList的底層數(shù)據(jù)結(jié)構(gòu)都是數(shù)組两嘴，在使用上相似丛楚。
- Vector的方法都是同步的(Synchronized),是線程安全的，而ArrayList的方法不是憔辫，由于線程的同步必然要影響性能趣些，因此，ArrayList的性能比Vector好贰您。（建議使用ArrayList坏平，因為高效，就算是多線程可以自己加鎖）
- 當容器空間不足時锦亦，Vector會將它的容量翻倍舶替，而ArrayList只增加50%的大小，這樣杠园，ArrayList就有利于節(jié)約內(nèi)存空間顾瞪。
總結(jié)
在不同的應(yīng)用場景下，選擇合適的集合。比如說在需要頻繁讀取集合中的元素時陈醒，使用ArrayList效率較高惕橙，而在插入和刪除操作較多時，使用LinkedList效率較高钉跷。
Set類
Set體系的類特點：
- 不保證放入元素的順序(存入和取出的順序不一定一致)
- 元素不可以重復(fù)弥鹦。
HashSet類
HashSet底層數(shù)據(jù)結(jié)構(gòu)是哈希表，線程不同步爷辙。
下面是HashSet的構(gòu)造函數(shù)以及主要方法的代碼：
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
private transient HashMap<E,Object> map;
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public int size() {
return map.size();
}
從以上代碼可以知道：
- HashSet基于HashMap實現(xiàn)彬坏，底層使用HashMap保存數(shù)據(jù)。
- 其實HashSet就是操作了HashMap的key犬钢，并且同時具有Set接口的特點苍鲜。
HashSet是如何保證元素唯一性的呢？
是通過兩個方法玷犹，hashCode和equals來完成混滔。
如果元素hashCode值相同，才會判斷equals是否為true歹颓。
如果元素的hashCode不同坯屿，不會調(diào)用equals方法。
注意：對于判斷元素是否存在以及刪除等操作巍扛，依賴的方法是元素的hashCode和equals方法领跛。
/**
* 往HashSet集合中存入自定對象 姓名和年齡相同為同一個人，重復(fù)元素撤奸。
*
*/
public class HashSetDemo {
public static void print(Object obj) {
System.out.println(obj);
}
public static void main(String[] args) {
HashSet<Person> hashSet = new HashSet<>();
hashSet.add(new Person("a1", 11));
hashSet.add(new Person("a2", 12));
hashSet.add(new Person("a3", 13));
hashSet.add(new Person("a2", 12));
// hashSet.add(new Person("a4",14));
// print("a1:"+hashSet.contains(new Person("a2",12)));
// hashSet.remove(new Person("a4",13));
Iterator it = hashSet.iterator();
while (it.hasNext()) {
Person p = (Person) it.next();
print(p.getName() + "::" + p.getAge());
}
}
}
class Person {
private String name;
private int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
public int hashCode() {
System.out.println(this.name + "....hashCode");
return name.hashCode() + age * 37;
}
public boolean equals(Object obj) {
if (!(obj instanceof Person))
return false;
Person p = (Person) obj;
System.out.println(this.name + "...equals.." + p.name);
return this.name.equals(p.name) && this.age == p.age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
LinkedHashSet
LinkedHashSet是HashSet的子類吠昭，它和HashSet的區(qū)別就在于LinkedHashSet的元素嚴格按照放入順序排列。LinkedHashSet內(nèi)部使用LinkedHashMap實現(xiàn)胧瓜，所以它和HashSet的關(guān)系就相當于HashMap和LinkedHashMap的關(guān)系矢棚。如果你想讓取出元素的順序和插入元素的順序完全相同，那么就使用LinkedHashSet代替HashSet府喳。
TreeSet
上面提到HashSet是用HashMap實現(xiàn)的蒲肋，其實這里的TreeSet也是用Map接口的另一個實現(xiàn)類TreeMap實現(xiàn)的。TreeMap是一個有序的二叉樹钝满。TreeSet實現(xiàn)了SortedSet接口兜粘，其特點是會對放入其中的元素進行排序，和LinkedHashSet不同的是弯蚜，LinkedHashSet是根據(jù)元素的放入順序進行排序孔轴，而TreeSet是根據(jù)元素的自然順序進行排序。
保證元素唯一性的依據(jù)：
compareTo方法return 0.
TreeSet排序的第一種方式：讓元素自身具備比較性熟吏。
元素需要實現(xiàn)Comparable接口距糖，覆蓋compareTo方法玄窝。
這種方式也稱為元素的自然順序，或者叫做默認順序悍引。
TreeSet能對Integer和String類型的數(shù)據(jù)進行排序恩脂，是因為Integer和String都實現(xiàn)Comparable接口并實現(xiàn)了compareTo方法。
TreeSet的第二種排序方式趣斤。
當元素自身不具備比較性時俩块，或者具備的比較性不是所需要的。
這時就需要讓集合自身具備比較性浓领。
在集合初始化時玉凯，就有了比較方式。
實際開發(fā)中联贩，TreeSet的使用頻率較低漫仆，是因為TreeSet每插入一個數(shù)據(jù)，就會排一次序泪幌，導(dǎo)致性能降低盲厌，而一般我們都是放入一堆數(shù)據(jù)后再一起排序，所以用不到TreeSet祸泪。但如果剛好碰到需要進行插入后即時排序的需求吗浩，那這時候就可以用上TreeSet了。
總結(jié)
在Set接口的實現(xiàn)類中没隘，HashSet是一種元素不重復(fù)且無序的存儲容器懂扼，可以存儲一個null元素，放入HashSet的對象需要重寫equals和hashCode方法以保證存入對象唯一右蒲；LinkedHashSet是HashSet的子類阀湿，具有HashSet的性質(zhì)，且它保存了元素放入的順序瑰妄；TreeSet可以將存入的元素按照一定的規(guī)則排序炕倘，但是對象和集合其中一個必須要比較性，TreeSet中不能存在null元素翰撑。
