思維導圖

1. HashMap排序題， 上機題

已知一個HashMap<Integer, User> 集合，User 有name (String) 和age (int)屬性,。請寫一個方法實現(xiàn)對HashMap的排序功能，該方法接收HashMap <Integer, User>為形參，返回類型為HashMap
<Integer, User>,要求對HashMap中的User的age倒序進行排序,。排序時key=value鍵值對不得拆散,。.

注意: 要做出這道題必須對集合的體系結構非常的熟悉HashMap 本身就是不可排序的，但是該道題偏偏讓給HashMap排序,那我們就得想在API中有沒有這樣的Map結構是有序的，
LinkedHashMap, 對的，就是它，它是Map結構,也是鏈表結構,有序的，更可喜的是他是HashMap的子類,我們返回LinkedHashMap <Integer,User>即可，還符合面向接口(父類編程的思想),。但凡是對集合的操作,我們應該保持一個原則就是能用JDK中的API就有JDK中的API,比如排序算法我們不應該去用冒泡或者選擇，而是首先想到用Collections集合工具類,。

public 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 = sortHas hMap (users) ;
System. out . print ln (sortHashMap) ;
/**
*控制臺輸出內容
* {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的鍵值對集合
Set<Entry<Integer, User>> entrySet = map.entrySet() ;
// 將set 集合轉為List集合，為什么，為了使用工具類的排序方法
List<Entry<Integer, User>> list = new ArrayList<Entry<Integer, User>> (entrySet);
//使用Collections集合工具類對list進行排序，排序規(guī)則使用匿名內部類來實現(xiàn)
Collections.sort (list, new Comparator<Entry<Integer, User>>() {
@Override
public int compare (Entry<Integer, User> o1, Entry<Integer, User> o2) {
//按照要求根據User的age的倒序進行排
return o2.getValue().getAge()-o1.getValue().getAge() ;
}) ;
//創(chuàng)建-一個新的有序的HashMap子類的集合
Linke dHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User> () ;
//將List中的數(shù)據存儲在LinkedHashMap中
for (Entry<Integer, User> entry : list) {
linkedHashMap.put (entry.getKey(), entry.getValue()) ;
}
//返回結果
return linkedHashMap;
}
}

2.集合的安全性問題

請問ArrayList,、HashSet、 HashMap 是線程安全的嗎?如果不是我想要線程安全的集合怎么辦?
　
　我們都看過上面那些集合的源碼(如果沒有那就看看吧) ,每個方法都沒有加鎖，顯然都是線程不安全的,。話又說過來如果他們安全了也就沒第二問了,。在集合中Vector和HashTable 倒是線程安全的。你打開源碼會發(fā)現(xiàn)其實就是把各自核心方法添加上了synchronized關鍵字,。Collections工具類提供了相關的API,可以讓上面那3個不安全的集合變?yōu)榘踩摹?/p>

//Collections. synch ronizedCollection (c )
//Collections. synch ronizedList (list)
//Collec tions. synch roni ze dMap (m)
//Collections. synchronizedSet (s)

上面幾個函數(shù)都有對應的返回值類型，傳入什么類型返回什么類型,。打開源碼其實實現(xiàn)原理非常簡單，就是將集合的核心方法添加了synchronized關鍵字。

3. ArrayList 內部用什么實現(xiàn)的?

(回答這樣的問題，不要只回答個皮毛，可以再介紹一下 ArrayList內部是如何實現(xiàn)數(shù)組的增加和刪除的,因為數(shù)組在創(chuàng)建的時候長度是固定的，那么就有個問題我們往ArrayList 中不斷的添加對象，它是如何管理這些數(shù)組呢? )
　ArrayList內部是用Object[]實現(xiàn)的,。接下來我們分別分析ArrayList的構造,、add、remove,、 clear 方法的實現(xiàn)原理,。
　
一、構造函數(shù)
1)空參構造

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

array是一個Object[]類型,。當我們new -個空參構造時系統(tǒng)調用了EmptyArray.OBJECT 屬性, EmptyArray僅
僅是一個系統(tǒng)的類庫,該類源碼如下:

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];
}

也就是說當我們new -個空參ArrayList 的時候，系統(tǒng)內部使用了-個new Object[0]數(shù)組,。

2)帶參構造1

/**
* 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]);
}

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

3)帶參構造2

/**
* 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 Nul1PointerException("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;
}

如果調用構造函數(shù)的時候傳入了一個Collection的子類,那么先判斷該集合是否為null,為null則拋出空指針異常。如果不是則將該集合轉換為數(shù)組a,然后將該數(shù)組賦值為成員變量array,將該數(shù)組的長度作為成員變量size.這里面它先判斷a.getClass是否等于Object[].class,toArray方法是Collection接口義的因此其所有的子類都有這樣的方法，list集合的toArray和Set集合的toArray
返回的都是Object[]數(shù)組。
　　其實在看Java源碼的時候，作者的很多意圖都很費人心思，我能知道他的目標是啥，但是不知道他為何這樣寫,。比如對于ArrayList，array 是他的成員變量,但是每次在方法中使用該成員變量的時候作者都會重新在方法中開辟一個局部變量,然后給局部變量賦值為array,然后再使用，有人可能說這是為了防止并發(fā)修改array,畢竟array是成員變量,大家都可以使用因此需要將array變?yōu)榫植孔兞?然后再使用,這樣的說法并不是都成立的,也許有時候就是老外們寫代碼的一個習慣而已,。
　　
二、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是否等于數(shù)組的長度(如果集合的長度已經等于數(shù)組的長度了,說明數(shù)組已經滿了，該重新分配新數(shù)組了)，重新分配數(shù)組的時候需要計算新分配內存的空間大小，如果當前的長度小于MIN_CAPACITY INCREMENT/2 (這個常量值是12,除以2就是6,也就是如果當前集合長度小于6)則分配12個長度，如果集合長度大于6則分配當前長度s的一半長度,。這里面用到了三元運算符和位運算，s >> 1,意思就是將s往右移1位,相當于s=s/2,只不過位運算是效率最高的運算。
3,、將新添加的object對象作為數(shù)組的a[s]個元素,。
4、修改集合長度size為s+1,。
5,、modCotun+ +,該變量是父類中聲明的，用于記錄集合修改的次數(shù),記錄集合修改的次數(shù)是為了防止在用迭代器迭代集合時避免并發(fā)修改異常，或者說用于判斷是否出現(xiàn)并發(fā)修改異常的。
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、獲取數(shù)組中腳標為index的對象result,該對象作為方法的返回值
4,、調用System的arraycopy函數(shù)，拷貝原理如下圖所示,。

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

假設index=2，那么要刪除的對象如圖打叉部分，我們只需要將該數(shù)組后面藍色區(qū)域整體往前移動一位位置即可。上面的代碼完成就是這個工作,。
5.接下來就是很重要的一個工作,因為刪除了一個元素，而且集合整體向前移動了一位,因此需要將集合最后一個元索設置為null,否則就可能內存泄露。
6,、重新給成員變量array 和size賦值,。
7.記錄修改次數(shù)。
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底層結構是數(shù)組底層查詢快,增刪慢,。
LinkedList底層結構是鏈表型的,增刪快,查詢慢,。
voctor底層結構是數(shù)組 線程安全的,增刪慢查詢慢。

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

5.1結構特點
List和Set是存儲單列數(shù)據的集合，
Map是存儲鍵和值這樣的雙列數(shù)據的集合;

List 中存儲的數(shù)據是有順序,并且允許重復; Map中存儲的數(shù)據是沒有順序的，其鍵是不能重復的，它的值是可以有重復的，Set 中存儲的數(shù)據是無序的，且不允許有重復,但元素在集合中的位置由元素的hashcode決定,位置是固定的(Set集合根據hashcode來
進行數(shù)據的存儲,所以位置是固定的,但是位置不是用戶可以控制的,所以對于用戶來說set中的元素還是無序的) ;

5.2實現(xiàn)類
List接口有三個實現(xiàn)類(LinkedList:基于鏈表實現(xiàn),鏈表內存是散亂的,每一個元素存儲本身內存地址的同時還存儲下一個元素的地址,。鏈表增刪快,查找慢; ArrayList: 基于數(shù)組實現(xiàn)，非線程安全的,效率高，便于索引，但不便于插入刪除; Vector:基于數(shù)組實現(xiàn)，線程安全的，效率低),。
Map接口有三個實現(xiàn)類(HashMap: 基于hash表的Map接口實現(xiàn),非線程安全,高效，支持null值和null鍵; HashTable: 線程安全，低效,不支持null值和null鍵; LinkedHashMap: 是HashMap的一個子類,保存了記錄的插入順序; SortMap 接口: TreeMap, 能夠把它保存的記錄根據鍵排序,默認是鍵值的升序排序)。
Set接口有兩個實現(xiàn)類(HashSet: 底層是由HashMap實現(xiàn)，不允許集合中有重復的值，使用該方式時需要重寫equals0和hashCode0方法; LinkedHashSet: 繼承與HashSet,同時又基于LinkedHashMap來進行實現(xiàn)，底層使用的是LinkedHashMp),。

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

6 HashMap 和HashTable有什么區(qū)別?

HashMap是線程不安全的,HashMap是一個接口,是Map的一個子接口,是將鍵映射到值得對象不允許鍵值重復，允許空鍵和空值；由于非線程安全,HashMap的效率要較HashTable的效率高一些.
HashTable是線程安全的一個集合,不允許null值作為一個key值或者Value值;
HashTable是sychronize,多個線程訪問時不需要自己為它的方法實現(xiàn)同步，而HashMap在被多個線程訪問的時候需要自己為它的方法實現(xiàn)同步;

7. Java 中ArrayList和Linkedlist區(qū)別?

ArrayList和Vector使用了數(shù)組的實現(xiàn)，可以認為ArrayList或者Vector封裝了對內部數(shù)組的操作,比如向數(shù)組中添加，刪除，插入新的元素或者數(shù)據的擴展和重定向。LinkedList使用了循環(huán)雙向鏈表數(shù)據結構,。與基于數(shù)組的ArrayList相比,這是兩種截然不同的實現(xiàn)技術，這也決定了它們將適用于完全不同的工作場景,。
LinkedList鏈表由一系列表項連接而成。一個表項總是包含3個部分:元素內容,前驅表和后驅表,如圖所示:

在下圖展示了一個包含3個元素的LinkedList的各個表項間的連接關系,。在JDK的實現(xiàn)中，無論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");
}
}
}

運行結果: