java面試題-集合類_ZenDei技術網路在線

準備年後要跳槽，所以最近一直再看面試題，並且把收集到的面試題整理了以下發到博客上，希望對大家有所幫助。首先是集合類的面試題 1. HashMap 排序題，上機題。已知一個 HashMap<Integer，User>集合， User 有 name（String）和 age（int）屬性。請寫一個方 ...

準備年後要跳槽，所以最近一直再看面試題，並且把收集到的面試題整理了以下發到博客上，希望對大家有所幫助。

首先是集合類的面試題

1. HashMap 排序題，上機題。

已知一個 HashMap<Integer，User>集合， User 有 name（String）和 age（int）屬性。請寫一個方法實現對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 = sortHashMap(users);
System.out.println(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 進行排序，排序規則使用匿名內部類來實現
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();
}
});
 //創建一個新的有序的 HashMap 子類的集合
LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>();
 //將 List 中的數據存儲在 LinkedHashMap 中
for(Entry<Integer, User> entry : list){
linkedHashMap.put(entry.getKey(), entry.getValue());
}
 //返回結果
 return linkedHashMap;
 }
}

2. 集合的安全性問題

請問 ArrayList、HashSet、HashMap 是線程安全的嗎？如果不是我想要線程安全的集合怎麼辦？

我們都看過上面那些集合的源碼（如果沒有那就看看吧），每個方法都沒有加鎖，顯然都是線程不安全的。話又說過來如果他們安全了也就沒第二問了。

在集合中 Vector 和 HashTable 倒是線程安全的。你打開源碼會發現其實就是把各自核心方法添加上了synchronized 關鍵字。

Collections 工具類提供了相關的 API，可以讓上面那 3 個不安全的集合變為安全的。

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

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

3. 併發集合和普通集合如何區別？

併發集合常見的有 ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque 等。併發集合位於 java.util.concurrent 包下，是 jdk1.5 之後才有的，主要作者是 Doug Lea

（http://baike.baidu.com/view/3141057.htm）完成的。

在 java 中有普通集合、同步（線程安全）的集合、併發集合。普通集合通常性能最高，但是不保證多線程的安全性和併發的可靠性。線程安全集合僅僅是給集合添加了 synchronized 同步鎖，嚴重犧牲了性能，而且對併發的效率就更低了，併發集合則通過複雜的策略不僅保證了多線程的安全又提高的併發時的效率。

參考閱讀：

ConcurrentHashMap 是線程安全的 HashMap 的實現，預設構造同樣有 initialCapacity 和 loadFactor 屬性，不過還多了一個 concurrencyLevel 屬性，三屬性預設值分別為 16、0.75 及 16。其內部使用鎖分段技術，維持這鎖Segment 的數組，在 Segment 數組中又存放著 Entity[]數組，內部 hash 演算法將數據較均勻分佈在不同鎖中。

put 操作：並沒有在此方法上加上 synchronized，首先對 key.hashcode 進行 hash 操作，得到 key 的 hash 值。hash操作的演算法和map也不同，根據此hash值計算並獲取其對應的數組中的Segment對象(繼承自ReentrantLock)，接著調用此 Segment 對象的 put 方法來完成當前操作。

ConcurrentHashMap 基於 concurrencyLevel 劃分出了多個 Segment 來對 key-value 進行存儲，從而避免每次 put 操作都得鎖住整個數組。在預設的情況下，最佳情況下可允許 16 個線程併發無阻塞的操作集合對象，儘可能地減少併發時的阻塞現象。

get(key)：首先對 key.hashCode 進行 hash 操作，基於其值找到對應的 Segment 對象，調用其 get 方法完成當前操作。而 Segment 的 get 操作首先通過 hash 值和對象數組大小減 1 的值進行按位與操作來獲取數組上對應位置的HashEntry。在這個步驟中，可能會因為對象數組大小的改變，以及數組上對應位置的 HashEntry 產生不一致性，那麼 ConcurrentHashMap 是如何保證的？

對象數組大小的改變只有在 put 操作時有可能發生，由於 HashEntry 對象數組對應的變數是 volatile 類型的，因此可以保證如 HashEntry 對象數組大小發生改變，讀操作可看到最新的對象數組大小。

在獲取到了 HashEntry 對象後，怎麼能保證它及其 next 屬性構成的鏈表上的對象不會改變呢？這點ConcurrentHashMap 採用了一個簡單的方式，即 HashEntry 對象中的 hash、key、next 屬性都是 final 的，這也就意味著沒辦法插入一個HashEntry對象到基於next屬性構成的鏈表中間或末尾。這樣就可以保證當獲取到HashEntry對象後，其基於 next 屬性構建的鏈表是不會發生變化的。

ConcurrentHashMap 預設情況下採用將數據分為 16 個段進行存儲，並且 16 個段分別持有各自不同的鎖Segment，鎖僅用於 put 和 remove 等改變集合對象的操作，基於 volatile 及 HashEntry 鏈表的不變性實現了讀取的不加鎖。這些方式使得 ConcurrentHashMap 能夠保持極好的併發支持，尤其是對於讀遠比插入和刪除頻繁的 Map而言，而它採用的這些方法也可謂是對於 Java 記憶體模型、併發機制深刻掌握的體現。

其實關於集合的面試題我收集了很多沒有辦法一次性全部發出來,只是挑選了這麼3道。最後推薦大家看看hashmap的源碼（1.8之後的）,作為集合最常問的面試題hashmap以及底層的數組、鏈表和紅黑樹都是必須要掌握的。所謂知其然才能知其所以然就是這個意思數據結構就是一個程式員內力的體現。