一、List接口概述
鑒于Java中數(shù)組用來存儲(chǔ)數(shù)據(jù)的局限性，我們通常使用List替代數(shù)組
List集合類中元素有序、且可重復(fù)，集合中的每個(gè)元素都有其對應(yīng)的順序索引。
?List容器中的元素都對應(yīng)一個(gè)整數(shù)型的序號記載其在容器中的位置，可以根據(jù) 序號存取容器中的元素。
JDK API中List接口的實(shí)現(xiàn)類常用的有：ArrayList、LinkedList和Vector。
List接口框架
? |----Collection接口：單列集合，用來存儲(chǔ)一個(gè)一個(gè)的對象
? ? ? |----List接口：存儲(chǔ)有序的、可重復(fù)的數(shù)據(jù)。? -->“動(dòng)態(tài)”數(shù)組,替換原有的數(shù)組
? ? ? ? |----ArrayList：作為List接口的主要實(shí)現(xiàn)類；線程不安全的，效率高；底層使用Object[] elementData存儲(chǔ)
? ? ? ? |----LinkedList：對于頻繁的插入、刪除操作，使用此類效率比ArrayList高；底層使用雙向鏈表存儲(chǔ)
? ? ? ? |----Vector：作為List接口的古老實(shí)現(xiàn)類；線程安全的，效率低；底層使用Object[] elementData存儲(chǔ)
二、List實(shí)現(xiàn)類之一：ArrayList
1. ArrayList的源碼分析：
*? 1.1 jdk 7情況下
*? ? ? ArrayList list = new ArrayList();//底層創(chuàng)建了長度是10的Object[]數(shù)組elementData
*? ? ? list.add(123);//elementData[0] = new Integer(123);
*? ? ? ...
*? ? ? list.add(11);//如果此次的添加導(dǎo)致底層elementData數(shù)組容量不夠，則擴(kuò)容。
*? ? ? 默認(rèn)情況下，擴(kuò)容為原來的容量的1.5倍，同時(shí)需要將原有數(shù)組中的數(shù)據(jù)復(fù)制到新的數(shù)組中。
*
*? ? ? 結(jié)論：建議開發(fā)中使用帶參的構(gòu)造器：ArrayList list = new ArrayList(int capacity)
*
*? 1.2 jdk 8中ArrayList的變化：
*? ? ? ArrayList list = new ArrayList();//底層Object[] elementData初始化為{}.并沒有創(chuàng)建長度為10的數(shù)組
*
*? ? ? list.add(123);//第一次調(diào)用add()時(shí)，底層才創(chuàng)建了長度10的數(shù)組，并將數(shù)據(jù)123添加到elementData[0]
*? ? ? ...
*? ? ? 后續(xù)的添加和擴(kuò)容操作與jdk 7 無異。
*? 1.3 小結(jié)：jdk7中的ArrayList的對象的創(chuàng)建類似于單例的餓漢式，而jdk8中的ArrayList的對象的創(chuàng)建類似于單例的懶漢式，延遲了數(shù)組的創(chuàng)建，節(jié)省內(nèi)存。
? ? Arrays.asList(…) 方法返回的 List 集合，既不是 ArrayList 實(shí)例，也不是 Vector 實(shí)例。 Arrays.asList(…) 返回值是一個(gè)固定長度的 List 集合。
三、List實(shí)現(xiàn)類之二：LinkedList?
LinkedList的源碼分析：
? ? ? LinkedList list = new LinkedList(); 內(nèi)部聲明了Node類型的first和last屬性，默認(rèn)值為null
? ? ? list.add(123);//將123封裝到Node中，創(chuàng)建了Node對象。
? ? ? 其中，Node定義為：體現(xiàn)了LinkedList的雙向鏈表的說法
? ? ? private static class Node<E> {
? ? ? ? ? ? E item;
? ? ? ? ? ? Node<E> next;
? ? ? ? ? ? Node<E> prev;
? ? ? ? ? ? Node(Node<E> prev, E element, Node<E> next) {
? ? ? ? ? ? this.item = element;
? ? ? ? ? ? this.next = next;
? ? ? ? ? ? this.prev = prev;
? ? ? ? ? ? }
? ? ? ? }
? ? 定義內(nèi)部類Node，作為LinkedList中保存數(shù)據(jù)的基 本結(jié)構(gòu)。Node除了保存數(shù)據(jù)，還定義了兩個(gè)變量：?
? ? ? ? prev變量記錄前一個(gè)元素的位置
? ? ? ? next變量記錄下一個(gè)元素的位置
四、List 實(shí)現(xiàn)類之三：Vector?
Vector的源碼分析：
? ? ? jdk7和jdk8中通過Vector()構(gòu)造器創(chuàng)建對象時(shí)，底層都創(chuàng)建了長度為10的數(shù)組。在擴(kuò)容方面，默認(rèn)擴(kuò)容為原來的數(shù)組長度的2倍。
五、請問ArrayList/LinkedList/Vector的異同？談?wù)勀愕睦斫猓緼rrayList底層 是什么？擴(kuò)容機(jī)制？Vector和ArrayList的最大區(qū)別?
三個(gè)類都是實(shí)現(xiàn)了List接口，存儲(chǔ)數(shù)據(jù)的特點(diǎn)相同：存儲(chǔ)有序的、可重復(fù)的數(shù)據(jù)。
ArrayList和LinkedList的異同
二者都線程不安全，相對線程安全的Vector，執(zhí)行效率高。 此外，ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。對于 隨機(jī)訪問get和set，ArrayList絕對優(yōu)于LinkedList，因?yàn)長inkedList要移動(dòng)指針。對于新增 和刪除操作add(特指插入)和remove，LinkedList比較占優(yōu)勢，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。
ArrayList和Vector的區(qū)別
Vector和ArrayList幾乎是完全相同的,唯一的區(qū)別在于Vector是同步類(synchronized)，屬于 強(qiáng)同步類。因此開銷就比ArrayList要大，訪問要慢。正常情況下,大多數(shù)的Java程序員使用 ArrayList而不是Vector,因?yàn)橥酵耆梢杂沙绦騿T自己來控制。Vector每次擴(kuò)容請求其大 小的2倍空間，而ArrayList是1.5倍。Vector還有一個(gè)子類Stack。
六、List接口方法?
List除了從Collection集合繼承的方法外，List 集合里添加了一些根據(jù)索引來 操作集合元素的方法。
void add(int index, Object ele):在index位置插入ele元素
boolean addAll(int index, Collection eles):從index位置開始將eles中的所有元素添加進(jìn)來
Object get(int index):獲取指定index位置的元素
int indexOf(Object obj):返回obj在集合中首次出現(xiàn)的位置
int lastIndexOf(Object obj):返回obj在當(dāng)前集合中末次出現(xiàn)的位置
Object remove(int index):移除指定index位置的元素，并返回此元素
Object set(int index, Object ele):設(shè)置指定index位置的元素為ele
List subList(int fromIndex, int toIndex):返回從fromIndex到toIndex位置的子集合
@Test
? ? public void test1(){
? ? ? ? ArrayList list = new ArrayList();
? ? ? ? list.add(123);
? ? ? ? list.add(456);
? ? ? ? list.add("AA");
? ? ? ? list.add(new Person("Tom",12));
? ? ? ? list.add(456);
? ? ? ? System.out.println(list);
? ? ? ? //void add(int index, Object ele):在index位置插入ele元素
? ? ? ? list.add(1,"BB");
? ? ? ? System.out.println(list);
? ? ? ? //boolean addAll(int index, Collection eles):從index位置開始將eles中的所有元素添加進(jìn)來
? ? ? ? List list1 = Arrays.asList(1, 2, 3);
? ? ? ? list.addAll(list1);
//? ? ? ? list.add(list1);
? ? ? ? System.out.println(list.size());//9
? ? ? ? //Object get(int index):獲取指定index位置的元素
? ? ? ? System.out.println(list.get(0));
? ? }
@Test
? ? public void test2(){
? ? ? ? ArrayList list = new ArrayList();
? ? ? ? list.add(123);
? ? ? ? list.add(456);
? ? ? ? list.add("AA");
? ? ? ? list.add(new Person("Tom",12));
? ? ? ? list.add(456);
? ? ? ? //int indexOf(Object obj):返回obj在集合中首次出現(xiàn)的位置。如果不存在，返回-1.
? ? ? ? int index = list.indexOf(4567);
? ? ? ? System.out.println(index);
? ? ? ? //int lastIndexOf(Object obj):返回obj在當(dāng)前集合中末次出現(xiàn)的位置。如果不存在，返回-1.
? ? ? ? System.out.println(list.lastIndexOf(456));
? ? ? ? //Object remove(int index):移除指定index位置的元素，并返回此元素
? ? ? ? Object obj = list.remove(0);
? ? ? ? System.out.println(obj);
? ? ? ? System.out.println(list);
? ? ? ? //Object set(int index, Object ele):設(shè)置指定index位置的元素為ele
? ? ? ? list.set(1,"CC");
? ? ? ? System.out.println(list);
? ? ? ? //List subList(int fromIndex, int toIndex):返回從fromIndex到toIndex位置的左閉右開區(qū)間的子集合
? ? ? ? List subList = list.subList(2, 4);
? ? ? ? System.out.println(subList);
? ? ? ? System.out.println(list);
? ? }
總結(jié)：常用方法
? 增：add(Object obj)
? 刪：remove(int index) / remove(Object obj)
? 改：set(int index, Object ele)
? 查：get(int index)
? 插：add(int index, Object ele)
? 長度：size()
? 遍歷：① Iterator迭代器方式
? ? ? ? ② 增強(qiáng)for循環(huán)(foreach)
? ? ? ? ③ 普通的循環(huán)(for)
@Test
? ? public void test3(){//遍歷
? ? ? ? ArrayList list = new ArrayList();
? ? ? ? list.add(123);
? ? ? ? list.add(456);
? ? ? ? list.add("AA");
? ? ? ? //方式一：Iterator迭代器方式
? ? ? ? Iterator iterator = list.iterator();
? ? ? ? while(iterator.hasNext()){
? ? ? ? ? ? System.out.println(iterator.next());
? ? ? ? }
? ? ? ? //方式二：增強(qiáng)for循環(huán)
? ? ? ? for(Object obj : list){
? ? ? ? ? ? System.out.println(obj);
? ? ? ? }
? ? ? ? //方式三：普通for循環(huán)
? ? ? ? for(int i = 0;i < list.size();i++){
? ? ? ? ? ? System.out.println(list.get(i));
? ? ? ? }
? ? }
/*
? ? 區(qū)分List中remove(int index)和remove(Object obj)
? ? */
? ? @Test
? ? public void testListRemove() {
? ? ? ? List list = new ArrayList();
? ? ? ? list.add(1);
? ? ? ? list.add(2);
? ? ? ? list.add(3);
? ? ? ? updateList(list);
? ? ? ? System.out.println(list);//
? ? }
? ? private void updateList(List list) {
//? ? ? ? list.remove(2);//刪除索引值為2的元素
? ? ? ? list.remove(new Integer(2));//刪除元素value值為2的元素。
? ? }
一、Set 接口概述
Set接口是Collection的子接口，Set接口沒有提供額外的方法
Set 集合不允許包含相同的元素，如果試把兩個(gè)相同的元素加入同一個(gè) Set 集合中，則添加操作失敗。
?Set 判斷兩個(gè)對象是否相同不是使用 == 運(yùn)算符，而是根據(jù)equals() 方法。
向Set(主要指：HashSet、LinkedHashSet)中添加的數(shù)據(jù)，其所在的類一定要重寫hashCode()和equals()。
1. Set接口的框架：
*
* |----Collection接口：單列集合，用來存儲(chǔ)一個(gè)一個(gè)的對象
*? ? ? ? ? |----Set接口：存儲(chǔ)無序的、不可重復(fù)的數(shù)據(jù)? -->高中講的“集合”
*? ? ? ? ? ? ? |----HashSet：作為Set接口的主要實(shí)現(xiàn)類；線程不安全的；可以存儲(chǔ)null值
*? ? ? ? ? ? ? ? ? |----LinkedHashSet：作為HashSet的子類；遍歷其內(nèi)部數(shù)據(jù)時(shí)，可以按照添加的順序遍歷
*? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 對于頻繁的遍歷操作，LinkedHashSet效率高于HashSet.
*? ? ? ? ? ? ? |----TreeSet：可以按照添加對象的指定屬性，進(jìn)行排序。
二、Set實(shí)現(xiàn)類之一：HashSet
HashSet 是 Set 接口的典型實(shí)現(xiàn)，大多數(shù)時(shí)候使用 Set 集合時(shí)都使用這個(gè)實(shí)現(xiàn)類。
HashSet 按 Hash 算法來存儲(chǔ)集合中的元素，因此具有很好的存取、查找、刪除 性能。
HashSet 具有以下特點(diǎn)： ?不能保證元素的排列順序 ?HashSet 不是線程安全的 ?集合元素可以是 null
HashSet 集合判斷兩個(gè)元素相等的標(biāo)準(zhǔn)：兩個(gè)對象通過hashCode() 方法比較相 等，并且兩個(gè)對象的 equals() 方法返回值也相等。 對于存放在Set容器中的對象，對應(yīng)的類一定要重寫equals()和hashCode(Object obj)方法，以實(shí)現(xiàn)對象相等規(guī)則。即：“相等的對象必須具有相等的散列碼”。
一、Set：存儲(chǔ)無序的、不可重復(fù)的數(shù)據(jù)
以HashSet為例說明：
1. 無序性：不等于隨機(jī)性。存儲(chǔ)的數(shù)據(jù)在底層數(shù)組中并非按照數(shù)組索引的順序添加，而是根據(jù)數(shù)據(jù)的哈希值決定的。
2. 不可重復(fù)性：保證添加的元素按照equals()判斷時(shí)，不能返回true.即：相同的元素只能添加一個(gè)。
二、添加元素的過程：以HashSet為例：
? ? 我們向HashSet中添加元素a,首先調(diào)用元素a所在類的hashCode()方法，計(jì)算元素a的哈希值，
? ? 此哈希值接著通過某種算法計(jì)算出在HashSet底層數(shù)組中的存放位置（即為：索引位置），判斷
? ? 數(shù)組此位置上是否已經(jīng)有元素：
? ? ? ? 如果此位置上沒有其他元素，則元素a添加成功。 --->情況1
? ? ? ? 如果此位置上有其他元素b(或以鏈表形式存在的多個(gè)元素），則比較元素a與元素b的hash值：
? ? ? ? ? ? 如果hash值不相同，則元素a添加成功。--->情況2
? ? ? ? ? ? 如果hash值相同，進(jìn)而需要調(diào)用元素a所在類的equals()方法：
? ? ? ? ? ? ? ? ? equals()返回true,元素a添加失敗
? ? ? ? ? ? ? ? ? equals()返回false,則元素a添加成功。--->情況3
? ? 對于添加成功的情況2和情況3而言：元素a 與已經(jīng)存在指定索引位置上數(shù)據(jù)以鏈表的方式存儲(chǔ)。
? ? jdk 7 :元素a放到數(shù)組中，指向原來的元素。
? ? jdk 8 :原來的元素在數(shù)組中，指向元素a
? ? 總結(jié)：七上八下
? ? HashSet底層：數(shù)組+鏈表的結(jié)構(gòu)。
向HashSet中添加元素的過程：
當(dāng)向 HashSet 集合中存入一個(gè)元素時(shí)，HashSet 會(huì)調(diào)用該對象的 hashCode() 方法 來得到該對象的 hashCode 值，然后根據(jù) hashCode 值，通過某種散列函數(shù)決定該對象 在 HashSet 底層數(shù)組中的存儲(chǔ)位置。（這個(gè)散列函數(shù)會(huì)與底層數(shù)組的長度相計(jì)算得到在 數(shù)組中的下標(biāo)，并且這種散列函數(shù)計(jì)算還盡可能保證能均勻存儲(chǔ)元素，越是散列分布， 該散列函數(shù)設(shè)計(jì)的越好） ? 如果兩個(gè)元素的hashCode()值相等，會(huì)再繼續(xù)調(diào)用equals方法，如果equals方法結(jié)果 為true，添加失??；如果為false，那么會(huì)保存該元素，但是該數(shù)組的位置已經(jīng)有元素了， 那么會(huì)通過鏈表的方式繼續(xù)鏈接。
如果兩個(gè)元素的 equals() 方法返回 true，但它們的 hashCode() 返回值不相 等，hashSet 將會(huì)把它們存儲(chǔ)在不同的位置，但依然可以添加成功。
三、Set實(shí)現(xiàn)類之二：LinkedHashSet
LinkedHashSet 是 HashSet 的子類 。
LinkedHashSet 根據(jù)元素的 hashCode 值來決定元素的存儲(chǔ)位置， 但它同時(shí)使用雙向鏈表維護(hù)元素的次序，這使得元素看起來是以插入 順序保存的。
LinkedHashSet插入性能略低于 HashSet，但在迭代訪問 Set 里的全 部元素時(shí)有很好的性能。
LinkedHashSet 不允許集合元素重復(fù)。
四、Set實(shí)現(xiàn)類之三：TreeSet
TreeSet 是 SortedSet 接口的實(shí)現(xiàn)類，TreeSet 可以確保集合元素處于排序狀態(tài)。
TreeSet 兩種排序方法：自然排序和定制排序。默認(rèn)情況下，TreeSet 采用自然排序。
TreeSet底層使用紅黑樹結(jié)構(gòu)存儲(chǔ)數(shù)據(jù) 。
1.向TreeSet中添加的數(shù)據(jù)，要求是相同類的對象。
2.兩種排序方式：自然排序（實(shí)現(xiàn)Comparable接口） 和 定制排序（Comparator）
3.自然排序中，比較兩個(gè)對象是否相同的標(biāo)準(zhǔn)為：compareTo()返回0.不再是equals().
4.定制排序中，比較兩個(gè)對象是否相同的標(biāo)準(zhǔn)為：compare()返回0.不再是equals().
@Test
? ? public void test1(){
? ? ? ? TreeSet set = new TreeSet();
? ? ? ? //添加元素失敗：不能添加不同類的對象
//? ? ? ? set.add(123);
//? ? ? ? set.add(456);
//? ? ? ? set.add("AA");
//? ? ? ? set.add(new User("Tom",12));
? ? ? ? ? ? //舉例一：
//? ? ? ? set.add(34);
//? ? ? ? set.add(-34);
//? ? ? ? set.add(43);
//? ? ? ? set.add(11);
//? ? ? ? set.add(8);
? ? ? ? //舉例二：
? ? ? ? set.add(new User("Tom",12));
? ? ? ? set.add(new User("Jerry",32));
? ? ? ? set.add(new User("Jim",2));
? ? ? ? set.add(new User("Mike",65));
? ? ? ? set.add(new User("Jack",33));
? ? ? ? set.add(new User("Jack",56));
? ? ? ? Iterator iterator = set.iterator();
? ? ? ? while(iterator.hasNext()){
? ? ? ? ? ? System.out.println(iterator.next());
? ? ? ? }
? ? }
@Test
? ? public void test2(){//定制排序
? ? ? ? Comparator com = new Comparator() {
? ? ? ? ? ? //按照年齡從小到大排列
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(Object o1, Object o2) {
? ? ? ? ? ? ? ? if(o1 instanceof User && o2 instanceof User){
? ? ? ? ? ? ? ? ? User u1 = (User)o1;
? ? ? ? ? ? ? ? ? User u2 = (User)o2;
? ? ? ? ? ? ? ? ? return Integer.compare(u1.getAge(),u2.getAge());
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? throw new RuntimeException("輸入的數(shù)據(jù)類型不匹配");
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? };
? ? ? ? TreeSet set = new TreeSet(com);
? ? ? ? set.add(new User("Tom",12));
? ? ? ? set.add(new User("Jerry",32));
? ? ? ? set.add(new User("Jim",2));
? ? ? ? set.add(new User("Mike",65));
? ? ? ? set.add(new User("Mary",33));
? ? ? ? set.add(new User("Jack",33));
? ? ? ? set.add(new User("Jack",56));
? ? ? ? Iterator iterator = set.iterator();
? ? ? ? while(iterator.hasNext()){
? ? ? ? ? ? System.out.println(iterator.next());
? ? ? ? }
? ? }
}
//按照姓名從大到小排列,年齡從小到大排列
? ? @Override
? ? public int compareTo(Object o) {//自然排序
? ? ? ? if(o instanceof User){
? ? ? ? ? ? User user = (User)o;
//? ? ? ? ? ? return -this.name.compareTo(user.name);
? ? ? ? ? ? int compare = -this.name.compareTo(user.name);
? ? ? ? ? ? if(compare != 0){
? ? ? ? ? ? ? ? return compare;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? return Integer.compare(this.age,user.age);
? ? ? ? ? ? }
? ? ? ? }else{
? ? ? ? ? ? throw new RuntimeException("輸入的類型不匹配");
? ? ? ? }
? ? }
}
