2018-12-25 java集合框架總結

1.List，Set,Map之間的區(qū)別

List：對付順序的好幫手

List接口存儲一組不唯一（可以有多個元素引用相同的對象），有序的對象

Set:注重獨一無二的性質

不允許重復的集合。不會有多個元素引用相同的對象。

Map:用Key來搜索的專家

使用鍵值對存儲。Map會維護與Key有關聯(lián)的值。兩個Key可以引用相同的對象，但Key不能重復，典型的Key是String類型，但也可以是任何對象。

2.ArrayList與LinkedList的區(qū)別

Arraylist底層使用的是數(shù)組（存讀數(shù)據(jù)效率高，插入刪除特定位置效率低），LinkedList底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結構（插入，刪除效率特別高）。學過數(shù)據(jù)結構這門課后我們就知道采用鏈表存儲，插入，刪除元素時間復雜度不受元素位置的影響，都是近似O（1）而數(shù)組為近似O（n），因此當數(shù)據(jù)特別多，而且經(jīng)常需要插入刪除元素時建議選用LinkedList.一般程序只用Arraylist就夠用了，因為一般數(shù)據(jù)量都不會蠻大，Arraylist是使用最多的集合類。

3.ArrayList 與 Vector 區(qū)別

ArrayList是Vector的高級版，它是用來替換Vector的，ArrayList是線程不安全的，Vector的所有方法都是同步的，故當2個線程同時訪問的時候要花費大量的時間，故用ArrayList來替換他。

4.HashMap 和 Hashtable 的區(qū)別

1.HashMap是線程不安全的，HashTable是線程安全的，HashTable的內(nèi)部方法基本都使用synchronized修飾。
2.HashMap比HashTable效率高，HashTable基本被淘汰。
3.HashMap允許有鍵值都為null，HashTable鍵值都不可以為null，否則會報NullPointerException。
Hashtable和HashMap有幾個主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用Java5或以上的話，請使用ConcurrentHashMap吧


圖片.png

5.HashMap 和 ConcurrentHashMap 的區(qū)別

1.ConcurrentHashMap采用鎖分段技術，將整個Hash桶進行了分段segment，也就是將這個大的數(shù)組分成了幾個小的片段segment，而且每個小的片段segment上面都有鎖存在，那么在插入元素的時候就需要先找到應該插入到哪一個片段segment，然后再在這個片段上面進行插入，而且這里還需要獲取segment鎖。相對于HashTable的synchronized鎖的粒度更精細了一些，并發(fā)性能更好，而HashMap沒有鎖機制，不是線程安全的。（JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實現(xiàn),利用CAS算法。）

2.HashMap的鍵值對允許有null，但是ConCurrentHashMap都不允許。

6. HashSet如何檢查重復

當我們將對象存入到HashSet當中的時候，HashSet會調用當前對象的HashCode()進行比較，如果該HashCode已經(jīng)存在，HashSet會調用equals()方法進行比較，如果兩者相同，HashSet就不會讓加入操作成功，如果不同就使用拉鏈法插入。

（一）hashCode（）與equals（）的相關規(guī)定：

如果兩個對象相等，則hashcode一定也是相同的
兩個對象相等,對兩個equals方法返回true
兩個對象有相同的hashcode值，它們也不一定是相等的
綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋
hashCode()的默認行為是對堆上的對象產(chǎn)生獨特值。如果沒有重寫hashCode()，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數(shù)據(jù)）。

（二）==與equals()

  1. ==是判斷兩個變量或實例是不是指向同一個內(nèi)存空間 equals是判斷兩個變量或實例所指向的內(nèi)存空間的值是不是相同
  2. ==是指對內(nèi)存地址進行比較 equals()是對字符串的內(nèi)容進行比較.
    3.==指引用是否相同 equals()指的是值是否相同

7.comparable與comparator的區(qū)別

1.comparable接口是java.lang下的包，他有一個compareTo(Object obj)方法用來排序。
2.Comparator接口是java.util下的包，有一個compare(Object obj1, Object obj2)方法用來排序。

一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo方法或compare方法，當我們需要對某一個集合實現(xiàn)兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個Comparator來實現(xiàn)歌名排序和歌星名排序

(一)Comparator定制排序

package com.xd.map;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Test8 {    

   public static void main(String[] args) {
       
       ArrayList<Integer> arrayList = new ArrayList<Integer>();
        arrayList.add(-1);
        arrayList.add(3);
        arrayList.add(3);
        arrayList.add(-5);
        arrayList.add(7);
        arrayList.add(4);
        arrayList.add(-9);
        arrayList.add(-7);
        System.out.println("原始數(shù)組:");
        System.out.println(arrayList);
        System.out.println("****************************定制化排序**********************************");
        //集合反轉
        Collections.reverse(arrayList);
        System.out.println(arrayList);
        //將list集合的后面4個數(shù)轉換到前面
        Collections.rotate(arrayList, 4);
        System.out.println(arrayList);
        //將list集合的前4個數(shù)放到后面
        Collections.rotate(arrayList, -4);
        System.out.println(arrayList);

        //按照自然排序升序排序
        Collections.sort(arrayList);
        System.out.println(arrayList);
   }
}

重寫compareTo方法實現(xiàn)按年齡來排序

ackage cn.demo;
 
public class Student implements Comparable{
    private int number=0;           //學號
    private String name="";         //學生姓名
    private String gender="";       //性別
    public int getNumber(){
        return number;
    }
    public void setNumber(int number){
        this.number=number;
    }
    public String getName(){
        return name;
    }
    public void setName(String name){
        this.name=name;
    }
    public String getGender(){
        return gender;
    }
    public void setGender(String gender){
        this.gender=gender;
    }
    
    public int compareTo(Object obj){
        Student student=(Student)obj;
        if(this.number==student.number){  
            return 0;           //如果學號相同，那么兩者就是相等的
        }else if(this.number>student.getNumber()){ 
            return 1;           //如果這個學生的學號大于傳入學生的學號
        }else{ 
            return -1;          //如果這個學生的學號小于傳入學生的學號
        }
    }
}


package cn.demo;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
 
public class Test {
    public static void main(String[] args) {
        Student student1=new Student();
        student1.setNumber(5);
        Student student2=new Student();
        student2.setNumber(2);
        Student student3=new Student();
        student3.setNumber(1);
        Student student4=new Student();
        student4.setNumber(4);
        ArrayList<Student> list=new ArrayList<Student>();
        list.add(student1);
        list.add(student2);
        list.add(student3);
        list.add(student4);
        System.out.println("-------排序前-------");
        Iterator<Student> iterator=list.iterator();
        while(iterator.hasNext()){
            Student stu=iterator.next();
            System.out.println(stu.getNumber());
        }
        //使用Collections的sort方法對list進行排序
        System.out.println("-------排序后-------");
        Collections.sort(list); 
        iterator=list.iterator();
        while(iterator.hasNext()){
            Student stu=iterator.next();
            System.out.println(stu.getNumber());
        } 
 
    }
}

如何對Object的list排序

對objects數(shù)組進行排序，我們可以用Arrays.sort()方法
對objects的集合進行排序，需要使用Collections.sort()方法

8.如何實現(xiàn)數(shù)組與List的相互轉換

List轉數(shù)組：toArray(arraylist.size()方法；數(shù)組轉List:Arrays的asList(a)方法

    List<String> arrayList = new ArrayList<String>();
        arrayList.add("s");
        arrayList.add("e");
        arrayList.add("n");
        /**
         * ArrayList轉數(shù)組
         */
        int size=arrayList.size();
        String[] a = arrayList.toArray(new String[size]);
        //輸出第二個元素
        System.out.println(a[1]);//結果：e
        //輸出整個數(shù)組
        System.out.println(Arrays.toString(a));//結果：[s, e, n]
        /**
         * 數(shù)組轉list
         */
        List<String> list=Arrays.asList(a);
        /**
         * list轉Arraylist
         */
        List<String> arrayList2 = new ArrayList<String>();
        arrayList2.addAll(list);
        System.out.println(list);

如何求ArrayList集合的交集 并集 差集 去重復并集

需要用到List接口中定義的幾個方法：

addAll(Collection<? extends E> c) :按指定集合的Iterator返回的順序將指定集合中的所有元素追加到此列表的末尾 實例代碼：
retainAll(Collection<?> c): 僅保留此列表中包含在指定集合中的元素。
removeAll(Collection<?> c) :從此列表中刪除指定集合中包含的所有元素。

package com.xd.map;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test9 {    

   public static void main(String[] args) {
       
       List<Integer> list1 = new ArrayList<Integer>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);

        List<Integer> list2 = new ArrayList<Integer>();
        list2.add(2);
        list2.add(3);
        list2.add(4);
        list2.add(5);
        // 并集
        // list1.addAll(list2);
        // 交集
        //list1.retainAll(list2);
        // 差集
        //list1.removeAll(list2);
        // 無重復并集
        list2.removeAll(list1);
        list1.addAll(list2);
        for (Integer i : list1) {
            System.out.println(i);
        } 
   }
}

HashMap 的工作原理及代碼實現(xiàn)

集合框架源碼學習之HashMap(JDK1.8)

ConcurrentHashMap 的工作原理及代碼實現(xiàn)

ConcurrentHashMap實現(xiàn)原理及源碼分析

9.集合框架底層數(shù)據(jù)結構總結

Collection

1. List

  • Arraylist：數(shù)組（查詢快,增刪慢 線程不安全,效率高 ）
  • Vector：數(shù)組（查詢快,增刪慢 線程安全,效率低 ）
  • LinkedList：鏈表（查詢慢,增刪快 線程不安全,效率高 ）

2. Set

  • HashSet（無序，唯一）:哈希表或者叫散列集(hash table)
  • LinkedHashSet：鏈表和哈希表組成 。 由鏈表保證元素的排序 ， 由哈希表證元素的唯一性
  • TreeSet（有序，唯一）：紅黑樹(自平衡的排序二叉樹。)

- Map

  • HashMap：基于哈希表的Map接口實現(xiàn)（哈希表對鍵進行散列，Map結構即映射表存放鍵值對）
  • LinkedHashMap:HashMap 的基礎上加上了鏈表數(shù)據(jù)結構
  • HashTable:哈希表
  • TreeMap:紅黑樹（自平衡的排序二叉樹）

集合的選用

主要根據(jù)集合的特點來選用，比如我們需要根據(jù)鍵值獲取到元素值時就選用Map接口下的集合，需要排序時選擇TreeMap,不需要排序時就選擇HashMap,需要保證線程安全就選用ConcurrentHashMap.當我們只需要存放元素值時，就選擇實現(xiàn)Collection接口的集合，需要保證元素唯一時選擇實現(xiàn)Set接口的集合比如TreeSet或HashSet，不需要就選擇實現(xiàn)List接口的比如ArrayList或LinkedList，然后再根據(jù)實現(xiàn)這些接口的集合的特點來選用。

10. Arraylist 與 LinkedList 異同

  • 1. 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
  • 2. 底層數(shù)據(jù)結構： Arraylist 底層使用的是Object數(shù)組；LinkedList 底層使用的是雙向鏈表數(shù)據(jù)結構（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別：）； 詳細可閱讀JDK1.7-LinkedList循環(huán)鏈表優(yōu)化
  • 3. 插入和刪除是否受元素位置的影響： ① ArrayList 采用數(shù)組存儲，所以插入和刪除元素的時間復雜度受元素位置的影響。 比如：執(zhí)行add(E e) 方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間復雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element) ）時間復雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作。 ② LinkedList 采用鏈表存儲，所以插入，刪除元素時間復雜度不受元素位置的影響，都是近似 O（1）而數(shù)組為近似 O（n）。
  • 4. 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持?？焖匐S機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index) 方法)。
  • 5. 內(nèi)存空間占用： ArrayList的空 間浪費主要體現(xiàn)在在list列表的結尾會預留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅以及數(shù)據(jù)）。

補充內(nèi)容:RandomAccess接口

public interface RandomAccess {
}

查看源碼我們發(fā)現(xiàn)實際上 RandomAccess 接口中什么都沒有定義。所以，在我看來 RandomAccess 接口不過是一個標識罷了。標識什么？ 標識實現(xiàn)這個接口的類具有隨機訪問功能。

ArraysList 實現(xiàn)了 RandomAccess 接口， 而 LinkedList 沒有實現(xiàn)。

下面再總結一下 list 的遍歷方式選擇：

實現(xiàn)了RadmoAcces接口的list，優(yōu)先選擇普通for循環(huán) ，其次foreach,
未實現(xiàn)RadmoAcces接口的ist， 優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過iterator實現(xiàn)的），大size的數(shù)據(jù)，千萬不要使用普通for循環(huán)

ArrayList 與 Vector 區(qū)別

Vector類的所有方法都是同步的?？梢杂蓛蓚€線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。

Arraylist不是同步的，所以在不需要保證線程安全時時建議使用Arraylist。

HashMap 和 Hashtable 的區(qū)別

   1.線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?   2.效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
   3.對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋出 NullPointerException。
   4.初始容量大小和每次擴充容量大小的不同 ： ①創(chuàng)建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之后每次擴充，容量變?yōu)樵瓉淼?n+1。HashMap 默認的初始化大小為16。之后每次擴充，容量變?yōu)樵瓉淼?倍。②創(chuàng)建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大?。℉ashMap 中的tableSizeFor()方法保證，下面給出了源代碼）。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方。
   5.底層數(shù)據(jù)結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。

HashMap，Hashtable，ArrayList初始容量大小

  • Arraylist的初始容量是10，每次擴容之后容量都會變?yōu)樵瓉淼?1.5 倍！
  • HashMap的初始容量是16，之后每次擴充，容量變?yōu)樵瓉淼?倍，創(chuàng)建時如果給定了容量初始值，而 HashMap 會將其擴充為2的冪次方大小。
  • Hashtable 默認的初始大小為11，之后每次擴充，容量變?yōu)樵瓉淼?n+1，創(chuàng)建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小。

HashMap 多線程操作導致死循環(huán)問題

在多線程下，進行 put 操作會導致 HashMap 死循環(huán)，原因在于 HashMap 的擴容 resize()方法
注意：jdk1.8已經(jīng)解決了死循環(huán)的問題。

11.HashSet 和 HashMap 區(qū)別

hashSet 底層就是基于 HashMap 實現(xiàn)的。（HashSet 的源碼非常非常少，因為除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不實現(xiàn)之外，其他方法都是直接調用 HashMap 中的方法。）

圖片.png

12. ConcurrentHashMap 和 Hashtable 的區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實現(xiàn)線程安全的方式上不同。

底層數(shù)據(jù)結構： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實現(xiàn)，JDK1.8 采用的數(shù)據(jù)結構跟HashMap1.8的結構一樣，數(shù)組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結構類似都是采用 數(shù)組+鏈表 的形式，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的；

實現(xiàn)線程安全的方式（重要）： ① 在JDK1.7的時候，ConcurrentHashMap（分段鎖） ****對整個桶數(shù)組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數(shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會存在鎖競爭，提高并發(fā)訪問率。***（默認分配16個Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的時候已經(jīng)摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結構來實現(xiàn)，并發(fā)控制使用 synchronized 和 CAS 來操作。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化） 整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結構，但是已經(jīng)簡化了屬性，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態(tài)，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。

對整個桶數(shù)組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數(shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會存在鎖競爭，提高并發(fā)訪問率（默認分配16個Segment，比Hashtable效率提高16倍。）

圖片.png

圖片.png

13.ConcurrentHashMap線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)

首先將數(shù)據(jù)分為一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中一個段數(shù)據(jù)時，其他段的數(shù)據(jù)也能被其他線程訪問。

ConcurrentHashMap 是由 Segment 數(shù)組結構和 HashEntry 數(shù)組結構組成。

14.集合框架底層數(shù)據(jù)結構總結

Collection

1. List

2. Set

  • HashSet（無序，唯一）: 基于 HashMap 實現(xiàn)的，底層采用 HashMap 來保存元素
  • LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內(nèi)部是通過 LinkedHashMap 來實現(xiàn)的。有點類似于我們之前說的LinkedHashMap 其內(nèi)部是基于 Hashmap 實現(xiàn)一樣，不過還是有一點點區(qū)別的。
  • TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。)

Map

  • HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間
  • LinkedHashMap: LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現(xiàn)了訪問順序相關邏輯。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》
  • HashTable: 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的
  • TreeMap: 紅黑樹（自平衡的排序二叉樹）
最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • Java集合類可用于存儲數(shù)量不等的對象,并可以實現(xiàn)常用的數(shù)據(jù)結構如棧,隊列等,Java集合還可以用于保存具有映射關...
    小徐andorid閱讀 2,087評論 0贊 13
  • 原文地址 Java集合 Java集合框架：是一種工具類，就像是一個容器可以存儲任意數(shù)量的具有共同屬性的對象。 Ja...
    gyl_coder閱讀 1,039評論 0贊 8
  • 一、集合入門總結 集合框架： Java中的集合框架大類可分為Collection和Map；兩者的區(qū)別： 1、Col...
    程序員歐陽閱讀 11,812評論 2贊 61
  • 在一個方法內(nèi)部定義的變量都存儲在棧中，當這個函數(shù)運行結束后，其對應的棧就會被回收，此時，在其方法體中定義的變量將不...
    Y了個J閱讀 4,573評論 1贊 14
  • 在第二課時教學中，我以學生為本、以讀為主線,引導學生采用多種形式的朗讀如指名讀、小組讀、師范讀、齊讀、男女生合作讀...
    莫名_3afe閱讀 209評論 0贊 0

友情鏈接更多精彩內(nèi)容