Java中的集合（面試題2）

二、add方法

add方法有兩個重載,這裡隻研究最簡單的那個。

/*
* Adds the specified object at the end of this {@code ArrayList}.
* @param obj ect
* 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;
}

      

1、首先将成員變量array指派給局部變量a,将成員變量size指派給局部變量s。

2、判斷集合的長度s是否等于數組的長度(如果集合的長度已經等于數組的長度了,說明數組已經滿了，該重新配置設定新數組了)，重新配置設定數組的時候需要計算新配置設定記憶體的空間大小，如果目前的長度小于MIN_CAPACITY INCREMENT/2 (這個常量值是12,除以2就是6,也就是如果目前集合長度小于6)則配置設定12個長度，如果集合長度大于6則配置設定目前長度s的一半長度。這裡面用到了三元運算符和位運算，s >> 1,意思就是将s往右移1位,相當于s=s/2,隻不過位運算是效率最高的運算。

3、将新添加的object對象作為數組的a[s]個元素。

4、修改集合長度size為s+1。

5、modCotun+ +,該變量是父類中聲明的，用于記錄集合修改的次數,記錄集合修改的次數是為了防止在用疊代器疊代集合時避免并發修改異常，或者說用于判斷是否出現并發修改異常的。

6、return true,這個傳回值意義不大，因為一直傳回true,除非報了一個運作時異常。

三、remove方法

remove方法有兩個重載，我們隻研究remove (int index)方法。

/*Removes the object at the specified location from this list.
* @param index
* the index of the object to remove 。
* areturn the removed object. 
* @throws IndexOu tofBounds Exception
* when {@code location < 0 || location >= size() }
*/
@Override public E remove (int index) {
    object[] a = array;
    int s = size;
    if (index >= s) {
  throwIndexOu tOfBounds Exception (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;
}      

1、先将成員變量array和size指派給局部變量a和s。

2、判斷形參index是否大于等于集合的長度，如果成了則抛出運作時異常

3、擷取數組中腳标為index的對象result,該對象作為方法的傳回值

4、調用System的arraycopy函數，拷貝原理如下圖所示。

System.arraycopy(a, index + 1，a, index, --s - index);

假設index=2，那麼要删除的對象如圖打叉部分，我們隻需要将該數組後面藍色區域整體往前移動一位位置即可。上面的代碼完成就是這個工作。

5.接下來就是很重要的一個工作,因為删除了一個元素，而且集合整體向前移動了一位,是以需要将集合最後一個元索設定為null,否則就可能記憶體洩露。

6、重新給成員變量array 和size指派。

7.記錄修改次數。

8、傳回删除的元素(讓使用者再看最後一眼)。

四、dear方法

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

4. List 的三個子類的特點

ArrayList底層結構是數組底層查詢快,增删慢。

LinkedList底層結構是連結清單型的,增删快,查詢慢。

voctor底層結構是數組 線程安全的,增删慢查詢慢。

5. List 和Map、Set 的差別

5.1結構特點

List和Set是存儲單列資料的集合，

Map是存儲鍵和值這樣的雙列資料的集合;

List 中存儲的資料是有順序,并且允許重複; Map中存儲的資料是沒有順序的，其鍵是不能重複的，它的值是可以有重複的，Set 中存儲的資料是無序的，且不允許有重複,但元素在集合中的位置由元素的hashcode決定,位置是固定的(Set集合根據hashcode來

進行資料的存儲,是以位置是固定的,但是位置不是使用者可以控制的,是以對于使用者來說set中的元素還是無序的) ;

5.2實作類

List接口有三個實作類(LinkedList:基于連結清單實作,連結清單記憶體是散亂的,每一個元素存儲本身記憶體位址的同時還存儲下一個元素的位址。連結清單增删快,查找慢; ArrayList: 基于數組實作，非線程安全的,效率高，便于索引，但不便于插入删除; Vector:基于數組實作，線程安全的，效率低)。

Map接口有三個實作類(HashMap: 基于hash表的Map接口實作,非線程安全,高效，支援null值和null鍵; HashTable: 線程安全，低效,不支援null值和null鍵; LinkedHashMap: 是HashMap的一個子類,儲存了記錄的插入順序; SortMap 接口: TreeMap, 能夠把它儲存的記錄根據鍵排序,預設是鍵值的升序排序)。

Set接口有兩個實作類(HashSet: 底層是由HashMap實作，不允許集合中有重複的值，使用該方式時需要重寫equals0和hashCode0方法; LinkedHashSet: 繼承與HashSet,同時又基于LinkedHashMap來進行實作，底層使用的是LinkedHashMp)。

5.3差別

List集合中對象按照索引位置排序，可以有重複對象，允許按照對象在集合中的索引位置檢索對象，例如通過list.get()方法來擷取集合中的元素; Map中的每一個元素包含一個鍵和一個值，成對出現，鍵對象不可以重複,值對象可以重複; Set集合中的對象不按照特定的方式排序,并且沒有重複對象,但它的實作類能對集合中的對象按照特定的方式排序,例如TreeSet類,可以按照預設順序,也可以通過實作Java.util.Comparator 接口來自定義排序方式。

6 HashMap 和HashTable有什麼差別?

HashMap是線程不安全的,HashMap是一個接口,是Map的一個子接口,是将鍵映射到值得對象不允許鍵值重複，允許空鍵和空值；由于非線程安全,HashMap的效率要較HashTable的效率高一些.

HashTable是線程安全的一個集合,不允許null值作為一個key值或者Value值;

HashTable是sychronize,多個線程通路時不需要自己為它的方法實作同步，而HashMap在被多個線程通路的時候需要自己為它的方法實作同步;

7. Java 中ArrayList和Linkedlist差別?

ArrayList和Vector使用了數組的實作，可以認為ArrayList或者Vector封裝了對内部數組的操作,比如向數組中添加，删除，插入新的元素或者資料的擴充和重定向。LinkedList使用了循環雙向連結清單資料結構。與基于數組的ArrayList相比,這是兩種截然不同的實作技術，這也決定了它們将适用于完全不同的工作場景。

LinkedList連結清單由一系清單項連接配接而成。一個表項總是包含3個部分:元素内容,前驅表和後驅表,如圖所示:

在下圖展示了一個包含3個元素的LinkedList的各個表項間的連接配接關系。在JDK的實作中，無論LikedList是否為空,連結清單内部都有一個header表項,它既表示連結清單的開始,也表示連結清單的結尾。表項header的後驅表項便是連結清單中第一個元素，表項header的前驅表項便是連結清單中最後一個元素。

8. Map中的key和value可以為null麼?

HashMap對象的key. value 值均可為null.

HahTable對象的key. value 值均不可為null,

且兩者的的key值均不能重複,若添加key相同的鍵值對,後面的value會自動覆寫前面的value,但不會報錯。

測試代碼如下:

public class Test {
    public static void main (String[] args) {
  Map<String, String> map = new HashMap<String,String>();// HashMap對象
  Map<String, String> tableMap = new Hashtable<String, String>(); //HashTable對象
  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");
  }
    }
}      

運作結果: