1. ConcurrentHashMap 和 HashTable 有哪些區別
- 原理
- HashTable:它繼承自
Dictionary
類,是 Java 早期提供的線程安全哈希表。其線程安全的實現方式是對每個方法都使用synchronized
關鍵字進行同步。例如,在調用put
、get
等方法時,整個 HashTable 會被鎖定,其他線程必須等待當前線程釋放鎖后才能訪問該方法。
java
import java.util.Hashtable;public class HashTableExample {public static void main(String[] args) {Hashtable<String, Integer> hashtable = new Hashtable<>();// 線程安全的 put 操作hashtable.put("one", 1); }
}
- ConcurrentHashMap:
- Java 7 版本:采用分段鎖機制,將整個哈希表分成多個
Segment
(段),每個Segment
相當于一個小的 HashTable,每個Segment
都有自己的鎖。不同的Segment
可以被不同的線程同時訪問,只要訪問的不是同一個Segment
,就不會產生鎖競爭,從而提高了并發性能。 - Java 8 版本:摒棄了分段鎖,采用 CAS(Compare - And - Swap)和
synchronized
來保證并發操作的安全性。它使用數組 + 鏈表 + 紅黑樹的數據結構,在進行插入、刪除和查找操作時,首先通過哈希值找到對應的桶,然后對桶首節點加鎖,鎖的粒度更小,性能更高。
- Java 7 版本:采用分段鎖機制,將整個哈希表分成多個
java
import java.util.concurrent.ConcurrentHashMap;public class ConcurrentHashMapExample {public static void main(String[] args) {ConcurrentHashMap<String, Integer> concurrentHashMap = new ConcurrentHashMap<>();// 并發安全的 put 操作concurrentHashMap.put("one", 1); }
}
- 要點
- 線程安全實現方式:HashTable 是全量同步,所有方法都加鎖,同一時間只能有一個線程訪問;ConcurrentHashMap 在 Java 7 中是分段同步,Java 8 中是細粒度同步,允許多個線程同時訪問不同部分。
- 性能:在高并發場景下,ConcurrentHashMap 的性能遠遠優于 HashTable,因為 HashTable 的鎖粒度太大,容易造成線程阻塞。
- 空值處理:HashTable 不允許鍵或值為
null
,而 ConcurrentHashMap 同樣不允許鍵為null
,如果插入null
鍵會拋出NullPointerException
。
- 應用
- 可以深入了解 CAS 算法的底層原理,它是一種無鎖算法,通過比較內存中的值和預期值,如果相等則更新,否則重試。
- 研究 Java 8 中 ConcurrentHashMap 在擴容、紅黑樹轉換等方面的優化策略。
2. 什么是 LinkedHashMap
- 原理
LinkedHashMap
繼承自 HashMap
,它在 HashMap
的基礎上維護了一個雙向鏈表。這個雙向鏈表定義了元素的迭代順序,默認情況下是插入順序,即元素按照插入的先后順序進行迭代;也可以通過構造函數將其設置為訪問順序,即最近訪問的元素會被移動到鏈表尾部。
java
import java.util.LinkedHashMap;
import java.util.Map;public class LinkedHashMapExample {public static void main(String[] args) {// 創建一個按照插入順序排序的 LinkedHashMapLinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();linkedHashMap.put("one", 1);linkedHashMap.put("two", 2);linkedHashMap.put("three", 3);for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}}
}
- 要點
- 繼承關系:繼承自
HashMap
,具備HashMap
的基本特性,如快速的查找、插入和刪除操作。 - 雙向鏈表:通過雙向鏈表維護元素順序,使得元素可以按照插入順序或訪問順序進行迭代。
- 訪問順序:如果設置為訪問順序,每次訪問元素時,該元素會被移動到鏈表尾部,這在實現 LRU 緩存時非常有用。
- 應用
- 實現一個簡單的 LRU 緩存,使用
LinkedHashMap
來存儲緩存數據,當緩存滿時,自動移除最久未使用的元素。
java
import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {private final int capacity;public LRUCache(int capacity) {// 第三個參數設置為 true 表示按照訪問順序排序super(capacity, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}};this.capacity = capacity;}public static void main(String[] args) {LRUCache<Integer, Integer> cache = new LRUCache<>(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1)); // 返回 1cache.put(3, 3); // 該操作會使得關鍵字 2 作廢System.out.println(cache.get(2)); // 返回 -1 (未找到)cache.put(4, 4); // 該操作會使得關鍵字 1 作廢System.out.println(cache.get(1)); // 返回 -1 (未找到)System.out.println(cache.get(3)); // 返回 3System.out.println(cache.get(4)); // 返回 4}
}
3. LinkedHashMap 與 HashMap 有哪些區別
- 原理
- HashMap:基于哈希表實現,通過哈希函數將鍵映射到桶中,每個桶可以存儲一個鏈表或紅黑樹(當鏈表長度超過 8 且數組長度大于 64 時,鏈表會轉換為紅黑樹)。它不保證元素的順序,每次迭代的順序可能不同。
java
import java.util.HashMap;
import java.util.Map;public class HashMapExample {public static void main(String[] args) {HashMap<String, Integer> hashMap = new HashMap<>();hashMap.put("one", 1);hashMap.put("two", 2);hashMap.put("three", 3);for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}}
}
- LinkedHashMap:除了使用哈希表存儲元素外,還使用雙向鏈表維護元素的插入順序或訪問順序。在插入元素時,不僅會將元素存儲到哈希表中,還會將其添加到雙向鏈表的尾部;在訪問元素時,如果是訪問順序,會將該元素移動到鏈表尾部。
- 要點
- 順序性:HashMap 不保證元素的順序,而 LinkedHashMap 可以保證插入順序或訪問順序。
- 性能:由于需要維護雙向鏈表,LinkedHashMap 的插入和刪除操作相對 HashMap 會稍慢一些,但在迭代元素時,LinkedHashMap 可以按照順序快速迭代。
- 內存占用:LinkedHashMap 由于需要額外維護雙向鏈表,會比 HashMap 占用更多的內存空間。
- 應用
- 對比它們在不同場景下的性能差異,例如在大數據量插入和頻繁迭代的場景下,測試 LinkedHashMap 和 HashMap 的性能表現。
- 分析在使用 LinkedHashMap 時,不同的訪問順序設置對性能和內存的影響。
4. 什么是 HashSet
- 原理
HashSet
基于 HashMap
實現,它不允許存儲重復的元素。HashSet
內部使用一個 HashMap
來存儲元素,將元素作為鍵,值統一為一個靜態常量對象 PRESENT
。當向 HashSet
中添加元素時,實際上是將該元素作為鍵插入到內部的 HashMap
中,值為 PRESENT
。
java
import java.util.HashSet;public class HashSetExample {public static void main(String[] args) {HashSet<String> hashSet = new HashSet<>();hashSet.add("one");hashSet.add("two");hashSet.add("three");for (String element : hashSet) {System.out.println(element);}}
}
- 要點
- 唯一性:不允許存儲重復元素,通過
HashMap
的鍵的唯一性來保證。 - 實現基礎:基于
HashMap
實現,利用HashMap
的哈希算法和存儲結構來實現快速的查找和插入操作。 - 無序性:不保證元素的順序,每次迭代的順序可能不同。
- 應用
- 了解
HashSet
在去重場景中的應用,例如對一個包含重復元素的列表進行去重操作。
java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;public class DuplicateRemoval {public static void main(String[] args) {List<String> listWithDuplicates = new ArrayList<>();listWithDuplicates.add("one");listWithDuplicates.add("two");listWithDuplicates.add("one");HashSet<String> set = new HashSet<>(listWithDuplicates);List<String> listWithoutDuplicates = new ArrayList<>(set);for (String element : listWithoutDuplicates) {System.out.println(element);}}
}
5. HashMap 與 HashSet 有什么區別
- 原理
- HashMap:存儲鍵值對,通過鍵的哈希值來確定存儲位置,允許鍵和值為
null
。它使用哈希表來存儲元素,當發生哈希沖突時,會通過鏈表或紅黑樹來解決。
java
import java.util.HashMap;
import java.util.Map;public class HashMapExample {public static void main(String[] args) {HashMap<String, Integer> hashMap = new HashMap<>();hashMap.put("one", 1);hashMap.put("two", 2);System.out.println(hashMap.get("one"));}
}
- HashSet:只存儲元素,基于
HashMap
實現,元素作為鍵存儲,值為一個固定的常量對象。它不允許存儲重復元素,通過HashMap
的鍵的唯一性來保證。
java
import java.util.HashSet;public class HashSetExample {public static void main(String[] args) {HashSet<String> hashSet = new HashSet<>();hashSet.add("one");hashSet.add("two");System.out.println(hashSet.contains("one"));}
}
- 要點
- 存儲內容:HashMap 存儲鍵值對,HashSet 只存儲元素。
- 用途:HashMap 用于根據鍵查找值,HashSet 用于判斷元素是否存在。
- 空值處理:HashMap 允許鍵和值為
null
,而 HashSet 允許存儲一個null
元素。
- 應用
- 分析在不同業務場景下,如何選擇使用 HashMap 或 HashSet,例如在存儲用戶信息(鍵為用戶 ID,值為用戶對象)時使用 HashMap,在存儲不重復的單詞列表時使用 HashSet。
- 研究
HashMap
和HashSet
在處理哈希沖突時的性能差異。
6. 什么是 Collections.sort,內部原理
- 原理
Collections.sort
是 Java 集合框架中用于對列表進行排序的靜態方法。它有兩種重載形式:
- 對于實現了
RandomAccess
接口的列表(如ArrayList
),使用雙軸快速排序(Dual - pivot Quicksort)。雙軸快速排序是一種改進的快速排序算法,它選擇兩個軸元素,將數組分為三個部分,從而減少了比較和交換的次數,平均時間復雜度為 O(nlogn)。 - 對于未實現
RandomAccess
接口的列表(如LinkedList
),先將列表元素復制到一個數組中,對數組進行排序,再將排序后的元素復制回列表。
java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class CollectionsSortExample {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(3);list.add(1);list.add(2);Collections.sort(list);for (Integer num : list) {System.out.println(num);}}
}
- 要點
- 排序算法:根據列表類型選擇不同的排序算法,對于隨機訪問列表使用雙軸快速排序,對于非隨機訪問列表使用先復制到數組再排序的方式。
- 時間復雜度:平均為 O(nlogn),在最壞情況下為 O(n2),但雙軸快速排序的最壞情況很少出現。
- 穩定性:
Collections.sort
是不穩定的排序算法,即相等元素的相對順序可能會改變。
- 應用
- 了解雙軸快速排序的具體實現細節,以及它與傳統快速排序的區別和優勢。
- 研究其他排序算法(如歸并排序、堆排序)的特點,并與雙軸快速排序進行性能比較。
7. 什么是 hash 算法
- 原理
哈希算法是一種將任意長度的輸入數據轉換為固定長度的輸出數據的算法,輸出數據通常稱為哈希值或散列值。哈希算法具有以下特點:
- 確定性:相同的輸入始終產生相同的輸出。
- 高效性:計算哈希值的速度快,通常在常數時間內完成。
- 均勻性:輸出值在哈希空間中均勻分布,盡量減少哈希沖突的發生。
- 抗碰撞性:盡量避免不同的輸入產生相同的輸出,但在理論上,由于輸入空間無限大,輸出空間有限,哈希沖突是不可避免的。
- 要點
- 作用:用于數據的快速查找、存儲和驗證。例如,在哈希表中,通過哈希算法將鍵映射到桶中,實現快速的查找和插入操作;在文件驗證中,通過計算文件的哈希值來驗證文件的完整性。
- 特性:確定性、高效性、均勻性和抗碰撞性是哈希算法的重要特性。
- 應用場景:廣泛應用于密碼學、數據存儲、緩存等領域。
- 應用
- 了解常見的哈希算法(如 MD5、SHA - 1、SHA - 256)的原理和應用場景。例如,MD5 曾經廣泛用于文件校驗,但由于其存在安全漏洞,現在逐漸被棄用;SHA - 256 常用于區塊鏈等領域。
- 研究哈希碰撞的處理方法,如開放尋址法、鏈地址法等。
8. 什么是迭代器 Iterator 和 Enumeration
- 原理
- Iterator:是 Java 集合框架中用于遍歷集合元素的接口,它提供了
hasNext()
、next()
和remove()
方法。hasNext()
用于判斷集合中是否還有下一個元素,next()
用于返回下一個元素,remove()
用于刪除最后一次調用next()
方法返回的元素。Iterator
可以在遍歷過程中安全地刪除元素。
java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;public class IteratorExample {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("one");list.add("two");list.add("three");Iterator<String> iterator = list.iterator();while (iterator.hasNext()) {String element = iterator.next();if (element.equals("two")) {iterator.remove();}}for (String element : list) {System.out.println(element);}}
}
- Enumeration:是 Java 早期版本中用于遍歷集合元素的接口,它只提供了
hasMoreElements()
和nextElement()
方法。hasMoreElements()
用于判斷集合中是否還有更多元素,nextElement()
用于返回下一個元素。Enumeration
不支持在遍歷過程中刪除元素。
java
import java.util.Enumeration;
import java.util.Vector;public class EnumerationExample {public static void main(String[] args) {Vector<String> vector = new Vector<>();vector.add("one");vector.add("two");vector.add("three");Enumeration<String> enumeration = vector.elements();while (enumeration.hasMoreElements()) {String element = enumeration.nextElement();System.out.println(element);}}
}
- 要點
- 功能差異:Iterator 支持刪除元素,Enumeration 不支持。
- 使用場景:Iterator 是推薦的遍歷方式,適用于大多數集合類;Enumeration 主要用于舊代碼的兼容性,在新代碼中盡量避免使用。
- 線程安全:
Enumeration
是線程安全的,因為它沒有remove()
方法,不會改變集合的結構;而Iterator
在多線程環境下使用時需要注意線程安全問題。
- 應用
- 了解迭代器模式的原理和應用,它是一種行為設計模式,用于提供一種方法順序訪問一個聚合對象中的各個元素,而又不暴露該對象的內部表示。
- 研究
Iterator
的子類(如ListIterator
)的特點,ListIterator
是Iterator
的子接口,它可以雙向遍歷列表,并且支持在遍歷過程中添加、修改和刪除元素。
9. 什么是 LIST,ArrayList,LinkedList 和 Vector 的區別和實現原理
- 原理
- ArrayList:基于動態數組實現,它會自動擴容以容納更多元素。當元素數量超過數組容量時,會創建一個更大的數組,并將原數組元素復制到新數組中。默認初始容量為 10,每次擴容為原來的 1.5 倍。
java
import java.util.ArrayList;
import java.util.List;public class ArrayListExample {public static void main(String[] args) {List<String> arrayList = new ArrayList<>();arrayList.add("one");arrayList.add("two");System.out.println(arrayList.get(0));}
}
- LinkedList:基于雙向鏈表實現,每個節點包含數據和指向前一個節點和后一個節點的引用。插入和刪除操作只需要修改節點的引用,不需要移動大量元素,因此在插入和刪除操作頻繁的場景下性能較好。
java
import java.util.LinkedList;
import java.util.List;public class LinkedListExample {public static void main(String[] args) {List<String> linkedList = new LinkedList<>();linkedList.add("one");linkedList.add("two");System.out.println(linkedList.get(0));}
}
- Vector:也是基于動態數組實現,與
ArrayList
類似,但它是線程安全的,所有方法都使用synchronized
關鍵字進行同步。默認初始容量為 10,每次擴容為原來的 2 倍。
java
import java.util.Vector;
import java.util.List;public class VectorExample {public static void main(String[] args) {List<String> vector = new Vector<>();vector.add("one");vector.add("two");System.out.println(vector.get(0));}
}
- 要點
- 數據結構:ArrayList 和 Vector 是數組,支持隨機訪問,通過索引可以快速訪問元素;LinkedList 是鏈表,不支持隨機訪問,需要從頭節點或尾節點開始遍歷。
- 線程安全:Vector 是線程安全的,ArrayList 和 LinkedList 不是。在多線程環境下,如果需要線程安全的列表,可以使用 Vector 或使用
Collections.synchronizedList
方法將 ArrayList 轉換為線程安全的列表。 - 性能:ArrayList 和 Vector 隨機訪問速度快,插入和刪除操作在尾部以外的位置較慢;LinkedList 插入和刪除操作快,隨機訪問速度慢。
- 內存占用:ArrayList 和 Vector 由于是數組,會預先分配一定的內存空間,可能會造成內存浪費;LinkedList 每個節點需要額外的引用,會占用更多的內存空間。
應用
- 分析在不同場景下如何選擇使用 ArrayList、LinkedList 和 Vector,例如在需要頻繁隨機訪問元素時使用 ArrayList,在需要頻繁插入和刪除元素時使用 LinkedList,在多線程環境下使用 Vector。
- 研究 ArrayList 和 Vector 在擴容機制上的差異對性能的影響。
10. 什么是 volatile 和 synchronized,有什么區別
- 原理
- volatile:是一個關鍵字,用于修飾變量。它保證了變量的可見性,即當一個線程修改了被
volatile
修飾的變量的值,其他線程能夠立即看到最新的值。這是因為volatile
變量會直接從主內存中讀取和寫入,而不是從線程的本地緩存中讀取和寫入。但它不保證原子性,例如對volatile
變量進行自增操作不是原子操作。
java
public class VolatileExample {private static volatile int counter = 0;public static void main(String[] args) {Thread t1 = new Thread(() -> {for (int i = 0; i < 1000; i++) {counter++;}});Thread t2 = new Thread(() -> {for (int i = 0; i < 1000; i++) {counter++;}});t1.start();t2.start();try {t1.join();t2.join();} catch (InterruptedException e) {e.printStackTrace();}System.out.println(counter);}
}
- synchronized:是一個關鍵字,用于修飾方法或代碼塊。它可以保證在同一時間只有一個線程可以訪問被
synchronized
修飾的方法或代碼塊,從而保證了線程安全,既保證了可見性,也保證了原子性。當一個線程進入synchronized
方法或代碼塊時,會獲得對象的鎖,其他線程必須等待該線程釋放鎖后才能進入。
java
public class SynchronizedExample {private static int counter = 0;public static synchronized void increment() {counter++;}public static void main(String[] args) {Thread t1 = new Thread(() -> {for (int i = 0; i < 1000; i++) {increment();}});Thread t2 = new Thread(() -> {for (int i = 0; i < 1000; i++) {increment();}});t1.start();t2.start();try {t1.join();t2.join();} catch (InterruptedException e) {e.printStackTrace();}System.out.println(counter);}
}
- 要點
- 功能:volatile 保證可見性,synchronized 保證可見性和原子性。
- 使用場景:volatile 適用于一個變量被多個線程讀取,一個線程寫入的場景,例如狀態標志位;synchronized 適用于多個線程對共享資源進行讀寫操作的場景,例如多線程對計數器進行自增操作。
- 性能:volatile 的性能開銷較小,因為它不會阻塞線程;synchronized 的性能開銷較大,因為它會導致線程阻塞。
- 應用
- 了解 Java 內存模型(JMM)中關于可見性和原子性的原理,以及
volatile
和synchronized
在 JMM 中的實現機制。 - 研究
volatile
和synchronized
在不同并發場景下的優化使用,例如使用volatile
結合 CAS 操作實現無鎖算法。
友情提示:本文已經整理成文檔,可以到如下鏈接免積分下載閱讀
https://download.csdn.net/download/ylfhpy/90498379