Java集合面試題

1、HashMap排序題

已知一個(gè) HashMap<Integer，User>集合， User 有 name（String）和 age（int）屬性。請(qǐng)寫(xiě)一個(gè)方法實(shí)現(xiàn)對(duì)HashMap 的排序功能，該方法接收 HashMap<Integer，User>為形參，返回類(lèi)型為 HashMap<Integer，User>，要求對(duì) HashMap 中的 User 的 age 倒序進(jìn)行排序。排序時(shí) key=value 鍵值對(duì)不得拆散。

注意：要做出這道題必須對(duì)集合的體系結(jié)構(gòu)非常的熟悉。HashMap本身就是不可排序的，但是該題偏偏讓HashMap排序，那我們就得想在API中有沒(méi)有這樣的 Map 結(jié)構(gòu)是有序的，我們不難發(fā)現(xiàn)其中LinkedHashMap就具有這樣的結(jié)構(gòu)，是鏈表結(jié)構(gòu)有序的，更可喜的是他是  HashMap的子類(lèi)，我們返回LinkedHashMap<Integer，User>即可，還符合面向接口編程的思想。

但凡是對(duì)集合的操作，我們應(yīng)該保持一個(gè)原則就是能用JDK中的API就用JDK中的 API，比如排序算法我們不應(yīng)該去用冒泡或者選擇，而是首先想到用 Collections 集合工具類(lèi)。

import java.util.*;

class HashMapTest {
    public static void main(String[] args) {
        HashMap<Integer, User> users = new HashMap<>();
        users.put(1, new User("張三", 25));
        users.put(3,new User("李四",22));
        users.put(2, new User("王五", 28));
        System.out.println(users);
        HashMap<Integer, User> sortHashMap = sortHashMap(users);
        System.out.println(sortHashMap);
        /**
         * 控制臺(tái)輸出內(nèi)容
         * {1=User [name=張三, age=25], 2=User [name=王五,age=28], 3=User [name=李四, age=22]}
         * {2=User [name=王五, age=28], 1=User [name=張三, age=25], 3=User [name=李四, age=22]}
         */
    }

    public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) {
        // 首先拿到 map 的鍵值對(duì)集合
        Set<Map.Entry<Integer, User>> entrySet = map.entrySet();
        // 將 set 集合轉(zhuǎn)為 List 集合，為什么，為了使用工具類(lèi)的排序方法
        List<Map.Entry<Integer,User>> list = new ArrayList<Map.Entry<Integer, User>>(entrySet);
        // 使用 Collections 集合工具類(lèi)對(duì) list 進(jìn)行排序，排序規(guī)則使用匿名內(nèi)部類(lèi)來(lái)實(shí)現(xiàn)
        Collections.sort(list, new Comparator<Map.Entry<Integer, User>>() {
            @Override
            public int compare(Map.Entry<Integer, User> o1, Map.Entry<Integer, User> o2) {
                //按照要求根據(jù) User 的 age 的倒序進(jìn)行排
                return o2.getValue().getAge() - o1.getValue().getAge();
            }
        });
        //創(chuàng)建一個(gè)新的有序的 HashMap 子類(lèi)的集合
        LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>();
        //將 List 中的數(shù)據(jù)存儲(chǔ)在 LinkedHashMap 中
        for (Map.Entry<Integer,User> entry : list) {
            linkedHashMap.put(entry.getKey(), entry.getValue());
        }
        return linkedHashMap;
    }
}

class User {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

2、請(qǐng)問(wèn) ArrayList、HashSet、HashMap 是線(xiàn)程安全的嗎？如果不是怎么獲取線(xiàn)程安全的集合？

通過(guò)以上類(lèi)的源碼進(jìn)行分析，每個(gè)方法都沒(méi)有加鎖，顯然都是非線(xiàn)程安全的。在集合中Vector 和HashTable是線(xiàn)程安全的。打開(kāi)源碼會(huì)發(fā)現(xiàn)其實(shí)就是把各自核心方法添加上了synchronized 關(guān)鍵字。Collections工具類(lèi)提供了相關(guān)的 API，可以讓上面那3個(gè)不安全的集合變?yōu)榘踩摹?/span>

Collections.synchronizedCollection(c);
Collections.synchronizedList(list);
Collections.synchronizedMap(m);
Collections.synchronizedSet(s);

上面幾個(gè)函數(shù)都有對(duì)應(yīng)的返回值類(lèi)型，傳入什么類(lèi)型返回什么類(lèi)型。打開(kāi)源碼其實(shí)原理非常簡(jiǎn)單，就是將集合的核心方法添加上了synchronized關(guān)鍵字。

3、ArrayList內(nèi)部用什么實(shí)現(xiàn)的？

回答這樣的問(wèn)題，不要只回答個(gè)皮毛，可以再介紹一下ArrayList內(nèi)部是如何實(shí)現(xiàn)數(shù)組的增加和刪除的，因?yàn)閿?shù)組在創(chuàng)建的時(shí)候長(zhǎng)度是固定的，那么就有個(gè)問(wèn)題我們往ArrayList中不斷的添加對(duì)象，它是如何管理這些數(shù)組呢？通過(guò)源碼可以看到ArrayList內(nèi)部是用Object[]實(shí)現(xiàn)的。接下來(lái)我們分別分析ArrayList的構(gòu)造以及add()、remove()、clear()方法的實(shí)現(xiàn)原理。

● 無(wú)參數(shù)構(gòu)造方法

/**
 * Constructs a new {@code ArrayList} instance with zero initial capacity.
 */
public ArrayList(){
    array=EmptyArray.OBJECT;
}

array 是一個(gè) Object[]類(lèi)型。當(dāng)我們 new 一個(gè)空參構(gòu)造時(shí)系統(tǒng)調(diào)用了 EmptyArray.OBJECT 屬性，EmptyArray 僅僅是一個(gè)系統(tǒng)的類(lèi)庫(kù)，該類(lèi)源碼如下：

public final class EmptyArray {
    private EmptyArray() {
    }
    public static final boolean[] BOOLEAN = new boolean[0];
    public static final byte[] BYTE = new byte[0];
    public static final char[] CHAR = new char[0];
    public static final double[] DOUBLE = new double[0];
    public static final int[] INT = new int[0];
    public static final Class<?>[] CLASS = new Class[0];
    public static final Object[] OBJECT = new Object[0];
    public static final String[] STRING = new String[0];
    public static final Throwable[] THROWABLE = new Throwable[0];
    public static final StackTraceElement[] STACK_TRACE_ELEMENT = new StackTraceElement[0];
}

也就是說(shuō)當(dāng)我們 new 一個(gè)空參 ArrayList 的時(shí)候，系統(tǒng)內(nèi)部使用了一個(gè) new Object[0]數(shù)組。

● 帶容量參數(shù)的構(gòu)造器

/**
 * Constructs a new instance of {@code ArrayList} with the specified
 * initial capacity.
 * @param capacity the initial capacity of this {@code ArrayList}.
 */
public ArrayList(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity < 0: " + capacity);
    }
    array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}

該構(gòu)造函數(shù)傳入一個(gè) int 值，該值作為數(shù)組的長(zhǎng)度值。如果該值小于 0，則拋出一個(gè)運(yùn)行時(shí)異常。如果等于 0，則使用一個(gè)空數(shù)組，如果大于 0，則創(chuàng)建一個(gè)長(zhǎng)度為該值的新數(shù)組。

● 帶集合參數(shù)的構(gòu)造器

/**
 * Constructs a new instance of {@code ArrayList} containing the elements of
 * the specified collection.
 *
 * @param collection the collection of elements to add.
 */
public ArrayList(Collection<? extends E> collection) {
    if (collection == null) {
        throw new NullPointerException("collection == null");
    }

    Object[] a = collection.toArray();
    if (a.getClass() != Object[].class) {
        Object[] newArray = new Object[a.length];
        System.arraycopy(a, 0, newArray, 0, a.length);
        a = newArray;
    }
    array = a;
    size = a.length;
}

如果調(diào)用構(gòu)造函數(shù)的時(shí)候傳入了一個(gè) Collection 的子類(lèi)，那么先判斷該集合是否為 null，為 null 則拋出空指針異常。如果不是則將該集合轉(zhuǎn)換為數(shù)組 a，然后將該數(shù)組賦值為成員變量 array，將該數(shù)組的長(zhǎng)度作為成員變量 size。

● add方法

/**
 * Adds the specified object at the end of this {@code ArrayList}.
 *
 * @param object the object to add.
 * @return always true
 */
@Override
public boolean add(E object) {
    Object[] a = array;
    int s = size;
    if (s == a.length) {
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ? MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

● 第一：首先將成員變量 array 賦值給局部變量 a，將成員變量 size 賦值給局部變量 s。

● 第二：判斷集合的長(zhǎng)度 s 是否等于數(shù)組的長(zhǎng)度（如果集合的長(zhǎng)度已經(jīng)等于數(shù)組的長(zhǎng)度了，說(shuō)明數(shù)組已經(jīng)滿(mǎn)了，該重新分 配 新 數(shù) 組 了 ） ， 重 新 分 配 數(shù) 組 的 時(shí) 候 需 要 計(jì) 算 新 分 配 內(nèi) 存 的 空 間 大 小 ， 如 果 當(dāng) 前 的 長(zhǎng) 度 小 于MIN_CAPACITY_INCREMENT/2（這個(gè)常量值是 12，除以 2 就是 6，也就是如果當(dāng)前集合長(zhǎng)度小于 6）則分配 12 個(gè)長(zhǎng)度，如果集合長(zhǎng)度大于 6 則分配當(dāng)前長(zhǎng)度 s 的一半長(zhǎng)度。這里面用到了三元運(yùn)算符和位運(yùn)算，s >> 1，意思就是將s 往右移 1 位，相當(dāng)于 s=s/2，只不過(guò)位運(yùn)算是效率最高的運(yùn)算。

● 第三：將新添加的 object 對(duì)象作為數(shù)組的 a[s]個(gè)元素。

● 第四：修 改 集 合 長(zhǎng) 度size為s+1。

● 第五：modCount++，該變量是父類(lèi)中聲明的，用于記錄集合修改的次數(shù)，記錄集合修改的次數(shù)是為了防止在用迭代器迭代集合時(shí)避免并發(fā)修改異常，或者說(shuō)用于判斷是否出現(xiàn)并發(fā)修改異常的。

● 第六：return true，這個(gè)返回值意義不大，因?yàn)橐恢狈祷?true，除非報(bào)了一個(gè)運(yùn)行時(shí)異常。

● remove方法

/**
 * Removes the object at the specified location from this list.
 *
 * @param index the index of the object to remove.
 * @return the removed object.
 * @throws IndexOutOfBoundsException when {@code location < 0 || location >= size()}
 */
@Override
public E remove(int index) {
    Object[] a = array;
    int s = size;
    if (index >= s) {
        throwIndexOutOfBoundsException(index, s);
    }
    @SuppressWarnings("unchecked") E result = (E) a[index];
    System.arraycopy(a, index + 1, a, index, --s - index);
    a[s] = null; // Prevent memory leak
    size = s;
    modCount++;
    return result;
}

● 第一：先將成員變量 array 和 size 賦值給局部變量 a 和 s。

● 第二：判斷形參 index 是否大于等于集合的長(zhǎng)度，如果成了則拋出運(yùn)行時(shí)異常

● 第三：獲取數(shù)組中腳標(biāo)為 index 的對(duì)象 result，該對(duì)象作為方法的返回值

● 第四：調(diào)用 System 的 arraycopy 函數(shù)完成數(shù)組拷貝。

● 第五：接下來(lái)就是很重要的一個(gè)工作，因?yàn)閯h除了一個(gè)元素，而且集合整體向前移動(dòng)了一位，因此需要將集合最后一個(gè)元素設(shè)置為 null，否則就可能內(nèi)存泄露。

● 第六：重新給成員變量 array 和 size 賦值。

● 第七：記錄修改次數(shù)。

● 第八：返回刪除的元素。

● clear方法

/**
 * Removes all elements from this {@code ArrayList}, leaving it empty.
 *
 * @see #isEmpty
 * @see #size
 */
@Override
public void clear() {
    if (size != 0) {
        Arrays.fill(array, 0, size, null);
        size = 0;
        modCount++;
    }
}

如果集合長(zhǎng)度不等于 0，則將所有數(shù)組的值都設(shè)置為 null，然后將成員變量 size 設(shè)置為 0 即可，最后讓修改記錄加 1。

4、并發(fā)集合和普通集合如何區(qū)別？

并發(fā)集合常見(jiàn)的有ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque等。并發(fā)集合位于java.util.concurrent包下，是jdk1.5之后才有的，在 java 中有普通集合、同步（線(xiàn)程安全）的集合、并發(fā)集合。

普通集合通常性能最高，但是不保證多線(xiàn)程的安全性和并發(fā)的可靠性。線(xiàn)程安全集合僅僅是給集合添加了 synchronized 同步鎖，嚴(yán)重犧牲了性能，而且對(duì)并發(fā)的效率就更低了，并發(fā)集合則通過(guò)復(fù)雜的策略不僅保證了多線(xiàn)程的安全又提高的并發(fā)時(shí)的效率。

參考閱讀：ConcurrentHashMap 是線(xiàn)程安全的 HashMap 的實(shí)現(xiàn)，默認(rèn)構(gòu)造同樣有 initialCapacity 和 loadFactor 屬性， 不過(guò)還多了一個(gè) concurrencyLevel 屬性，三屬性默認(rèn)值分別為 16、0.75 及 16。其內(nèi)部使用鎖分段技術(shù)，維持這鎖Segment 的數(shù)組，在 Segment 數(shù)組中又存放著 Entity[]數(shù)組，內(nèi)部 hash 算法將數(shù)據(jù)較均勻分布在不同鎖中。put 操作：并沒(méi)有在此方法上加上 synchronized，首先對(duì) key.hashcode 進(jìn)行 hash 操作，得到 key 的 hash 值。hash 操作的算法和map 也不同，根據(jù)此hash 值計(jì)算并獲取其對(duì)應(yīng)的數(shù)組中的Segment 對(duì)象(繼承自ReentrantLock)，接著調(diào)用此 Segment 對(duì)象的 put 方法來(lái)完成當(dāng)前操作。ConcurrentHashMap 基于 concurrencyLevel 劃分出了多個(gè) Segment 來(lái)對(duì) key-value 進(jìn)行存儲(chǔ)，從而避免每次 put 操作都得鎖住整個(gè)數(shù)組。在默認(rèn)的情況下，最佳情況時(shí)可允許 16 個(gè)線(xiàn)程并發(fā)無(wú)阻塞的操作集合對(duì)象，盡可能地減少并發(fā)時(shí)的阻塞現(xiàn)象。get(key)首先對(duì) key.hashCode 進(jìn)行 hash 操作，基于其值找到對(duì)應(yīng)的 Segment 對(duì)象，調(diào)用其 get 方法完成當(dāng)前操作。而 Segment 的 get 操作首先通過(guò) hash 值和對(duì)象數(shù)組大小減1的值進(jìn)行按位與操作來(lái)獲取數(shù)組上對(duì)應(yīng)位置的HashEntry。在這個(gè)步驟中，可能會(huì)因?yàn)閷?duì)象數(shù)組大小的改變，以及數(shù)組上對(duì)應(yīng)位置的 HashEntry 產(chǎn)生不一致性，那么 ConcurrentHashMap 是如何保證的？對(duì)象數(shù)組大小的改變只有在 put 操作時(shí)有可能發(fā)生，由于 HashEntry 對(duì)象數(shù)組對(duì)應(yīng)的變量是 volatile 類(lèi)型的，因此可以保證如 HashEntry 對(duì)象數(shù)組大小發(fā)生改變，讀操作可看到最新的對(duì)象數(shù)組大小。在獲取到了 HashEntry 對(duì)象后，怎么能保證它及其 next 屬性構(gòu)成的鏈表上的對(duì)象不會(huì)改變呢？這點(diǎn)ConcurrentHashMap 采用了一個(gè)簡(jiǎn)單的方式，即 HashEntry 對(duì)象中的 hash、key、next 屬性都是 final 的，這也就意味著沒(méi)辦法插入一個(gè) HashEntry 對(duì)象到基于 next 屬性構(gòu)成的鏈表中間或末尾。這樣就可以保證當(dāng)獲取到 HashEntry 對(duì)象后，其基于 next 屬性構(gòu)建的鏈表是不會(huì)發(fā)生變化的。ConcurrentHashMap 默認(rèn)情況下采用將數(shù)據(jù)分為 16 個(gè)段進(jìn)行存儲(chǔ)，并且 16 個(gè)段分別持有各自不同的鎖Segment，鎖僅用于 put 和 remove 等改變集合對(duì)象的操作，基于 volatile 及 HashEntry 鏈表的不變性實(shí)現(xiàn)了讀取的不加鎖。這些方式使得 ConcurrentHashMap 能夠保持極好的并發(fā)支持，尤其是對(duì)于讀遠(yuǎn)比插入和刪除頻繁的 Map 而言，而它采用的這些方法也可謂是對(duì)于 Java 內(nèi)存模型、并發(fā)機(jī)制深刻掌握的體現(xiàn)。

5、List 和 Map、Set 的區(qū)別？

● 結(jié)構(gòu)特點(diǎn)：List 和 Set 是存儲(chǔ)單列數(shù)據(jù)的集合，Map 是存儲(chǔ)鍵和值這樣的雙列數(shù)據(jù)的集合；List 中存儲(chǔ)的數(shù)據(jù)是有順序，并且允許重復(fù)；Map 中存儲(chǔ)的數(shù)據(jù)是沒(méi)有順序的，其鍵是不能重復(fù)的，它的值是可以有重復(fù)的，Set 中存儲(chǔ)的數(shù)據(jù)是無(wú)序的，且不允許有重復(fù)，但元素在集合中的位置由元素的 hashCode 決定，位置是固定的（Set 集合根據(jù) hashCode 來(lái)進(jìn)行數(shù)據(jù)的存儲(chǔ)，所以位置是固定的，但是位置不是用戶(hù)可以控制的，所以對(duì)于用戶(hù)來(lái)說(shuō) Set 中的元素還是無(wú)序的）；

● 實(shí)現(xiàn)類(lèi)：List 接口下的實(shí)現(xiàn)類(lèi)（LinkedList：基于鏈表實(shí)現(xiàn)，鏈表內(nèi)存是散亂的，每一個(gè)元素存儲(chǔ)本身內(nèi)存地址的同時(shí)還存儲(chǔ)下一個(gè)元素的地址。鏈表增刪快，查找慢；ArrayList：基于數(shù)組實(shí)現(xiàn)，非線(xiàn)程安全的，效率高，便于索引，但不便于插入刪除；Vector：基于數(shù)組實(shí)現(xiàn)，線(xiàn)程安全的，效率低）。Map 接口下的實(shí)現(xiàn)類(lèi)（HashMap：基于 hash 表的 Map 接口實(shí)現(xiàn)，非線(xiàn)程安全，高效，支持 null 值和 null 鍵；Hashtable：線(xiàn)程安全，低效，不支持 null 值和  null 鍵；LinkedHashMap：是HashMap 的一個(gè)子類(lèi)，保存了記錄的插入順序；SortedMap 接口：TreeMap，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是鍵值的升序排序）。Set 接口下的實(shí)現(xiàn)類(lèi)（HashSet：底層是由 HashMap 實(shí)現(xiàn)，不允許集合中有重復(fù)的值，使用該方式時(shí)需要重寫(xiě) equals()和 hashCode()方法；LinkedHashSet繼承與 HashSet，同時(shí)又基于LinkedHashMap 來(lái)進(jìn)行實(shí)現(xiàn)，底層使用的是LinkedHashMp）。

● 區(qū)別：List集合中對(duì)象按照索引位置排序，可以有重復(fù)對(duì)象，允許按照對(duì)象在集合中的索引位置檢索對(duì)象，例如通過(guò)list.get(i)方法來(lái)獲取集合中的元素；Map中的每一個(gè)元素包含一個(gè)鍵和一個(gè)值，成對(duì)出現(xiàn)，鍵對(duì)象不可以重復(fù)，值對(duì)象可以重復(fù)；Set集合中的對(duì)象不按照特定的方式排序，并且沒(méi)有重復(fù)對(duì)象，但它的實(shí)現(xiàn)類(lèi)能對(duì)集合中的對(duì)象按照特定的方式排序，例如 TreeSet類(lèi)，可以按照默認(rèn)順序，也可以通過(guò)實(shí)現(xiàn) java.util.Comparator接口來(lái)自定義排序方式。

6、HashMap和Hashtable有什么區(qū)別？

HashMap是非線(xiàn)程安全的，HashMap是Map的一個(gè)實(shí)現(xiàn)類(lèi)，是將鍵映射到值的對(duì)象，不允許鍵值重復(fù)。允許空鍵和空值；由于非線(xiàn)程安全，HashMap的效率要較 Hashtable 的效率高一些。Hashtable 是線(xiàn)程安全的一個(gè)集合，不允許 null 值作為一個(gè) key 值或者value 值；Hashtable是sychronized，多個(gè)線(xiàn)程訪(fǎng)問(wèn)時(shí)不需要自己為它的方法實(shí)現(xiàn)同步，而 HashMap 在被多個(gè)線(xiàn)程訪(fǎng)問(wèn)的時(shí)候需要自己為它的方法實(shí)現(xiàn)同步。

7、數(shù)組和鏈表分別比較適合用于什么場(chǎng)景，為什么？

● 數(shù)組和鏈表的區(qū)別

數(shù)組是將元素在內(nèi)存中連續(xù)存儲(chǔ)的；它的優(yōu)點(diǎn)：因?yàn)閿?shù)據(jù)是連續(xù)存儲(chǔ)的，內(nèi)存地址連續(xù)，所以在查找數(shù)據(jù)的時(shí)候效率比較高；它的缺點(diǎn)：在存儲(chǔ)之前，我們需要申請(qǐng)一塊連續(xù)的內(nèi)存空間，并且在編譯的時(shí)候就必須確定好它的空間的大小。在運(yùn)行的時(shí)候空間的大小是無(wú)法隨著你的需要進(jìn)行增加和減少而改變的，當(dāng)數(shù)據(jù)兩比較大的時(shí)候，有可能會(huì)出現(xiàn)越界的情況，數(shù)據(jù)比較小的時(shí)候，又有可能會(huì)浪費(fèi)掉內(nèi)存空間。在改變數(shù)據(jù)個(gè)數(shù)時(shí)，增加、插入、刪除數(shù)據(jù)效率比較低。鏈表是動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不需要像數(shù)組需要提前申請(qǐng)好內(nèi)存的大小，鏈表只需在用的時(shí)候申請(qǐng)就可以，根據(jù)需要來(lái)動(dòng)態(tài)申請(qǐng)或者刪除內(nèi)存空間，對(duì)于數(shù)據(jù)增加和刪除以及插入比數(shù)組靈活。還有就是鏈表中數(shù)據(jù)在內(nèi)存中可以在任意的位置，通過(guò)應(yīng)用來(lái)關(guān)聯(lián)數(shù)據(jù)（就是通過(guò)存在元素的地址來(lái)聯(lián)系）

● 鏈表和數(shù)組使用場(chǎng)景

數(shù)組應(yīng)用場(chǎng)景：數(shù)據(jù)比較少；經(jīng)常做的運(yùn)算是按序號(hào)訪(fǎng)問(wèn)數(shù)據(jù)元素；數(shù)組更容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言都支持；構(gòu)建的線(xiàn)性表較穩(wěn)定。

鏈表應(yīng)用場(chǎng)景：對(duì)線(xiàn)性表的長(zhǎng)度或者規(guī)模難以估計(jì)；頻繁做插入刪除操作；構(gòu)建動(dòng)態(tài)性比較強(qiáng)的線(xiàn)性表。

8、Java中ArrayList和LinkedList區(qū)別？

ArrayList和Vector使用了數(shù)組的實(shí)現(xiàn)，可以認(rèn)為 ArrayList 或者 Vector 封裝了對(duì)內(nèi)部數(shù)組的操作，比如向數(shù)組中添加、刪除、插入新的元素或者數(shù)據(jù)的擴(kuò)展和重定向。

LinkedList 使用了循環(huán)雙向鏈表數(shù)據(jù)結(jié)構(gòu)。與基于數(shù)組的 ArrayList 相比，這是兩種截然不同的實(shí)現(xiàn)技術(shù)，這也決定了它們將適用于完全不同的工作場(chǎng)景。

LinkedList 鏈表由一系列表項(xiàng)連接而成。一個(gè)表項(xiàng)總是包含 3 個(gè)部分：元素內(nèi)容，前驅(qū)表和后驅(qū)表，如圖所示：

在下圖展示了一個(gè)包含 3 個(gè)元素的 LinkedList 的各個(gè)表項(xiàng)間的連接關(guān)系。在 JDK 的實(shí)現(xiàn)中，無(wú)論 LikedList 是否為空，鏈表內(nèi)部都有一個(gè) header 表項(xiàng)，它既表示鏈表的開(kāi)始，也表示鏈表的結(jié)尾。表項(xiàng) header 的后驅(qū)表項(xiàng)便是鏈表中第一個(gè)元素，表項(xiàng) header 的前驅(qū)表項(xiàng)便是鏈表中最后一個(gè)元素。

ArrayList 是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList 基于鏈表的數(shù)據(jù)結(jié)構(gòu)。如果集合數(shù)據(jù)是對(duì)于集合隨機(jī)訪(fǎng)問(wèn) get 和 set，ArrayList 絕對(duì)優(yōu)于 LinkedList，因?yàn)?LinkedList 要移動(dòng)指針。如果集合數(shù)據(jù)是對(duì)于集合新增和刪除操作 add 和 remove，LinkedList 比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。

ArrayList 和 LinkedList 是兩個(gè)集合類(lèi)，用于存儲(chǔ)一系列的對(duì)象引用(references)。例如我們可以用 ArrayList 來(lái)存儲(chǔ)一系列的 String 或者 Integer。那么 ArrayList 和 LinkedList 在性能上有什么差別呢？什么時(shí)候應(yīng)該用 ArrayList 什么時(shí)候又該用 LinkedList 呢？

● 時(shí)間復(fù)雜度

首先一點(diǎn)關(guān)鍵的是，ArrayList 的內(nèi)部實(shí)現(xiàn)是基于基礎(chǔ)的對(duì)象數(shù)組的，因此，它使用 get 方法訪(fǎng)問(wèn)列表中的任意一個(gè)元素時(shí)(random access)，它的速度要比 LinkedList 快。LinkedList 中的 get 方法是按照順序從列表的一端開(kāi)始檢查，直到另外一端。對(duì) LinkedList 而言，訪(fǎng)問(wèn)列表中的某個(gè)指定元素沒(méi)有更快的方法了。

假設(shè)我們有一個(gè)很大的列表，它里面的元素已經(jīng)排好序了，這個(gè)列表可能是 ArrayList 類(lèi)型的也可能是 LinkedList 類(lèi)型的，現(xiàn)在我們對(duì)這個(gè)列表來(lái)進(jìn)行二分查找(binary search)，比較列表是 ArrayList 和 LinkedList 時(shí)的查詢(xún)速度，看下面的程序：

public class TestList {
    public static final int N = 50000;    //50000 個(gè)數(shù)
    public static List values; //要查找的集合
    //放入 50000 個(gè)數(shù)給 value；
    static {
        Integer vals[] = new Integer[N];
        Random r = new Random();
        for (int i = 0, currval = 0; i < N; i++) {
            vals = new Integer(currval);
            currval += r.nextInt(100) + 1;
        }
        values = Arrays.asList(vals);
    }
    //通過(guò)二分查找法查找
    static long timeList(List lst) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            int index = Collections.binarySearch(lst, values.get(i));
            if (index != i)
                System.out.println("***錯(cuò)誤***");
        }
        return System.currentTimeMillis() - start;
    }
    public static void main(String args[]) {
        System.out.println("ArrayList 消耗時(shí)間：" + timeList(new ArrayList(values)));
        System.out.println("LinkedList 消耗時(shí)間：" + timeList(new LinkedList(values)));
    }
}

LinkedList 做隨機(jī)訪(fǎng)問(wèn)所消耗的時(shí)間與這個(gè) list 的大小是成比例的。而相應(yīng)的，在 ArrayList 中進(jìn)行隨機(jī)訪(fǎng)問(wèn)所消耗的時(shí)間是固定的。

這是否表明 ArrayList 總是比 LinkedList 性能要好呢？這并不一定，在某些情況下 LinkedList 的表現(xiàn)要優(yōu)于ArrayList，有些算法在 LinkedList 中實(shí)現(xiàn)時(shí)效率更高。比方說(shuō)，利用 Collections.reverse 方法對(duì)列表進(jìn)行反轉(zhuǎn)時(shí)，其性能就要好些。看這樣一個(gè)例子，加入我們有一個(gè)列表，要對(duì)其進(jìn)行大量的插入和刪除操作，在這種情況下LinkedList 就是一個(gè)較好的選擇。請(qǐng)看如下一個(gè)極端的例子，我們重復(fù)的在一個(gè)列表的開(kāi)端插入一個(gè)元素：

public class ListDemo {
    static final int N = 50000;
    static long timeList(List list) {
        long start = System.currentTimeMillis();
        Object o = new Object();
        for (int i = 0; i < N; i++)
            list.add(0, o);
        return System.currentTimeMillis() - start;
    }
    public static void main(String[] args) {
        System.out.println("ArrayList 耗時(shí)：" + timeList(new ArrayList()));
        System.out.println("LinkedList 耗時(shí)：" + timeList(new LinkedList()));
    }
}

輸出結(jié)果是：

ArrayList 耗時(shí)：2463

LinkedList 耗時(shí)：15

● 空間復(fù)雜度

在 LinkedList 中有一個(gè)私有的內(nèi)部類(lèi)，定義如下：

private static class Entry {
    Object element;
    Entry next;
    Entry previous;
}

每個(gè) Entry對(duì)象reference列表中的一個(gè)元素，同時(shí)還有在 LinkedList 中它的上一個(gè)元素和下一個(gè)元素。一個(gè)有1000個(gè)元素的LinkedList 對(duì)象將有 1000 個(gè)鏈接在一起的 Entry 對(duì)象，每個(gè)對(duì)象都對(duì)應(yīng)于列表中的一個(gè)元素。這樣的話(huà)，在一個(gè) LinkedList 結(jié)構(gòu)中將有一個(gè)很大的空間開(kāi)銷(xiāo)，因?yàn)樗鎯?chǔ)這 1000 個(gè) Entity 對(duì)象的相關(guān)信息。

ArrayList 使用一個(gè)內(nèi)置的數(shù)組來(lái)存儲(chǔ)元素，這個(gè)數(shù)組的起始容量是10。當(dāng)數(shù)組需要增長(zhǎng)時(shí)，新的容量按如下公式獲得：新容量=(舊容量*3)/2+1，也就是說(shuō)每一次容量大概會(huì)增長(zhǎng) 50%。這就意味著，如果你有一個(gè)包含大量元素的 ArrayList 對(duì)象，那么最終將有很大的空間會(huì)被浪費(fèi)掉，這個(gè)浪費(fèi)是由ArrayList 的工作方式本身造成的。如果沒(méi)有足夠的空間來(lái)存放新的元素，數(shù)組將不得不被重新進(jìn)行分配以便能夠增加新的元素。對(duì)數(shù)組進(jìn)行重新分配，將會(huì)導(dǎo)致性能急劇下降。如果我們知道一個(gè)ArrayList將會(huì)有多少個(gè)元素，我們可以通過(guò)構(gòu)造方法來(lái)指定容量。我們還可以通過(guò) trimToSize 方法在 ArrayList 分配完畢之后去掉浪費(fèi)掉的空間。

● 總結(jié)

ArrayList 和 LinkedList 在性能上各有優(yōu)缺點(diǎn)，都有各自所適用的地方，總的說(shuō)來(lái)可以描述如下：

第一：對(duì) ArrayList 和 LinkedList 而言，在列表末尾增加一個(gè)元素所花的開(kāi)銷(xiāo)都是固定的。對(duì) ArrayList 而言，主要是在內(nèi)部數(shù)組中增加一項(xiàng)，指向所添加的元素，偶爾可能會(huì)導(dǎo)致對(duì)數(shù)組重新進(jìn)行分配；而對(duì) LinkedList 而言，這個(gè)開(kāi)銷(xiāo)是統(tǒng)一的，分配一個(gè)內(nèi)部 Entry 對(duì)象。

第二：在 ArrayList 的中間插入或刪除一個(gè)元素意味著這個(gè)列表中剩余的元素都會(huì)被移動(dòng)；而在 LinkedList 的中間插入或刪除一個(gè)元素的開(kāi)銷(xiāo)是固定的。

第三：LinkedList 不支持高效的隨機(jī)元素訪(fǎng)問(wèn)。

第四：ArrayList 的空間浪費(fèi)主要體現(xiàn)在在 list 列表的結(jié)尾預(yù)留一定的容量空間，而 LinkedList 的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗相當(dāng)?shù)目臻g。

可以這樣說(shuō)：當(dāng)操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間，并且需要隨機(jī)地訪(fǎng)問(wèn)其中的元素時(shí)，使用ArrayList 會(huì)提供比較好的性能；當(dāng)你的操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù)，并且按照順序訪(fǎng)問(wèn)其中的元素時(shí)，就應(yīng)該使用LinkedList了。

9、List a=new ArrayList()和ArrayList a =new ArrayList()的區(qū)別？

List list = new ArrayList();這句創(chuàng)建了一個(gè) ArrayList 的對(duì)象后賦給了List。此時(shí)它是一個(gè) List 對(duì)象了，有些ArrayList 有但是 List 沒(méi)有的屬性和方法，它就不能再用了。而ArrayList list=new ArrayList();創(chuàng)建一對(duì)象則保留了ArrayList 的所有屬性。 所以需要用到 ArrayList 獨(dú)有的方法的時(shí)候不能用前者。實(shí)例代碼如下：

List list = new ArrayList();
ArrayList arrayList = new ArrayList();
list.trimToSize(); //錯(cuò)誤，沒(méi)有該方法。
arrayList.trimToSize();    //ArrayList 里有該方法。

10、請(qǐng)用兩個(gè)隊(duì)列模擬堆棧結(jié)構(gòu)？

兩個(gè)隊(duì)列模擬一個(gè)堆棧，隊(duì)列是先進(jìn)先出，而堆棧是先進(jìn)后出。模擬如下隊(duì)列 a 和 b：

● 入棧：a 隊(duì)列為空，b 為空。例：則將”a，b，c，d，e”需要入棧的元素先放 a 中，a 進(jìn)棧為”a，b，c，d，e”出棧：a 隊(duì)列目前的元素為”a，b，c，d，e”。將 a 隊(duì)列依次加入 Arraylist 集合 a 中。以倒序的方法，將 a 中的集合取出，放入 b 隊(duì)列中，再將 b 隊(duì)列出列。代碼如下：

public static void main(String[] args) {
    Queue<String> queue = new LinkedList<String>(); //a 隊(duì) 列
    Queue<String> queue2 = new LinkedList<String>();    //b 隊(duì)列
    ArrayList<String> a = new ArrayList<String>();    //arrylist 集合是中間參數(shù)
    //往 a 隊(duì)列添加元素
    queue.offer("a");
    queue.offer("b");
    queue.offer("c");
    queue.offer("d");
    queue.offer("e");
    System.out.print("進(jìn)棧：");    //a 隊(duì)列依次加入 list 集合之中
    for (String q : queue) {
        a.add(q);
        System.out.print(q);
    }
    //以倒序的方法取出（a 隊(duì)列依次加入 list 集合）之中的值，加入 b 對(duì)列
    for (int i = a.size() - 1; i >= 0; i--) {
        queue2.offer(a.get(i));
    }
    //打印出棧隊(duì)列
    System.out.println("");
    System.out.print("出棧：");
    for (String q : queue2) {
        System.out.print(q);
    }
}

運(yùn)行結(jié)果為（遵循棧模式先進(jìn)后出）：

進(jìn)棧：a b c d e

出棧：e d c b a

11、Map中的key和value可以為null？

HashMap 對(duì)象的 key、value 值均可為 null。Hahtable 對(duì)象的 key、value 值均不可為 null。且兩者的的 key 值均不能重復(fù)，若添加 key 相同的鍵值對(duì)，后面的 value 會(huì)自動(dòng)覆蓋前面的 value，但不會(huì)報(bào)錯(cuò)。測(cè)試代碼如下：

public class Test {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>();//HashMap 對(duì)象
        Map<String, String> tableMap = new Hashtable<String, String>();//Hashtable 對(duì)象
        map.put(null, null);
        System.out.println("hashMap 的[key]和[value]均可以為 null:" + map.get(null));
        try {
            tableMap.put(null, "3");
            System.out.println(tableMap.get(null));
        } catch (Exception e) {
            System.out.println("【ERROR】：hashtable 的[key]不能為 null");
        }
        try {
            tableMap.put("3", null);
            System.out.println(tableMap.get("3"));
        } catch (Exception e) {
            System.out.println("【ERROR】：hashtable的[value]不能為null");
        }
    }
}

運(yùn)行結(jié)果：

hashMap 的[key]和[value]均可以為 null:null

【ERROR】：hashtable 的[key]不能為 null

【ERROR】：hashtable 的[value]不能為 null