今日任務(wù)
1、List接口介紹（掌握常用List特有方法）
2佣耐、練習(xí)
3政勃、ArrayList介紹（必須清楚集合的特征、掌握集合中的方法）
4兼砖、LinkedList介紹（必須清楚集合的特征奸远、掌握集合中的方法）
5、Vector 類(lèi)介紹(了解)
6讽挟、List下的子類(lèi)總結(jié)(掌握)
7懒叛、Set 接口介紹(掌握Set集合的特性)
8、HashSet 集合(掌握HashSet集合的應(yīng)用)
1耽梅、List接口介紹
在學(xué)習(xí)Collection接口的時(shí)候薛窥，api中告訴我們，在Collection接口的下面有2個(gè)直接的子接口眼姐，分別是Set和List诅迷。我們這里先學(xué)習(xí)List接口。
List接口：
1）是Collection接口的子接口妥凳，繼承了Collection接口中的所有方法竟贯；
2）List接口定義的所有集合中的元素都可以重復(fù)，并且還可以保證存取的順序一致(存儲(chǔ)和取出的順序一致的)逝钥；
3）List接口下的所有集合全部擁有下標(biāo)屑那，List接口更像數(shù)組；
4）由于List接口規(guī)定自己的真實(shí)實(shí)現(xiàn)類(lèi)（集合）都擁有下標(biāo)艘款，因此我們?cè)诓僮鱈ist接口下的所有集合容器的時(shí)候持际，都可以通過(guò)下標(biāo)操作；
5）因此在List接口中它不僅僅繼承到Collection接口中的所有函數(shù)哗咆，同時(shí)java 還根據(jù)List的下標(biāo)的特性蜘欲，定義了適合List接口的特有函數(shù)；
1.1晌柬、List的特有方法
List集合和Collection集合不同之處姥份，就是List接口中的特有方法都是圍繞集合的下標(biāo)而設(shè)計(jì)的郭脂。
List集合中的特有方法：
1）添加方法：
void add(int index,Object element )：根據(jù)指定的角標(biāo)位置，向集合中添加指定的元素對(duì)象澈歉；
index >= 0 && index <= size()展鸡；
boolean addAll(int index, Collection coll)：根據(jù)指定的角標(biāo)位置，向集合中添加指定集合中所有的元素埃难；
index >= 0 && index <= size()莹弊；
分析和步驟：
1）定義一個(gè)ListDemo類(lèi)，在這個(gè)類(lèi)中定義一個(gè)method_1()函數(shù)涡尘；
2）在method_1()函數(shù)中使用new關(guān)鍵字創(chuàng)建ArrayList類(lèi)的對(duì)象list忍弛，并賦值給接口List類(lèi)型；
3）使用集合對(duì)象list調(diào)用屬于Collection接口中的add(E e)函數(shù)向集合List中添加字符串”aaaa”考抄；
4）使用集合對(duì)象list調(diào)用屬于接口List中特有的函數(shù)add(int index,Object element )根據(jù)指定的下標(biāo)向集合中添加數(shù)據(jù)”abc”;
5）使用輸出語(yǔ)句輸出list對(duì)象中的值细疚；
public static void method_1() {
// 創(chuàng)建集合對(duì)象
List list = new ArrayList();
List list1 = new ArrayList();
// 向集合中添加數(shù)據(jù)
list.add("aaaa");
list.add("bbbb");
list.add("cccc");
list1.add("hhhh");
list1.add("哈哈");
// 使用List接口中特有的函數(shù)向接口中添加數(shù)據(jù)
// list.add(1, "dddd");//1表示要添加數(shù)據(jù)的下標(biāo)位置
// list.add(4,"xyz");//指定的下標(biāo)前面一定要有元素
// 向集合list的下標(biāo)為2的位置添加集合list1中所有的數(shù)據(jù)
list.addAll(2, list1);
// 輸出數(shù)據(jù)
System.out.println(list);
}
注意：
1）指定的下標(biāo)前面一定要有數(shù)據(jù)；
2）添加不是覆蓋座泳，指定的位置添加了元素后惠昔，之前存在元素就會(huì)向后移動(dòng)；
2）獲取方法：
List subList(int startIndex, int endIndex)： 返回集合中從指定角標(biāo)開(kāi)始(包含頭角標(biāo))到指定角標(biāo)結(jié)束(不包含尾角標(biāo))的所有元素挑势，以集合方式返回
int indexOf(Object obj)返回指定元素在集合中第一次出現(xiàn)的角標(biāo)镇防。沒(méi)有匹配元素則返回-1
分析和步驟：
1）在上述ListDemo類(lèi)中定義一個(gè)method_2()函數(shù)；
2）在method_2()函數(shù)中使用new關(guān)鍵字創(chuàng)建ArrayList類(lèi)的對(duì)象list潮饱，并賦值給接口List類(lèi)型来氧；
3）使用集合對(duì)象list調(diào)用屬于Collection接口中的add(E e)函數(shù)向集合List中添加幾個(gè)字符串?dāng)?shù)據(jù)；
4） 使用集合對(duì)象list調(diào)用屬于接口List中特有的函數(shù)get(int index )根據(jù)指定的下標(biāo)獲取下標(biāo)對(duì)應(yīng)的數(shù)據(jù)香拉；
5）使用輸出語(yǔ)句輸出獲得的數(shù)據(jù)obj啦扬；
public static void method_2() {
// 創(chuàng)建集合對(duì)象
List list = new ArrayList();
// 向集合中添加數(shù)據(jù)
list.add("nba");
list.add("nba");
list.add("cba");
list.add("wbna");
list.add("wcba");
// 根據(jù)下標(biāo)獲得對(duì)應(yīng)的元素
// Object obj = list.get(2);
// Object obj = list.get(7);//下標(biāo)不能是空白區(qū)域
// System.out.println(obj);
// List subList = list.subList(1,0);//結(jié)束角標(biāo)要大于等于起始角標(biāo)
// System.out.println(subList);
// 返回指定元素第一次出現(xiàn)的角標(biāo)
int index = list.indexOf("nbaa");// 沒(méi)有返回-1
System.out.println(index);
}
注意： 下標(biāo)的范圍：index >= 0 && index <= size()-1；
1.2凫碌、List的特有迭代器
List接口繼承了Collection接口扑毡，Collection接口中的獲取某個(gè)集合對(duì)應(yīng)的迭代器的函數(shù)，List一定也繼承到了盛险。但是由于List集合有下標(biāo)瞄摊，因此Java中針對(duì)List這類(lèi)集合同時(shí)也提供了自己特有的迭代器。
ListIterator接口：
ListIterator接口：它是專(zhuān)門(mén)針對(duì)List接口而設(shè)計(jì)的苦掘，這個(gè)迭代器在遍歷List集合的時(shí)候换帜，可以對(duì)這個(gè)集合中的元素進(jìn)行增 刪 改 查操作。并且它還可以逆向遍歷鹤啡。
注意：ListIterator迭代器只能被List集合使用惯驼，其它集合都不能使用。
使用ListIterator逆向迭代的時(shí)候一定要使用帶有參數(shù)的listIterator(index)函數(shù)，然后集合的長(zhǎng)度作為參數(shù)下標(biāo)祟牲，否則該迭代光標(biāo)就會(huì)從前往后迭代隙畜；
這里的index>=0&&index<=list.size();
使用list.size()作為參數(shù)。
分析和步驟：
1）定義一個(gè)ListIteratorDemo類(lèi)说贝；
2）在這個(gè)類(lèi)中使用new關(guān)鍵字創(chuàng)建ArrayList類(lèi)的對(duì)象list禾蚕，并賦值給接口List類(lèi)型；
3）使用集合對(duì)象list調(diào)用屬于Collection接口中的add(E e)函數(shù)向集合List中添加幾個(gè)字符串?dāng)?shù)據(jù)狂丝；
4）使用集合對(duì)象list調(diào)用屬于接口Collection中的iterator()函數(shù)獲得迭代器對(duì)象it,并在for循環(huán)中使用迭代器對(duì)象it調(diào)用hasNext()函數(shù)判斷是否有元素，使用迭代器對(duì)象it調(diào)用next()函數(shù)獲取list集合中的數(shù)據(jù)哗总，并打蛹秆铡；
5）使用集合對(duì)象list調(diào)用listIterator()函數(shù)生成ListIterator 類(lèi)型讯屈，并使用for循環(huán)對(duì)其迭代遍歷蛋哭；
6）同樣使用ListIterator 類(lèi)型的對(duì)象調(diào)用listIterator(list.size())函數(shù)，這里需要注意涮母，由于是從集合中的最后元素開(kāi)始向前遍歷谆趾，所以這里我們對(duì)于listIterator()函數(shù)應(yīng)該給一個(gè)參數(shù)，否則不會(huì)出現(xiàn)結(jié)果叛本；
7）lit.hasPrevious()判斷是否有元素沪蓬，如果有前一個(gè)元素可以迭代，則返回 true 来候，lit.previous()返回列表中的前一個(gè)元素跷叉；
package cn.xuexi.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/*
* List接口的特有的迭代器
*/
public class ListIteratorDemo {
public static void main(String[] args) {
//創(chuàng)建集合對(duì)象
List list=new ArrayList();
//向集合中添加數(shù)據(jù)
list.add("nba");
list.add("aaa");
list.add("cba");
list.add("wnba");
list.add("wcba");
//使用Collection接口中的Iterator進(jìn)行迭代
System.out.println("使用Iterator進(jìn)行迭代");
for (Iterator it = list.iterator(); it.hasNext();) {
//輸出數(shù)據(jù)
System.out.println(it.next());
}
//使用List接口中的特有迭代器ListIterator進(jìn)行迭代
System.out.println("使用ListIterator進(jìn)行正向迭代");
for (ListIterator it = list.listIterator();it.hasNext();) {
System.out.println(it.next());
}
System.out.println("使用ListIterator進(jìn)行逆向迭代");
//it.hasPrevious()如果為true表示集合中從后往前迭代開(kāi)始有元素
for (ListIterator it = list.listIterator(list.size()); it.hasPrevious();) {
//it.previous()表示返回集合中的上一個(gè)元素
System.out.println(it.previous());
}
}
}
注意：
1）使用ListIterator逆向迭代的時(shí)候一定要使用帶有參數(shù)的listIterator(index)函數(shù)，然后集合的長(zhǎng)度作為參數(shù)下標(biāo)营搅，否則該迭代光標(biāo)就會(huì)從前往后迭代云挟；
這里的index>=0&&index<=list.size();
2）這里為何使用list.size()作為參數(shù)而不是list.size()-1，因?yàn)槲覀円獜募现凶詈笠粋€(gè)元素后面開(kāi)始迭代转质，如果是list.size()-1园欣，迭代光標(biāo)會(huì)從最后一個(gè)元素前面開(kāi)始，這樣會(huì)導(dǎo)致忽略了集合中的最后一個(gè)元素休蟹；
擴(kuò)展：演示在使用ListIterator迭代器遍歷List集合的時(shí)候沸枯，可以對(duì)這個(gè)集合中的元素進(jìn)行修改操作，代碼如下：
案例：List集合的特有迭代器對(duì)象鸡挠。
在使用ListIterator迭代器遍歷集合的時(shí)候是可以修改集合的辉饱；
需求：迭代取出集合中的元素的時(shí)候，判斷是否等于某個(gè)數(shù)據(jù)拣展，如果相等使用迭代器對(duì)象調(diào)用迭代器中的add()函數(shù)向集合中添加一個(gè)新的數(shù)據(jù)或者使用迭代器中的set函數(shù)更改數(shù)據(jù)彭沼。
分析和步驟：
1）在這個(gè)類(lèi)中使用new關(guān)鍵字創(chuàng)建ArrayList類(lèi)的對(duì)象list，并賦值給接口List類(lèi)型备埃；
2）使用集合對(duì)象list調(diào)用屬于Collection接口中的add(E e)函數(shù)向集合List中添加幾個(gè)字符串?dāng)?shù)據(jù)姓惑；
3）使用集合對(duì)象list調(diào)用listIterator()函數(shù)生成ListIterator 類(lèi)型的迭代器對(duì)象褐奴；
4）使用while循環(huán)遍歷集合，將獲得的數(shù)據(jù)強(qiáng)制轉(zhuǎn)換為String類(lèi)型于毙；
5）使用判斷結(jié)構(gòu)判斷找到的對(duì)象數(shù)據(jù)是否是集合中的一個(gè)數(shù)據(jù)敦冬，如果是，則使用迭代器對(duì)象調(diào)用add()函數(shù)向集合中添加一個(gè)新的字符串?dāng)?shù)據(jù)唯沮；
6）循環(huán)結(jié)束輸出集合脖旱；
補(bǔ)充：注意，使用Iterator迭代器遍歷集合的時(shí)候介蛉，在Iterator接口中只提供了remove()函數(shù)進(jìn)行修改集合萌庆；
總結(jié)：（很重要，經(jīng)常犯錯(cuò)誤）
我們?cè)诘蠒r(shí)币旧，如果要對(duì)集合修改践险，一定要使用迭代器本身的功能！一定不能使用集合對(duì)象調(diào)用集合中的函數(shù)去修改集合吹菱。
Iterator中只提供了一個(gè)：remove功能
ListIterator中提供了：add巍虫、remove、set功能
1.3鳍刷、List集合遍歷方法總結(jié)
說(shuō)明：
迭代List集合有多種寫(xiě)法占遥，有五種寫(xiě)法：
1）toArray(); Object[] arr = list.toArray();
2）使用for循環(huán)借助Iterator接口可以實(shí)現(xiàn)；
3）使用for循環(huán)借助ListIterator接口可以實(shí)現(xiàn)倾剿；
4）使用普通for循環(huán)
for( int i=0;i<list.size();i++ ){
System.out.println(list.get(i));
}
5）使用foreach循環(huán)：
for( Object obj : list )
{
System.out.println(obj);
}
package cn.xuexi.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/*
* 迭代集合的五種方法：
* 1.toArray()
* 2.使用Iterator迭代器遍歷集合
* 3.使用ListIterator迭代器遍歷集合
* 4.使用普通for循環(huán)遍歷集合
* 5.使用foreach循環(huán)遍歷集合
*/
public class ListIteratorDemo2 {
public static void main(String[] args) {
//創(chuàng)建集合對(duì)象
List list=new ArrayList();
//向集合添加數(shù)據(jù)
list.add("及時(shí)雨");
list.add("白麒麟");
list.add("黑旋風(fēng)");
list.add("母老虎");
//使用toArray()函數(shù)遍歷集合
System.out.println("使用toArray()函數(shù)遍歷集合");
Object[] arr = list.toArray();
//遍歷數(shù)組
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
System.out.println("使用Iterator迭代器遍歷集合");
//使用Iterator迭代器遍歷集合
for (Iterator it = list.iterator(); it.hasNext();) {
System.out.println(it.next());
}
System.out.println("使用ListIterator迭代器遍歷集合");
//使用ListIterator迭代器遍歷集合
for (ListIterator it = list.listIterator(); it.hasNext();) {
System.out.println(it.next());
}
System.out.println("使用普通for循環(huán)遍歷集合");
//使用普通for循環(huán)遍歷集合
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("使用foreach循環(huán)遍歷集合");
//使用foreach循環(huán)遍歷集合
for (Object obj : list) {
System.out.println(obj);
}
}
}
2筷频、練習(xí)
需求：使用List存儲(chǔ)字符串，并去除重復(fù)元素前痘，要求在同一個(gè)集合中去除凛捏。
假如有一個(gè)集合，里面有一些重復(fù)的字符串芹缔。把重復(fù)給我去除坯癣。
分析和步驟：
思路：
1）：創(chuàng)建一個(gè)空的集合l2
2）：循環(huán)遍歷l1，取出每個(gè)字符串
3）：判斷取出的元素在l2中是否存在
是：存在最欠，舍棄
否：不存在示罗，添加到l2
4）：清空L1
5）：把L2的元素添加到L1
注意：這里使用for循環(huán)遍歷迭代的是l1集合，不是l2集合芝硬。
/**
* 需求：去除集合中的重復(fù)元素蚜点。
*/
public class CollectionTest {
public static void main(String[] args) {
List l1= new ArrayList();
l1.add("aaaa");
l1.add("abc");
l1.add("abc");
l1.add("bbbb");
l1.add("aaaa");
l1.add("xyz");
l1.add("xyz");
l1.add("aaaa");
//新建一個(gè)新的集合容器
List l2 = new ArrayList();
for (Iterator it = l1.iterator(); it.hasNext();) {
Object obj = it.next();
//判斷從原始集合中取出的元素在新的集合中是否存在
if( !l2.contains(obj) ){
l2.add(obj);
}
}
//循環(huán)結(jié)束之后，l2集合中一定保存的都是不重復(fù)的元素
//把原始集合中的數(shù)據(jù)清空拌阴，把l2中的不重復(fù)元素添加到原始集合中
l1.clear();
l1.addAll(l2);
System.out.println(l1);
}
}
3绍绘、LinkedList介紹(掌握)
3.1 概述
List集合
|------ArrayList集合
|------LinkedList集合
LinkedList集合：它也是List接口的實(shí)現(xiàn)類(lèi)，它的底層使用的鏈接列表（鏈表）數(shù)據(jù)結(jié)構(gòu)。
鏈表結(jié)構(gòu)的特點(diǎn)：有頭有尾陪拘。
補(bǔ)充概念：什么是數(shù)據(jù)結(jié)構(gòu)厂镇？
數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)方式，不同的集合容器它們存儲(chǔ)數(shù)據(jù)的方式都不一樣左刽。而我們學(xué)習(xí)眾多的集合容器捺信，重點(diǎn)是知道每個(gè)集合存儲(chǔ)數(shù)據(jù)的方式即可。不同集合的存儲(chǔ)方式不同欠痴，導(dǎo)致集合中的數(shù)據(jù)存取迄靠，以及元素能否重復(fù)等相關(guān)操作也都不相同。
LinkedList集合它采用的是數(shù)據(jù)結(jié)構(gòu)中的鏈表結(jié)構(gòu)：
鏈表結(jié)構(gòu)：由一個(gè)鏈子把多個(gè)節(jié)點(diǎn)連接起來(lái)的數(shù)據(jù)結(jié)構(gòu)喇辽。
節(jié)點(diǎn)：在鏈表結(jié)構(gòu)中每個(gè)可以保存數(shù)據(jù)的空間稱(chēng)為節(jié)點(diǎn)梨水，而一個(gè)鏈表結(jié)構(gòu)是由多個(gè)節(jié)點(diǎn)組成的。
也就是說(shuō)鏈表結(jié)構(gòu)使用節(jié)點(diǎn)來(lái)存儲(chǔ)數(shù)據(jù)茵臭。
每個(gè)節(jié)點(diǎn)(存儲(chǔ)數(shù)據(jù)的空間)可以分成若干部分，其中有一部分存儲(chǔ)數(shù)據(jù)舅世，另外一部分存儲(chǔ)的是其他節(jié)點(diǎn)的地址旦委。
說(shuō)明：
1）節(jié)點(diǎn)：實(shí)際存儲(chǔ)自己的數(shù)據(jù)+其他節(jié)點(diǎn)的地址，而作為鏈表結(jié)構(gòu)中的最后一個(gè)節(jié)點(diǎn)的存儲(chǔ)地址的空間是null雏亚。
2）鏈表結(jié)構(gòu)查詢(xún)或遍歷時(shí)都是從頭到尾的遍歷缨硝。
3）鏈表結(jié)構(gòu)是有頭有尾的。因此LinkedList集合中定義了自己的特有的方法都是圍繞鏈表的頭和尾設(shè)計(jì)的罢低。
4）鏈表分為兩種：?jiǎn)蜗蜴湵砗碗p向鏈表查辩。
如下圖所示就是數(shù)組結(jié)構(gòu)和鏈表結(jié)構(gòu)對(duì)數(shù)據(jù)的查詢(xún)、添加网持、刪除的區(qū)別對(duì)比圖如下所示：
總結(jié)：
1）數(shù)組結(jié)構(gòu)查詢(xún)快宜岛，但是增刪慢；
2）鏈表結(jié)構(gòu)查詢(xún)慢功舀，但是增刪快萍倡；
上述兩種數(shù)據(jù)結(jié)構(gòu)快慢只是相對(duì)來(lái)說(shuō)。
LinkedList集合特點(diǎn)：
1辟汰、它的底層使用的鏈表結(jié)構(gòu)列敲；
2、有頭有尾帖汞，其中的方法都是圍繞頭和尾設(shè)計(jì)的戴而；
3、LinkedList集合可以根據(jù)頭尾進(jìn)行各種操作翩蘸，但它的增刪效率高所意，查詢(xún)效率低；
LinkedList集合增刪效率高是因?yàn)榈讓邮擎湵斫Y(jié)構(gòu)，如果增加或者刪除只需要在增加或者刪除節(jié)點(diǎn)的位置上記住新的節(jié)點(diǎn)的地址即可扁眯，而其他節(jié)點(diǎn)不需要移動(dòng)壮莹，所以速度會(huì)快。
而查詢(xún)遍歷由于鏈表結(jié)構(gòu)的特點(diǎn)姻檀，查詢(xún)只能從頭一直遍歷到鏈表的結(jié)尾命满，所以速度會(huì)慢。
4绣版、LinkedList集合底層也是線程不安全胶台。效率高；
5杂抽、也可以存儲(chǔ)null元素诈唬；
3.2 LinkedList集合的特有方法
說(shuō)明：
這里只有兩個(gè)構(gòu)造函數(shù)，不像ArrayList集合有三個(gè)構(gòu)造函數(shù)缩麸，而這里不需要給容器初始化容量大小铸磅，因?yàn)長(zhǎng)inkedList集合的特點(diǎn)就是鏈表結(jié)構(gòu)，在底層如果新增加一個(gè)元素那么前一個(gè)節(jié)點(diǎn)記住新增加的節(jié)點(diǎn)地址杭朱，而新增加的節(jié)點(diǎn)記住后一個(gè)節(jié)點(diǎn)地址就可以阅仔，什么時(shí)候增加什么記住地址即可，不需要初始化容量大小弧械。
由于LinkedList是鏈表結(jié)構(gòu)八酒，而鏈表有頭有尾，所以在LinkedList集合中專(zhuān)門(mén)為鏈表結(jié)構(gòu)提供了特有的函數(shù)刃唐。
練習(xí)：需求練習(xí)LinkedList集合中特有的函數(shù)羞迷。
分析和步驟：
1）使用new關(guān)鍵字創(chuàng)建LinkedList類(lèi)的對(duì)象list，并賦值為L(zhǎng)inkedList類(lèi)型画饥；
2）使用對(duì)象list調(diào)用LinkedList集合中的addFirst()函數(shù)向集合中添加字符串衔瓮；
3）利用for循環(huán)和迭代器迭代遍歷LinkedList集合；
4）使用對(duì)象list調(diào)用LinkedList類(lèi)中的getLast()函數(shù)獲取最后一個(gè)元素并輸出抖甘；
5）使用對(duì)象list調(diào)用LinkedList類(lèi)中的removeFirst()函數(shù)刪除第一個(gè)元素并輸出报辱；
3.3 隊(duì)列和堆棧結(jié)構(gòu)(面試題)
由于LinkedList集合底層使用的鏈表結(jié)構(gòu)：導(dǎo)致LinkedList集合在存儲(chǔ)數(shù)據(jù)的時(shí)候可以根據(jù)頭和尾進(jìn)行增、刪单山、改碍现、查各種操作∶准椋可以使用LinkedList集合模擬常見(jiàn)的2種數(shù)據(jù)結(jié)構(gòu)：
隊(duì)列結(jié)構(gòu)：先進(jìn)的先出或者后進(jìn)的后出昼接。（排隊(duì)買(mǎi)票）
堆棧結(jié)構(gòu)：先進(jìn)的后出或者后進(jìn)的先出。（手槍的彈夾）
經(jīng)常使用LinkedList模擬上述的2種結(jié)構(gòu)：
1）案例：使用LinkedList模擬隊(duì)列結(jié)構(gòu) 悴晰。先進(jìn)的先出 （排隊(duì)買(mǎi)票）
注意：隊(duì)列的特點(diǎn)是獲取一個(gè)元素便同時(shí)將獲取的元素直接刪除慢睡；
可以理解為一個(gè)人買(mǎi)票逐工，買(mǎi)完票就不在隊(duì)伍中了；
由于隊(duì)列的特點(diǎn)漂辐，是先進(jìn)先出泪喊，所以這里可以刪除第一個(gè)元素，并返回刪除的元素髓涯；
分析和步驟：
1）新建一個(gè)模擬隊(duì)列的類(lèi)QueueDemo袒啼；
2）在這個(gè)類(lèi)Queue中創(chuàng)建LinkedList類(lèi)的集合對(duì)象list；
3）定義一個(gè)添加元素的函數(shù)addElement(Object obj),在函數(shù)體里面使用集合對(duì)象list調(diào)用LinkedList類(lèi)的集合中的addLast(obj)函數(shù)纬纪，將元素添加尾部蚓再；
4）定義一個(gè)獲取元素的函數(shù)getElement(),返回值是Object，由于元素獲取之后就要從集合中刪除包各，所以在函數(shù)體里面使用集合對(duì)象list調(diào)用LinkedList類(lèi)的集合中的removeFirst()函數(shù)摘仅，移除頭部元素并返回刪除的元素；
5）定義一個(gè)判斷隊(duì)列中是否還有元素存在的函數(shù)isNull()问畅，函數(shù)返回值是boolean,在函數(shù)體里面使用集合對(duì)象list調(diào)用LinkedList類(lèi)的集合中的isEmpty()函數(shù)娃属，不包含元素返回true，包含返回false护姆；
6）定義一個(gè)測(cè)試類(lèi)LinkedListDemo1,在這個(gè)類(lèi)中使用new關(guān)鍵字創(chuàng)建剛才創(chuàng)建好的Queue類(lèi)的對(duì)象q膳犹；
7）使用對(duì)象q調(diào)用addElement()函數(shù)向集合中添加數(shù)據(jù)；
8）使用while循環(huán)依次取出集合中的數(shù)據(jù)签则，對(duì)象q調(diào)用isNull()函數(shù)判斷是否還有元素，對(duì)象q調(diào)用getElement()铐料，獲得元素輸出并打咏チ选；
package cn.xuexi.list.test;
import java.util.LinkedList;
/*
* 模擬隊(duì)列結(jié)構(gòu) 特點(diǎn)：先進(jìn)先出钠惩，類(lèi)似買(mǎi)票
*/
//創(chuàng)建模擬隊(duì)列的類(lèi)
class QueueDemo
{
//創(chuàng)建LinkedList集合對(duì)象
LinkedList list=new LinkedList();
//定義函數(shù)模擬向隊(duì)列中添加元素
public void addElement(Object obj)
{
//每次都向集合最后面添加數(shù)據(jù) 添加到鏈表的尾部
list.addLast(obj);
}
//定義函數(shù)柒凉，讓外界獲取元素
public Object getElement()
{
/*
* 由于隊(duì)列的特點(diǎn)是獲取一個(gè)元素便同時(shí)將獲取的元素直接刪除
* 可以理解為一個(gè)人買(mǎi)票，買(mǎi)完票就不在隊(duì)伍中了
* 由于隊(duì)列的特點(diǎn)篓跛，是先進(jìn)先出膝捞，所以這里可以刪除第一個(gè)元素，并返回刪除的元素
*/
return list.removeFirst();
}
//判斷隊(duì)列中是否還有元素存在
public boolean isNull()
{
/*
* 在LinkedList函數(shù)中雖然沒(méi)有判斷集合中是否還含有數(shù)據(jù)
* 但是它的接口List中含有愧沟，所以我們可以使用list.isEmpty()來(lái)判斷集合中是否還含有數(shù)據(jù)
* isEmpty()函數(shù)是判斷集合中沒(méi)有元素返回true蔬咬，有元素返回false
*/
return list.isEmpty();
}
}
public class LinkedListQueue {
public static void main(String[] args) {
//創(chuàng)建模擬隊(duì)列類(lèi)的對(duì)象
QueueDemo q=new QueueDemo();
//向隊(duì)列中添加數(shù)據(jù)
q.addElement("元素1");
q.addElement("元素2");
q.addElement("元素3");
//判斷集合中是否還含有元素，有沐寺，則輸出數(shù)據(jù)
while(!q.isNull())//!q.isNull()如果為true林艘，表示集合中還有數(shù)據(jù)
{
//說(shuō)明集合中還有元素，取出數(shù)據(jù) 輸出元素結(jié)果 "元素1" "元素2" "元素3"
System.out.println(q.getElement());
}
}
}
2）案例：使用LinkedList模擬堆棧結(jié)構(gòu)混坞。先進(jìn)的后出狐援，（手槍的彈夾）
代碼和上述相同钢坦，只是將QueueDemo類(lèi)中的getElement()函數(shù)體中的代碼改成
return list.removeLast()即可
removeLast()表示移除尾部元素并返回刪除的元素。
package cn.xuexi.list.test;
import java.util.LinkedList;
/*
* 模擬堆棧結(jié)構(gòu) 特點(diǎn)：先進(jìn)后出啥酱，類(lèi)似子彈彈夾
*/
//創(chuàng)建模擬堆棧的類(lèi)
class QueueDemo
{
//創(chuàng)建LinkedList集合對(duì)象
LinkedList list=new LinkedList();
//定義函數(shù)模擬向堆棧中添加元素
public void addElement(Object obj)
{
//每次都向集合最后面添加數(shù)據(jù) 添加到鏈表的尾部
list.addLast(obj);
}
//定義函數(shù)爹凹，讓外界獲取元素
public Object getElement()
{
/*
* 由于堆棧的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是先進(jìn)后出，
* 所以我們可以將最后添加的數(shù)據(jù)先移除
*/
return list.removeLast();
}
//判斷堆棧中是否還有元素存在
public boolean isNull()
{
/*
* 在LinkedList函數(shù)中雖然沒(méi)有判斷集合中是否還含有數(shù)據(jù)
* 但是它的接口List中含有镶殷，所以我們可以使用list.isEmpty()來(lái)判斷集合中是否還含有數(shù)據(jù)
* isEmpty()函數(shù)是判斷集合中沒(méi)有元素返回true禾酱，有元素返回false
*/
return list.isEmpty();
}
}
public class LinkedListQueue {
public static void main(String[] args) {
//創(chuàng)建模擬堆棧類(lèi)的對(duì)象
QueueDemo q=new QueueDemo();
//向堆棧中添加數(shù)據(jù)
q.addElement("元素1");
q.addElement("元素2");
q.addElement("元素3");
//判斷集合中是否還含有元素，有批钠，則輸出數(shù)據(jù)
while(!q.isNull())//!q.isNull()如果為true宇植，表示集合中還有數(shù)據(jù)
{
//說(shuō)明集合中還有元素，取出數(shù)據(jù) 輸出元素結(jié)果 "元素3" "元素2" "元素1"
System.out.println(q.getElement());
}
}
}
4埋心、Vector介紹(了解)
Vector集合是JDK1.0的時(shí)候出現(xiàn)的集合指郁，它在jdk1.2的時(shí)候被收編到List接口的下面。而這個(gè)集合被JDK1.2中的ArrayList集合代替拷呆。
演示Vector類(lèi)的函數(shù)：
分析和步驟：
1）定義一個(gè)測(cè)試類(lèi)VectorDemo闲坎，并創(chuàng)建這個(gè)類(lèi)的對(duì)象v；
2）使用對(duì)象v調(diào)用Vector類(lèi)中的addElement()函數(shù)向Vector集合中添加字符串?dāng)?shù)據(jù)茬斧；
3）使用集合對(duì)象v調(diào)用iterator()函數(shù)獲得迭代器的對(duì)象it腰懂；
4）使用循環(huán)借助迭代器對(duì)象調(diào)用hasNext()函數(shù)和next()函數(shù)遍歷集合，并輸出项秉，可是iterator()不是Vector集合原來(lái)就開(kāi)始使用的迭代方式绣溜；
5）使用對(duì)象v調(diào)用Vector類(lèi)中的elements()函數(shù)來(lái)獲得類(lèi)似迭代器的對(duì)象en，并給Enumeration類(lèi)型娄蔼；
6）同樣使用en對(duì)象調(diào)用Enumeration中的hasMoreElements()和nextElement()函數(shù)借助集合進(jìn)行遍歷怖喻，而這種方式是最開(kāi)始誕生Vector類(lèi)使用迭代的方式；
問(wèn)題：
通過(guò)查閱API得知岁诉，Vector集合從jdk1.0版本就已經(jīng)存在了锚沸，而迭代器Iterator是從jdk1.2版本開(kāi)始才引入的，那么在jdk1.2版本之前是怎么對(duì)Vector集合進(jìn)行迭代和遍歷取出集合中的數(shù)據(jù)呢涕癣？
解釋說(shuō)明：
1）在1.2版本之前我們借助于另一個(gè)接口Enumeration來(lái)實(shí)現(xiàn)迭代的哗蜈；
2）使用接口Enumeration對(duì)集合進(jìn)行迭代，可以先使用Vector集合的對(duì)象調(diào)用Vector集合中的elements()函數(shù)來(lái)獲得接口Enumeration的對(duì)象坠韩；
3）然后使用接口Enumeration的對(duì)象調(diào)用hasMoreElements()判斷集合中是否還有元素距潘，有返回true；
4）然后使用接口Enumeration的對(duì)象調(diào)用nextElement()函數(shù)獲取集合中的元素只搁；
package cn.xuexi.vector;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.Vector;
/*
* Vector集合的演示
*/
public class VectorDemo {
public static void main(String[] args) {
//創(chuàng)建Vector集合對(duì)象
Vector v=new Vector();
//向Vector集合中添加數(shù)據(jù)
v.addElement("黑旋風(fēng)");
v.addElement("劉德華");
v.addElement("成龍");
v.addElement("李連杰");
//遍歷集合
/*for (Iterator it = v.iterator(); it.hasNext();)
{
//獲取集合里面的數(shù)據(jù)
System.out.println(it.next());
}*/
//使用jdk1.2版本之前對(duì)Vector集合進(jìn)行遍歷
for (Enumeration en = v.elements(); en.hasMoreElements();) {
//輸出集合中的數(shù)據(jù)
System.out.println(en.nextElement());
}
}
}
Vector集合它就是ArrayList集合绽昼，可以使用Enumeration迭代Vector集合，但是由于Enumeration迭代器中的方法的名字太長(zhǎng)须蜗，被Iterator代替硅确。后期如果需要迭代器Vector應(yīng)該優(yōu)先考慮使用Iterator迭代目溉。
Vector集合的特點(diǎn)：
1）Vector是jdk1.0出現(xiàn)的集合，它的增刪菱农，查詢(xún)效率都比較低缭付；
2）由于Vector底層是線程安全的。ArrayList 的底層是不安全的循未，因此ArrayList各方面的效率都比Vector高陷猫。
3）對(duì)于Vector類(lèi)現(xiàn)在開(kāi)發(fā)中已經(jīng)幾乎不再使用。根本就不用的妖。
5绣檬、List下的子類(lèi)總結(jié)(掌握)
Collection集合（接口）
|----List集合（接口）：可以存儲(chǔ)重復(fù)元素、可以存儲(chǔ)null嫂粟、有角標(biāo)娇未、存取有序。
|----ArrayList集合（類(lèi)）：實(shí)現(xiàn)List接口星虹。ArrayList集合中的特有方法是實(shí)現(xiàn)List
底層使用可變數(shù)組結(jié)構(gòu)零抬。
查詢(xún)遍歷的效率比較高、增刪的效率比較低
屬于線程不安全的集合類(lèi)宽涌。執(zhí)行效率比較高
|----LinkedList集合（類(lèi)）：實(shí)現(xiàn)List接口平夜。
底層使用鏈表結(jié)構(gòu)。（鏈表：有頭有尾）
LinkedList集合中的特有方法都是圍繞鏈表的頭尾設(shè)計(jì)
查詢(xún)遍歷的效率比較慢卸亮、增刪的效率比較高
屬于線程不安全的集合類(lèi)忽妒。執(zhí)行效率比較高
|----Vector集合（類(lèi)）：實(shí)現(xiàn)List接口。線程安全的集合類(lèi)。
底層使用可變數(shù)組結(jié)構(gòu)。查詢(xún)遍歷效率、增刪效率都比較低。
Vector類(lèi)屬于線程安全的集合類(lèi)妻熊。效率比較慢。現(xiàn)在開(kāi)發(fā)中已經(jīng)不再使用躏将。
問(wèn)題：遇到對(duì)線程有需求的情況陌知，應(yīng)該使用哪個(gè)集合類(lèi)？
還使用LinkedList颜及、ArrayList（在后面學(xué)習(xí)過(guò)程中甩苛，可以解決LinkedList\ ArrayList線程不安全的問(wèn)題）
疑問(wèn)：
1）解釋?zhuān)簽槭裁碅rrayList集合增刪效率低，而查詢(xún)速度快俏站？
因?yàn)槲覀兿蚣现刑砑釉氐臅r(shí)候讯蒲，有時(shí)會(huì)將元素添加到集合中的最前面，或者有可能刪除最前面的數(shù)據(jù)肄扎，這樣就導(dǎo)致其他數(shù)據(jù)向后移動(dòng)或者刪除時(shí)向前移動(dòng)墨林，所以效率會(huì)低赁酝。
對(duì)于查詢(xún)ArrayList集合，由于ArrayList集合是數(shù)組結(jié)構(gòu)旭等，而數(shù)組結(jié)構(gòu)是排列有序的酌呆，并且下標(biāo)是有序增加的，當(dāng)查詢(xún)ArrayList集合的時(shí)候可以按照排列順序去查詢(xún)搔耕，或者直接可以通過(guò)某個(gè)下標(biāo)去查詢(xún)隙袁，這樣就會(huì)導(dǎo)致查詢(xún)速度相對(duì)來(lái)說(shuō)會(huì)快很多。
2）解釋?zhuān)簽槭裁碙inkedList集合增刪效率快弃榨，而查詢(xún)速度慢菩收？
LinkedList集合增刪效率高是因?yàn)榈讓邮擎湵斫Y(jié)構(gòu)，如果增加或者刪除只需要在增加或者刪除節(jié)點(diǎn)的位置上記住新的節(jié)點(diǎn)的地址即可鲸睛，而其他節(jié)點(diǎn)不需要移動(dòng)娜饵，所以速度會(huì)快。
而查詢(xún)遍歷由于鏈表結(jié)構(gòu)的特點(diǎn)腊凶，查詢(xún)只能從頭一直遍歷到鏈表的結(jié)尾划咐，所以速度會(huì)慢。
注意：學(xué)習(xí)了這么多集合類(lèi)钧萍，在開(kāi)發(fā)中如果不知道使用哪個(gè)集合褐缠，到底什么時(shí)候使用ArrayList集合和LinkedList集合？
1）如果對(duì)集合進(jìn)行查詢(xún)操作建議使用ArrayList集合风瘦；
2）如果對(duì)集合進(jìn)行增刪操作建議使用LinkedList集合队魏；
總結(jié)：如果實(shí)在把握不好使用的時(shí)機(jī)，建議大家以后在開(kāi)發(fā)中都使用ArrayList集合即可万搔，因?yàn)樵陂_(kāi)發(fā)中我們對(duì)于集合的操作幾乎都是查詢(xún)操作胡桨，很少執(zhí)行增刪操作的。
6瞬雹、Set接口
6.1昧谊、Set接口概述
Collection集合（接口）的接口下面有2個(gè)直接的子接口：
|-----List集合（接口）：可以保存重復(fù)元素，擁有下標(biāo)酗捌，存儲(chǔ)有序呢诬，可以存儲(chǔ)多個(gè)null元素。
|-----ArrayList類(lèi)：底層是可變數(shù)組胖缤，根據(jù)下標(biāo)進(jìn)行操作尚镰，查詢(xún)效率快，增刪效率低哪廓。
|-----LinkedList類(lèi)：底層是鏈表狗唉，根據(jù)鏈表的頭尾進(jìn)行操作，增刪效率快涡真，查詢(xún)效率低分俯。
|-----Set集合（接口）：不能保存重復(fù)元素肾筐，沒(méi)有下標(biāo)“钠龋可以存儲(chǔ)null但只能有一個(gè)局齿。并且不保證存取的順序，也就是說(shuō)對(duì)于集合set進(jìn)行存取操作的時(shí)候都沒(méi)有任何順序橄登，沒(méi)有任何規(guī)律而言抓歼。
|-----HashSet類(lèi)
|-----LinkedHashSet類(lèi)
|-----TreeSet類(lèi)
說(shuō)明：
1）Set接口中沒(méi)有自己的特有函數(shù)，所有的函數(shù)全部來(lái)自于Collection接口拢锹。
2）Set集合沒(méi)有角標(biāo)谣妻，只能通過(guò)Iterator迭代器遍歷獲取集合中的元素，Set集合不能使用ListIterator迭代器卒稳，因?yàn)長(zhǎng)istIterator只是針對(duì)List集合特有的迭代器蹋半。
6.2、Set接口的練習(xí)
需求：存儲(chǔ)字符串并遍歷充坑。
由于Set是接口不能創(chuàng)建對(duì)象减江，只能創(chuàng)建Set實(shí)現(xiàn)類(lèi)的接口，任何一個(gè)都可以捻爷，這里就創(chuàng)建HashSet類(lèi)的對(duì)象辈灼。
分析和步驟：
1）使用new關(guān)鍵字創(chuàng)建Set接口下的子類(lèi)HashSet類(lèi)的對(duì)象，并賦值給對(duì)象s也榄，類(lèi)型是Set接口類(lèi)型巡莹；
2）使用對(duì)象s調(diào)用add()函數(shù)向集合中添加字符串?dāng)?shù)據(jù)；
3）循環(huán)遍歷集合甜紫；
package cn.xuexi.set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/*
* Set集合的練習(xí)
*/
public class SetDemo {
public static void main(String[] args) {
//創(chuàng)建集合對(duì)象
Set s=new HashSet();
//向Set集合中添加數(shù)據(jù)
s.add("aaa");
s.add("aaa");
s.add("bbb");
s.add(null);
s.add("ccc");
//遍歷集合
//注意：由于Set集合中不允許包含重復(fù)的元素降宅，所以當(dāng)添加元素的時(shí)候，
//集合對(duì)象會(huì)把重復(fù)的元素刪除囚霸，不讓保存到集合中
for (Iterator it = s.iterator(); it.hasNext();) {
//輸出數(shù)據(jù)
System.out.println(it.next());
}
}
}
7腰根、HashSet集合(掌握)
7.1、HashSet類(lèi)的介紹和特點(diǎn)
說(shuō)明：
1）實(shí)現(xiàn)了Set接口拓型，具備了Set集合的特性额嘿；
2）不保證集合中的迭代順序（不保證元素存取一致），允許存儲(chǔ)null元素吨述；
3）底層使用哈希表結(jié)構(gòu)岩睁；
案例：HashSet集合的應(yīng)用钞脂。
分析和步驟：
1）使用new關(guān)鍵字創(chuàng)建HashSet集合類(lèi)的對(duì)象set揣云，類(lèi)型是HashSet類(lèi)型；
2）使用集合對(duì)象set調(diào)用集合中的add()函數(shù)向HashSet集合中添加字符串?dāng)?shù)據(jù)冰啃；
3）使用對(duì)象set調(diào)用iterator()函數(shù)獲取迭代器對(duì)象it邓夕；
4）使用for循環(huán)遍歷刘莹，通過(guò)迭代器對(duì)象調(diào)用hasNext()和next()函數(shù)，并輸出獲取的數(shù)據(jù)焚刚；
package cn.xuexi.set;
import java.util.HashSet;
import java.util.Iterator;
/*
* hashSet演示
*/
public class HashSetDemo {
public static void main(String[] args) {
//創(chuàng)建HashSet集合對(duì)象
HashSet set=new HashSet();
//向集合中添加數(shù)據(jù)
set.add("JavaSe");
set.add("JavaSE");
set.add("JavaEE");
set.add("AAAA");
set.add("AAAA");
set.add("bbbb");
set.add("bbbb");
//遍歷集合
for (Iterator it = set.iterator(); it.hasNext();) {
//輸出集合中的數(shù)據(jù)
System.out.println(it.next());
}
}
}
輸出結(jié)果：
通過(guò)以上程序輸出結(jié)果得出結(jié)論：
1）HashSet集合不能存儲(chǔ)重復(fù)的元素点弯；
2）HashSet集合存儲(chǔ)元素的順序不固定；
接下我們要分析為什么HashSet集合存儲(chǔ)的數(shù)據(jù)順序不固定和為什么不支持存儲(chǔ)重復(fù)的元素矿咕？
答案肯定和HashSet集合的底層哈希表數(shù)據(jù)結(jié)構(gòu)有關(guān)系抢肛，所以接下來(lái)我們要學(xué)習(xí)什么是哈希表。
7.2碳柱、哈希表介紹(掌握)
哈希表：
它是一個(gè)數(shù)據(jù)結(jié)構(gòu)捡絮，底層依賴(lài)的是數(shù)組，只是不按照數(shù)組的下標(biāo)操作數(shù)組中的元素莲镣。需要根據(jù)數(shù)組中存儲(chǔ)的元素的哈希值進(jìn)行元素操作福稳。
哈希表的存儲(chǔ)過(guò)程：
1）哈希表底層是一個(gè)數(shù)組，我們必須知道集合中的一個(gè)對(duì)象元素到底要存儲(chǔ)到哈希表中的數(shù)組的哪個(gè)位置瑞侮，也就是需要一個(gè)下標(biāo)的圆。
2）哈希表會(huì)根據(jù)集合中的每個(gè)對(duì)象元素的內(nèi)容計(jì)算得出一個(gè)整數(shù)值。由于集合中的對(duì)象元素類(lèi)型是任意的半火，而現(xiàn)在這里使用的算法必須是任意類(lèi)型的元素都可以使用的算法越妈。能夠讓任意類(lèi)型的對(duì)象元素都可以使用的算法肯定在任意類(lèi)型的對(duì)象所屬類(lèi)的父類(lèi)中，即上帝類(lèi)Object中慈缔，這個(gè)算法就是Object類(lèi)中的hashCode()函數(shù)叮称。
結(jié)論：要給HashSet集合中保存對(duì)象，需要調(diào)用對(duì)象的hashCode函數(shù)藐鹤。
解釋說(shuō)明：
通過(guò)查閱API得知瓤檐，使用Object的任意子類(lèi)對(duì)象都可以調(diào)用Object類(lèi)中的hashCode()函數(shù)并生成任意對(duì)象的哈希碼值。
代碼演示如下：
由以上結(jié)果可以看出任意對(duì)象調(diào)用Object類(lèi)中的hashCode()函數(shù)都會(huì)生成一個(gè)整數(shù)娱节。
3）hashCode算法挠蛉，得到一個(gè)整數(shù)，但是這個(gè)整數(shù)太大了肄满，這個(gè)值不能直接作為數(shù)組下標(biāo)的谴古。所以底層還會(huì)對(duì)這個(gè)值結(jié)合數(shù)組的長(zhǎng)度繼續(xù)計(jì)算運(yùn)行，得到一個(gè)在0~數(shù)組長(zhǎng)度-1之間的整數(shù)稠歉，這樣就可以作為數(shù)組的下標(biāo)了掰担。
問(wèn)題1：使用hashCode函數(shù)生成的一個(gè)過(guò)大整數(shù)是用什么算法將將生成哈希碼值變成0~數(shù)組長(zhǎng)度-1之間的數(shù)字呢？
其中一種最簡(jiǎn)單的算法是可以實(shí)現(xiàn)的怒炸，舉例：假設(shè)底層哈希表中數(shù)組長(zhǎng)度是5带饱，那么下標(biāo)的范圍是0~4，
所以我們這里可以使用生成的哈希碼值（過(guò)大的整數(shù)）對(duì)數(shù)組長(zhǎng)度取余數(shù)，我們發(fā)現(xiàn)任何數(shù)在這里對(duì)5取余都是在 0 1 2 3 4 之間勺疼，所以這樣就可以獲取到0~數(shù)組長(zhǎng)度-1之間的下標(biāo)了教寂。
問(wèn)題2：如果數(shù)據(jù)過(guò)多，HashSet底層的數(shù)組存儲(chǔ)不下执庐，怎么辦酪耕？
hashSet集合底層數(shù)組初始容量是16，如果大小不夠轨淌，那么會(huì)繼續(xù)新創(chuàng)建一個(gè)數(shù)組迂烁，新數(shù)組大小等于原來(lái)數(shù)組的大小*0.75+原來(lái)數(shù)組的大小。
4）如果上述做法已經(jīng)計(jì)算出底層數(shù)組的下標(biāo)位置递鹉，那么就要判斷計(jì)算出的下標(biāo)位置是否已經(jīng)有元素了：
A.如果下標(biāo)對(duì)應(yīng)的位置沒(méi)有元素：直接存儲(chǔ)數(shù)據(jù)婚被；
B.如果下標(biāo)對(duì)應(yīng)的位置有元素：這時(shí)就必須調(diào)用對(duì)象的equals()函數(shù)比較兩個(gè)對(duì)象是否相同：
如果結(jié)果是true：相同，直接將要添加的數(shù)據(jù)丟棄梳虽；
如果結(jié)果是false：不相同址芯，那直接將數(shù)據(jù)存儲(chǔ)到數(shù)組當(dāng)前空間位置；
但是當(dāng)前位置已經(jīng)存在元素了窜觉，怎么將后來(lái)的數(shù)據(jù)存儲(chǔ)到數(shù)組中呢谷炸？
這里需要使用類(lèi)似鏈表的結(jié)構(gòu)了，在當(dāng)前位置上在畫(huà)出來(lái)一個(gè)空間禀挫，然后將當(dāng)前的對(duì)象數(shù)據(jù)保存到新劃出來(lái)的空間中旬陡，在原來(lái)的空間中設(shè)置一個(gè)引用變量記錄著新劃分空間的地址，如果后面還有數(shù)據(jù)要存儲(chǔ)當(dāng)前空間语婴，做法和上述相同描孟。
哈希表如下圖所示：
最終結(jié)論：哈希表底層通過(guò)hashCode和equals算法結(jié)合，來(lái)保證對(duì)象數(shù)據(jù)在HashSet集合中不重復(fù)唯一砰左，并且存儲(chǔ)的順序不固定匿醒。
哈希表：數(shù)組+hashCode函數(shù)+equals函數(shù)，哈希表保證對(duì)象唯一需要依賴(lài)對(duì)象的hashCode和equals方法缠导。
面試題：哈希表如何保證元素唯一廉羔？
哈希表保證元素唯一依賴(lài)兩個(gè)方法：hashCode和equals。
哈希表底層其實(shí)還是一個(gè)數(shù)組僻造，元素在存儲(chǔ)的時(shí)候憋他，會(huì)先通過(guò)hashCode算法結(jié)合數(shù)組長(zhǎng)度得到一個(gè)索引。然后判斷該索引位置是否有元素：如果沒(méi)有髓削，不用調(diào)用equals函數(shù)竹挡，直接存儲(chǔ)；如果有立膛，再調(diào)用元素的equals方法比較是否相同：相同揪罕，直接舍棄；如果不同，也存儲(chǔ)耸序。
7.3、HashSet保存自定義對(duì)象
案例需求：向HashSet集合中添加自定義對(duì)象鲁猩。
分析和步驟：
1）定義一個(gè)Person類(lèi)坎怪，在Person類(lèi)中定義兩個(gè)屬性name和age，并分別生成toString()廓握、set()搅窿、get()方法；
2）在定義一個(gè)測(cè)試類(lèi)HashSetDemo隙券，在這個(gè)類(lèi)中的main函數(shù)中男应，使用new關(guān)鍵字創(chuàng)建HashSet集合類(lèi)的對(duì)象set，類(lèi)型是HashSet類(lèi)型娱仔；
3）使用集合對(duì)象set調(diào)用集合中的add()函數(shù)向HashSet集合中添加Person類(lèi)的匿名對(duì)象沐飘，并通過(guò)創(chuàng)建Person類(lèi)的對(duì)象調(diào)用構(gòu)造函數(shù)給name和age賦值；
4）使用對(duì)象set調(diào)用iterator()函數(shù)獲取迭代器對(duì)象it牲迫；
5）使用for循環(huán)遍歷耐朴，通過(guò)迭代器對(duì)象調(diào)用hasNext()和next()函數(shù)，并輸出獲取的數(shù)據(jù)盹憎；
測(cè)試類(lèi)代碼如下：
package cn.xuexi.set;
import java.util.HashSet;
import java.util.Iterator;
/*
* 使用哈希表存儲(chǔ)自定義對(duì)象
*/
public class HashSetDemo2 {
public static void main(String[] args) {
//創(chuàng)建集合對(duì)象
HashSet set=new HashSet();
//向集合中添加自定義對(duì)象數(shù)據(jù)
set.add(new Person("黑旋風(fēng)",19));
set.add(new Person("助教",18));
set.add(new Person("班導(dǎo)",28));
set.add(new Person("班長(zhǎng)",19));
set.add(new Person("黑旋風(fēng)",19));
//循環(huán)遍歷集合
for (Iterator it = set.iterator(); it.hasNext();) {
//輸出數(shù)據(jù)
System.out.println(it.next());
}
}
}
運(yùn)行結(jié)果：
上述代碼有問(wèn)題筛峭，為什么以上程序中的HashSet集合中會(huì)出現(xiàn)相同的Person類(lèi)的對(duì)象？
給哈希表中保存自定義對(duì)象時(shí)陪每，由于每次創(chuàng)建的都是新的Person對(duì)象影晓，而每個(gè)Person對(duì)象都有自己的唯一的內(nèi)存地址，就是每個(gè)對(duì)象的內(nèi)存地址都不相同檩禾。并且在給哈希表中存放這些對(duì)象的時(shí)候每個(gè)對(duì)象都需要調(diào)用自己從Object類(lèi)中繼承到的hashCode函數(shù)挂签，而hashCode函數(shù)會(huì)根據(jù)每個(gè)對(duì)象自己內(nèi)存地址計(jì)算每個(gè)對(duì)象哈希值，每個(gè)對(duì)象的內(nèi)存地址不同盼产，計(jì)算出來(lái)的哈希值也一定不同竹握，最后就會(huì)導(dǎo)致生成的底層的數(shù)組的下標(biāo)也不相同。如果下標(biāo)不一樣辆飘，根本就不會(huì)去調(diào)用equals比較是否是同一個(gè)元素啦辐，直接就會(huì)導(dǎo)致每個(gè)對(duì)象都可以正常的保存到哈希表中。
自己定義的對(duì)象蜈项，有自己所屬的類(lèi)芹关，而這個(gè)類(lèi)繼承到了Object的hashCode函數(shù)，所以導(dǎo)致這個(gè)函數(shù)是根據(jù)對(duì)象內(nèi)存地址計(jì)算哈希值紧卒，而我們更希望根據(jù)對(duì)象自己的特有數(shù)據(jù)(name和age的屬性值)來(lái)計(jì)算哈希值侥衬。
問(wèn)題：那么為什么我們之前向集合中保存String類(lèi)的字符串對(duì)象時(shí)沒(méi)有出現(xiàn)這種現(xiàn)象呢？
因?yàn)樵赟tring類(lèi)中已經(jīng)復(fù)寫(xiě)了Object類(lèi)中的hashCode()和equals()函數(shù)，所以存儲(chǔ)字符串對(duì)象的時(shí)候轴总，底層調(diào)用的hashCode()和equals()函數(shù)根本就不是Object類(lèi)中的而是String類(lèi)中已經(jīng)復(fù)寫(xiě)好的函數(shù)直颅。
也就是對(duì)于String類(lèi)的對(duì)象調(diào)用自己的hashCode函數(shù)，根本就不是根據(jù)字符串對(duì)象的地址計(jì)算出來(lái)的哈希碼值怀樟，而是根據(jù)字符串內(nèi)容計(jì)算出來(lái)的功偿。
對(duì)于equals函數(shù)，也是調(diào)用自己的函數(shù)往堡，底層根本比較不是 this==obj,而是比較的是字符串對(duì)象的內(nèi)容械荷。
解決上述問(wèn)題的辦法：
所以我們需要重寫(xiě)Object類(lèi)中的hashCode方法。這樣重寫(xiě)完之后就會(huì)根據(jù)對(duì)象特有的數(shù)據(jù)來(lái)計(jì)算哈希值了虑灰，而不再是根據(jù)對(duì)象的隨機(jī)地址生成哈希值了吨瞎。在這里：根據(jù)姓名和年齡計(jì)算。
上述辦法只重寫(xiě)hashCode函數(shù)穆咐，僅僅是保證了對(duì)象內(nèi)容相同時(shí)計(jì)算的數(shù)組下標(biāo)相同颤诀。同時(shí)即使一個(gè)人的姓名和年齡不相等，也有可能計(jì)算的下標(biāo)是相同的对湃。所以着绊，當(dāng)數(shù)組下標(biāo)相同時(shí)，我們接下來(lái)還要調(diào)用equals函數(shù)來(lái)比較對(duì)象元素的內(nèi)容熟尉。根據(jù)我們之前所學(xué)的Object類(lèi)中的equals函數(shù)得知归露，Object類(lèi)中的equals函數(shù)體是比較兩個(gè)對(duì)象的地址值是否相等，那么即使兩個(gè)對(duì)象內(nèi)容的下標(biāo)相同斤儿，但是equals函數(shù)比較的不是兩個(gè)對(duì)象的內(nèi)容剧包，是地址，也會(huì)永遠(yuǎn)不相等往果，所以這里也得復(fù)寫(xiě)Object類(lèi)中的equals()函數(shù)疆液。這樣才能保證當(dāng)兩個(gè)對(duì)象內(nèi)容一致不會(huì)被保存到HashSet集合中。
所以還得重寫(xiě)equals方法陕贮。
手動(dòng)復(fù)寫(xiě)Object類(lèi)中的hashCode()和equals()函數(shù)堕油，代碼如下：
說(shuō)明：雖然上述手動(dòng)復(fù)寫(xiě)Object類(lèi)中的hashCode和equals函數(shù)可以實(shí)現(xiàn)，但是在真實(shí)開(kāi)發(fā)中建議最好不要手動(dòng)去書(shū)寫(xiě)肮之，比較麻煩掉缺。
建議直接在eclipse中使用快捷鍵生成的方式，比較簡(jiǎn)單戈擒，開(kāi)發(fā)效率還快眶明。
在Person類(lèi)中使用快捷鍵生成復(fù)寫(xiě)Object類(lèi)中的hashCode()和equals()函數(shù)：
package cn.xuexi.set;
/*
* 描述人類(lèi)
*/
public class Person {
//屬性
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = 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;
}
//復(fù)寫(xiě)Object類(lèi)中的toString()函數(shù)
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
/*//復(fù)寫(xiě)hashCode函數(shù)
@Override
public int hashCode() {
* 根據(jù)年齡和姓名計(jì)算一個(gè)int值 this.name.hashCode()表示調(diào)用String類(lèi)中的hashCode函數(shù)
* 如果兩個(gè)字符串相同，生成的哈希值也會(huì)相同 如果兩個(gè)人的名字一樣筐高，則生成哈希值相同
* this.name.hashCode()+this.age ：表示如果兩個(gè)人的姓名和年齡相同搜囱，那么返回得整數(shù)值肯定也相同
return this.name.hashCode()+this.age;
}
//復(fù)寫(xiě)equals函數(shù)
@Override
public boolean equals(Object obj) {
Person p=(Person)obj;//強(qiáng)制轉(zhuǎn)換為Person類(lèi)型的對(duì)象
return this.name.equals(p.name) && this.age==p.age;
}*/
//復(fù)寫(xiě)Object類(lèi)中的hashCode()函數(shù)
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
//復(fù)寫(xiě)Object類(lèi)中的equals()函數(shù)
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
結(jié)論：
要求以后給HashSet集合即哈希表中保存對(duì)象的時(shí)候丑瞧，要求當(dāng)前這個(gè)對(duì)象所屬的類(lèi)必須復(fù)寫(xiě)Object類(lèi)中的hashCode和equals方法。建議最好快捷鍵生成蜀肘。
7.4绊汹、HashSet總結(jié)
HashSet集合存儲(chǔ)對(duì)象的時(shí)候：
1、HashSet集合的底層使用的哈希表結(jié)構(gòu)扮宠。那么就要求存放的對(duì)象必須具備hashCode功能西乖。由于任何一個(gè)類(lèi)的父類(lèi)都是Object類(lèi)，而hashCode函數(shù)定義在了Object類(lèi)中涵卵，因此所有的對(duì)象都具備hashCode功能。
2荒叼、如果我們要把一個(gè)對(duì)象可以正確的存放在HashSet集合中轿偎，這個(gè)對(duì)象所屬的類(lèi)一般都需要復(fù)寫(xiě)hashCode函數(shù)。建立本類(lèi)自己的計(jì)算哈希值的方式被廓。
3坏晦、如果在HashSet集合中要保證對(duì)象唯一，不能僅僅依靠hashCode函數(shù)嫁乘，還要依賴(lài)于對(duì)象的equals函數(shù)昆婿，當(dāng)hashCode函數(shù)計(jì)算出來(lái)的哈希值相同的時(shí)候，還要調(diào)用equals方法比較2個(gè)對(duì)象是否相同蜓斧。
4仓蛆、要求在向HashSet集合中存儲(chǔ)自己定義一個(gè)類(lèi)對(duì)象的時(shí)候，那么必須在這個(gè)自定義類(lèi)中復(fù)寫(xiě)Object類(lèi)中的hashCode和equals函數(shù)挎春。
5看疙、注意當(dāng)向HashSet集合中存儲(chǔ)數(shù)據(jù)的時(shí)候，對(duì)象一定會(huì)調(diào)用hashCode函數(shù)計(jì)算下標(biāo)直奋，但是不一定一定會(huì)調(diào)用equals函數(shù)能庆，只有當(dāng)計(jì)算的下標(biāo)相同時(shí)
才會(huì)調(diào)用equals函數(shù)，否則不會(huì)調(diào)用equals函數(shù)來(lái)比較兩個(gè)對(duì)象是否相等脚线。
7.5搁胆、LinkedHashSet介紹(了解)
LinkedHashSet集合：它的底層使用的鏈表+哈希表結(jié)構(gòu)。它和HashSet集合的區(qū)別是LinkedHashSet是一個(gè)可以保證存取順序的集合邮绿，并且LinkedHashSet集合中的元素也不能重復(fù)渠旁。
特點(diǎn)：
A：存取有序（底層有一個(gè)鏈接表） 鏈表記錄著存儲(chǔ)數(shù)據(jù)的順序
B：保證元素的唯一（哈希表） 哈希表是真正存儲(chǔ)數(shù)據(jù)的地方
C：線程不安全，效率高
說(shuō)明：LinkedHashSet集合沒(méi)有自己的特有函數(shù)船逮，所有的功能全部繼承父類(lèi)一死。
分析和步驟：
1）定義一個(gè)測(cè)試類(lèi)LinkedHashSetDemo；
2）在這個(gè)類(lèi)中使用new關(guān)鍵字創(chuàng)建LinkedHashSet類(lèi)的對(duì)象set傻唾，對(duì)象set的類(lèi)型是LinkedHashSet投慈；
3）使用對(duì)象set調(diào)用add()函數(shù)給集合LinkedHashSet添加字符串常量承耿；
4）使用迭代器類(lèi)Iterator進(jìn)行迭代并輸出集合中的數(shù)據(jù)；
package cn.xuexi.set;
import java.util.Iterator;
import java.util.LinkedHashSet;
/*
* LinkedHashSet集合演示
*/
public class LinkedHashSetDemo {
public static void main(String[] args) {
//創(chuàng)建集合對(duì)象
LinkedHashSet set=new LinkedHashSet();
//向集合中添加數(shù)據(jù)
set.add("aaa");
set.add("bbb");
set.add("aaa");
set.add("ccc");
//遍歷集合
for (Iterator it = set.iterator(); it.hasNext();) {
//輸出集合中的數(shù)據(jù)
System.out.println(it.next());
}
}
}
