文章目錄
- 一、Map 接口
- 1、HashMap 和 Hashtable 的差別
- 2、HashMap 和 HashSet 差別
- 3、HashMap 和 TreeMap 差別
- 4、HashSet 如何檢查重複
- 5、HashMap 的底層實作
- 5.1 JDK1.8 之前
- 5.2 JDK1.8 之後
- 6、HashMap 的長度為什麼是 2 的幂次方
- 7、HashMap 多線程操作導緻死循環問題
- 8、HashMap 有哪幾種常見的周遊方式?
- 9、ConcurrentHashMap 和 Hashtable 的差別
- 10、ConcurrentHashMap 線程安全的具體實作方式/底層具體實作
- JDK1.7（上面有示意圖）
- JDK1.8 （上面有示意圖）
- 二、Collections 工具類
- 1、排序操作
- 2、查找,替換操作
- 3、同步控制
- 總結
一、Map 接口
1、HashMap 和 Hashtable 的差別
- 線程是否安全：
HashMap
Hashtable
Hashtable
synchronized
ConcurrentHashMap
- 效率：因為線程安全的問題，
HashMap
Hashtable
Hashtable
- 對 Null key 和 Null value 的支援：
HashMap
NullPointerException
-
初始容量大小和每次擴充容量大小的不同 ：
① 建立時如果不指定容量初始值，
Hashtable
HashMap
預設的初始化大小為 16。之後每次擴充，容量變為原來的 2 倍。
② 建立時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而
HashMap
HashMap
tableSizeFor()
HashMap
- 底層資料結構：JDK1.8 以後的
HashMap
HashMap
中帶有初始容量的構造函數：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} 下面這個方法保證了
HashMap
總是使用 2 的幂作為哈希表的大小。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
} 2、HashMap 和 HashSet 差別
如果你看過
HashSet
源碼的話就應該知道：
HashSet
底層就是基于
HashMap
實作的。（
HashSet
的源碼非常非常少，因為除了
clone()
、
writeObject()
、
readObject()
是
HashSet
自己不得不實作之外，其他方法都是直接調用
HashMap
中的方法。
| |
實作了 | 實作 |
| 存儲鍵值對 | 僅存儲對象 |
調用 | 調用 |
| |
3、HashMap 和 TreeMap 差別
TreeMap
和
HashMap
都繼承自
AbstractMap
，但是需要注意的是
TreeMap
它還實作了
NavigableMap
接口和
SortedMap
接口。
實作
NavigableMap
接口讓
TreeMap
有了對集合内元素的搜尋的能力。
實作
SortedMap
接口讓
TreeMap
有了對集合中的元素根據鍵排序的能力。預設是按 key 的升序排序，不過我們也可以指定排序的比較器。示例代碼如下：
/**
* @author shuang.kou
* @createTime 2020年06月15日 17:02:00
*/
public class Person {
private Integer age;
public Person(Integer age) {
this.age = age;
}
public Integer getAge() {
return age;
}
public static void main(String[] args) {
TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
@Override
public int compare(Person person1, Person person2) {
int num = person1.getAge() - person2.getAge();
return Integer.compare(num, 0);
}
});
treeMap.put(new Person(3), "person1");
treeMap.put(new Person(18), "person2");
treeMap.put(new Person(35), "person3");
treeMap.put(new Person(16), "person4");
treeMap.entrySet().stream().forEach(personStringEntry -> {
System.out.println(personStringEntry.getValue());
});
}
} 輸出:
person1
person4
person2
person3 可以看出，
TreeMap
中的元素已經是按照
Person
的 age 字段的升序來排列了。
上面，我們是通過傳入匿名内部類的方式實作的，你可以将代碼替換成 Lambda 表達式實作的方式：
TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
int num = person1.getAge() - person2.getAge();
return Integer.compare(num, 0);
}); 綜上，相比于
HashMap
來說
TreeMap
主要多了對集合中的元素根據鍵排序的能力以及對集合内元素的搜尋的能力。
4、HashSet 如何檢查重複
以下内容摘自我的 Java 啟蒙書《Head first java》第二版：
當你把對象加入
HashSet
時，
HashSet
會先計算對象的
hashcode
值來判斷對象加入的位置，同時也會與其他加入的對象的
hashcode
值作比較，如果沒有相符的
hashcode
，
HashSet
會假設對象沒有重複出現。但是如果發現有相同
hashcode
值的對象，這時會調用
equals()
方法來檢查
hashcode
相等的對象是否真的相同。如果兩者相同，
HashSet
就不會讓加入操作成功。
在openjdk8中，
HashSet
的
add()
方法隻是簡單的調用了
HashMap
的
put()
方法，并且判斷了一下傳回值以確定是否有重複元素。直接看一下
HashSet
中的源碼：
// Returns: true if this set did not already contain the specified element
// 傳回值：當set中沒有包含add的元素時傳回真
public boolean add(E e) {
return map.put(e, PRESENT)==null;
} 而在
HashMap
的
putVal()
方法中也能看到如下說明：
// Returns : previous value, or null if none
// 傳回值：如果插入位置沒有元素傳回null，否則傳回上一個元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
} 也就是說，在openjdk8中，實際上無論
HashSet
中是否已經存在了某元素，
HashSet
都會直接插入，隻是會在
add()
方法的傳回值處告訴我們插入前是否存在相同元素。
hashCode()
與
equals()
的相關規定：
- 如果兩個對象相等，則
hashcode
- 兩個對象相等,對兩個
equals()
- 兩個對象有相同的
hashcode
- 綜上，
equals()
hashCode()
-
hashCode()
hashCode()
==與 equals 的差別
- 對于基本類型來說，== 比較的是值是否相等；
- 對于引用類型來說，== 比較的是兩個引用是否指向同一個對象位址（兩者在記憶體中存放的位址（堆記憶體位址）是否指向同一個地方）；
- 對于引用類型（包括包裝類型）來說，equals 如果沒有被重寫，對比它們的位址是否相等；如果 equals()方法被重寫（例如 String），則比較的是位址裡的内容。
5、HashMap 的底層實作
5.1 JDK1.8 之前
JDK1.8 之前
HashMap
底層是 數組和連結清單 結合在一起使用也就是 連結清單散列。HashMap 通過 key 的 hashCode 經過擾動函數處理過後得到 hash 值，然後通過 (n - 1) & hash 判斷目前元素存放的位置（這裡的 n 指的是數組的長度），如果目前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆寫，不相同就通過拉鍊法解決沖突。
所謂擾動函數指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動函數是為了防止一些實作比較差的 hashCode() 方法 換句話說使用擾動函數之後可以減少碰撞。
JDK 1.8 HashMap 的 hash 方法源碼:
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加簡化，但是原理不變。
static final int hash(Object key) {
int h;
// key.hashCode()：傳回散列值也就是hashcode
// ^ ：按位異或
// >>>:無符号右移，忽略符号位，空位都以0補齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 對比一下 JDK1.7 的 HashMap 的 hash 方法源碼.
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
} 相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次。
所謂 “拉鍊法” 就是：将連結清單和數組相結合。也就是說建立一個連結清單數組，數組中每一格就是一個連結清單。若遇到哈希沖突，則将沖突的值加到連結清單中即可。
5.2 JDK1.8 之後
相比于之前的版本， JDK1.8 之後在解決哈希沖突時有了較大的變化，當連結清單長度大于門檻值（預設為 8）（将連結清單轉換成紅黑樹前會判斷，如果目前數組的長度小于 64，那麼會選擇先進行數組擴容，而不是轉換為紅黑樹）時，将連結清單轉化為紅黑樹，以減少搜尋時間。
TreeMap、TreeSet 以及 JDK1.8 之後的 HashMap 底層都用到了紅黑樹。紅黑樹就是為了解決二叉查找樹的缺陷，因為二叉查找樹在某些情況下會退化成一個線性結構。
6、HashMap 的長度為什麼是 2 的幂次方
為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把資料配置設定均勻。我們上面也講到了過了，Hash 值的範圍值-2147483648 到 2147483647，前後加起來大概 40 億的映射空間，隻要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。但問題是一個 40 億長度的數組，記憶體是放不下的。是以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的餘數才能用來要存放的位置也就是對應的數組下标。這個數組下标的計算方法是“
(n - 1) & hash
”。（n 代表數組長度）。這也就解釋了 HashMap 的長度為什麼是 2 的幂次方。
這個算法應該如何設計呢？
我們首先可能會想到采用%取餘的操作來實作。但是，重點來了：“取餘(%)操作中如果除數是 2 的幂次則等價于與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二進制位操作 &，相對于%能夠提高運算效率，這就解釋了 HashMap 的長度為什麼是 2 的幂次方。
7、HashMap 多線程操作導緻死循環問題
主要原因在于并發下的 Rehash 會造成元素之間會形成一個循環連結清單。不過，jdk 1.8 後解決了這個問題，但是還是不建議在多線程下使用 HashMap,因為多線程下使用 HashMap 還是會存在其他問題比如資料丢失。并發環境下推薦使用 ConcurrentHashMap 。
詳情請檢視：https://coolshell.cn/articles/9606.html
8、HashMap 有哪幾種常見的周遊方式?
HashMap 的 7 種周遊方式與性能分析！
9、ConcurrentHashMap 和 Hashtable 的差別
ConcurrentHashMap
和
Hashtable
的差別主要展現在實作線程安全的方式上不同。
- 底層資料結構：JDK1.7 的
ConcurrentHashMap
HashMap1.8
Hashtable
HashMap
- 實作線程安全的方式（重要）：①在 JDK1.7 的時候，
ConcurrentHashMap
Segment
Segment
Node
synchronized
synchronized
HashMap
Segment
Hashtable
synchronized
兩者的對比圖：
Hashtable:
JDK1.7 的 ConcurrentHashMap：
JDK1.8 的 ConcurrentHashMap：
JDK1.8 的
ConcurrentHashMap
不再是 Segment 數組 + HashEntry 數組 + 連結清單，而是 Node 數組 + 連結清單 / 紅黑樹。不過，Node 隻能用于連結清單的情況，紅黑樹的情況需要使用
TreeNode
。當沖突連結清單達到一定長度時，連結清單會轉換成紅黑樹。
10、ConcurrentHashMap 線程安全的具體實作方式/底層具體實作
JDK1.7（上面有示意圖）
首先将資料分為一段一段的存儲，然後給每一段資料配一把鎖，當一個線程占用鎖通路其中一個段資料時，其他段的資料也能被其他線程通路。
ConcurrentHashMap
是由
Segment
數組結構和
HashEntry
數組結構組成。
Segment 繼承了
ReentrantLock
,是以
Segment
是一種可重入鎖，扮演鎖的角色。
HashEntry
用于存儲鍵值對資料。
static class Segment<K,V> extends ReentrantLock implements Serializable {
} 一個
ConcurrentHashMap
裡包含一個
Segment
數組。
Segment
的結構和
HashMap
類似，是一種數組和連結清單結構，一個
Segment
包含一個
HashEntry
數組，每個
HashEntry
是一個連結清單結構的元素，每個
Segment
守護着一個
HashEntry
數組裡的元素，當對
HashEntry
數組的資料進行修改時，必須首先獲得對應的
Segment
的鎖。
JDK1.8 （上面有示意圖）
ConcurrentHashMap
取消了
Segment
分段鎖，采用 CAS 和
synchronized
來保證并發安全。資料結構跟 HashMap1.8 的結構類似，數組+連結清單/紅黑二叉樹。Java 8 在連結清單長度超過一定門檻值（8）時将連結清單（尋址時間複雜度為 O(N)）轉換為紅黑樹（尋址時間複雜度為 O(log(N))）
synchronized
隻鎖定目前連結清單或紅黑二叉樹的首節點，這樣隻要 hash 不沖突，就不會産生并發，效率又提升 N 倍。
二、Collections 工具類
Collections 工具類常用方法:
- 排序
- 查找,替換操作
- 同步控制(不推薦，需要線程安全的集合類型時請考慮使用 JUC 包下的并發集合)
1、排序操作
void reverse(List list)//反轉
void shuffle(List list)//随機排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序邏輯
void swap(List list, int i , int j)//交換兩個索引位置的元素
void rotate(List list, int distance)//旋轉。當distance為正數時，将list後distance個元素整體移到前面。當distance為負數時，将 list的前distance個元素整體移到後面 2、查找,替換操作
int binarySearch(List list, Object key)//對List進行二分查找，傳回索引，注意List必須是有序的
int max(Collection coll)//根據元素的自然順序，傳回最大的元素。 類比int min(Collection coll)
int max(Collection coll, Comparator c)//根據定制排序，傳回最大元素，排序規則由Comparatator類控制。類比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//統計元素出現次數
int indexOfSubList(List list, List target)//統計target在list中第一次出現的索引，找不到則傳回-1，類比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替換舊元素 3、同步控制
Collections
提供了多個
synchronizedXxx()
方法·，該方法可以将指定集合包裝成線程同步的集合，進而解決多線程并發通路集合時的線程安全問題。
我們知道
HashSet
，
TreeSet
，
ArrayList
,
LinkedList
,
HashMap
,
TreeMap
都是線程不安全的。
Collections
提供了多個靜态方法可以把他們包裝成線程同步的集合。
最好不要用下面這些方法，效率非常低，需要線程安全的集合類型時請考慮使用 JUC 包下的并發集合。
方法如下：
synchronizedCollection(Collection<T> c) //傳回指定 collection 支援的同步（線程安全的）collection。
synchronizedList(List<T> list)//傳回指定清單支援的同步（線程安全的）List。
synchronizedMap(Map<K,V> m) //傳回由指定映射支援的同步（線程安全的）Map。
synchronizedSet(Set<T> s) //傳回指定 set 支援的同步（線程安全的）set。 總結
OK，今天關于 Java集合之Map集合、Collections工具類的面試題分享 就到這裡，希望本篇文章能夠幫助到大家，同時也希望大家看後能學有所獲！！！