Trong Java 8, lớp công cụ ConcurrentHashMap phổ biến đã được nâng cấp đáng kể, so với phiên bản Java 7 trước đó, nhiều khía cạnh đã được điều chỉnh và thay đổi.
Tuy nhiên, tư tưởng thiết kế Segment trong Java 7 vẫn còn giá trị tham khảo và học tập, vì vậy trong nhiều tình huống, nhà phỏng vấn thường hỏi bạn:
Cấu trúc của ConcurrentHashMap trong Java 7 và Java 8 là gì?
Điểm giống và khác nhau của chúng là gì?
ConcurrentHashMap trong Java 7
Chúng ta hãy xem sơ đồ cấu trúc của ConcurrentHashMap trong phiên bản Java 7:
Từ hình trên, chúng ta có thể thấy rằng trong ConcurrentHashMap có phân đoạn Segment, Segment kế thừa từ ReentrantLock, có thể hiểu như một khóa, các Segment độc lập với nhau và không ảnh hưởng khi khóa.
So với Hashtable trước đó mỗi lần hoạt động đều phải khóa toàn bộ đối tượng, điều này đã tăng hiệu suất đồng thời đáng kể. Vì khóa của chúng là độc lập chứ không phải toàn bộ đối tượng chỉ có một khóa.
Cấu trúc dữ liệu cơ bản của mỗi Segment tương tự như HashMap, vẫn là cấu trúc phương pháp xích (mảng và danh sách liên kết). Mặc định có 0~15 tổng cộng 16 Segment, vì vậy tối đa có thể hỗ trợ đồng thời 16 luồng hoạt động (hoạt động được phân phối trên các Segment khác nhau).
Giá trị mặc định 16 này có thể được đặt thành các giá trị khác khi khởi tạo, nhưng một khi đã khởi tạo thì không thể mở rộng.
ConcurrentHashMap trong Java 8
Trong Java 8, ConcurrentHashMap gần như được viết lại hoàn toàn, lượng mã từ hơn 1000 dòng trong Java 7 đã trở thành hơn 6000 dòng hiện tại, vì vậy việc đọc mã nguồn cũng trở nên khó khăn hơn nhiều.
Để dễ dàng hiểu, chúng ta vẫn bắt đầu từ sơ đồ cấu trúc tổng thể, xem xét tư tưởng thiết kế tổng thể, sau đó đi sâu vào chi tiết.
Trong hình có 3 loại nút.
- Loại thứ nhất là đơn giản nhất, vị trí trống cho thấy hiện tại chưa có phần tử để điền vào.
- Loại thứ hai là cấu trúc phương pháp xích tương tự như HashMap, trong mỗi vị trí sẽ điền vào nút đầu tiên, nhưng sau này nếu tính ra cùng một giá trị Hash, sẽ sử dụng dạng danh sách liên kết để mở rộng về sau.
- Loại thứ ba là cấu trúc cây đỏ-đen, đây là cấu trúc không có trong ConcurrentHashMap của Java 7, trước đây chúng ta có thể ít tiếp xúc với cấu trúc dữ liệu như vậy.
Khi tình huống thứ hai có độ dài danh sách liên kết lớn hơn một ngưỡng nhất định (mặc định là 8), và đồng thời đáp ứng các yêu cầu dung lượng nhất định, ConcurrentHashMap sẽ chuyển đổi danh sách liên kết từ dạng danh sách liên kết sang dạng cây đỏ-đen, mục đích là để进一步提升 hiệu suất tìm kiếm. Vì vậy, một thay đổi quan trọng của Java 8 là giới thiệu thiết kế cây đỏ-đen, vì cây đỏ-đen không phải là một cấu trúc dữ liệu phổ biến, chúng ta sẽ giới thiệu ngắn gọn các đặc điểm của cây đỏ-đen tại đây.
Cây đỏ-đen là một cây tìm kiếm nhị phân mà mỗi nút đều thuộc tính màu, màu là đỏ hoặc đen, bản chất của cây đỏ-đen là một chiến lược cân bằng cho cây tìm kiếm nhị phân BST, chúng ta có thể hiểu đó là một cây tìm kiếm nhị phân cân bằng, hiệu suất tìm kiếm cao, sẽ tự động cân bằng, ngăn chặn tình trạng mất cân bằng cực đoan ảnh hưởng đến hiệu suất tìm kiếm.
Vì đặc điểm tự cân bằng, tức là chiều cao của cây con trái và phải gần như như nhau, nên hiệu suất tìm kiếm của nó gần như tìm kiếm nhị phân, độ phức tạp thời gian là O(log(n)); ngược lại với danh sách liên kết, độ phức tạp thời gian của nó không giống nhau, nếu xảy ra trường hợp tồi nhất, có thể cần duyệt toàn bộ danh sách liên kết mới tìm được phần tử mục tiêu, độ phức tạp thời gian là O(n), lớn hơn nhiều so với O(log(n)) của cây đỏ-đen, đặc biệt là khi số lượng nút ngày càng tăng, ưu thế của O(log(n)) sẽ thể hiện rõ hơn.
Một số đặc điểm khác của cây đỏ-đen:
- Mỗi nút hoặc là màu đỏ, hoặc là màu đen, nhưng nút gốc永远是 màu đen.
- Các nút màu đỏ không thể liên tiếp, tức là nút con và nút cha của nút màu đỏ không thể là màu đỏ.
- Từ bất kỳ nút nào đến các nút lá của nó đều chứa cùng số lượng nút màu đen.
Chính do những quy tắc và yêu hạn chế này, cây đỏ-đen đảm bảo hiệu suất tìm kiếm cao, vì vậy bây giờ chúng ta có thể hiểu tại sao ConcurrentHashMap của Java 8 lại giới thiệu cây đỏ-đen.
Lợi ích là tránh trong trường hợp cực đoan danh sách liên kết xung đột trở nên rất dài, khi tìm kiếm, hiệu suất sẽ rất chậm. Còn cây đỏ-đen có đặc điểm tự cân bằng, vì vậy, ngay cả trong trường hợp cực đoan, cũng có thể đảm bảo hiệu suất tìm kiếm ở mức O(log(n)).
Phân tích mã nguồn quan trọng của ConcurrentHashMap trong Java 8
-
Nút Node
Đầu tiên, chúng ta hãy xem cấu trúc lưu trữ nội bộ cơ bản nhất Node, đây chính là từng nút, như đoạn mã này:
Có thể thấy, mỗi Node chứa key-value, và value được修饰 bằng volatile để đảm bảo tính khả thị, đồng thời bên trong còn có một con trỏ next trỏ đến nút tiếp theo, thuận tiện cho việc tạo cấu trúc danh sách liên kết.
Bây giờ chúng ta xem hai phương thức quan trọng và cốt lõi nhất.
-
Phân tích mã nguồn phương thức put
Phương thức cốt lõi của put là putVal, để tiện đọc, tôi đã thêm giải thích các bước quan trọng dưới dạng chú thích vào mã nguồn dưới đây. Chúng ta phân tích từng bước phương thức quan trọng nhất này, phương thức này tương đối dài, chúng ta hãy xem nó một cách rõ ràng.
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) {
throw new NullPointerException();
}
// Tính giá trị hash
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
// Nếu mảng là rỗng, thì khởi tạo
if (tab == null || (n = tab.length) == 0) {
tab = initTable();
}
// Tìm chỉ số mảng tương ứng với giá trị hash
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// Nếu vị trí này là rỗng, thì sử dụng phương thức CAS để đặt giá trị mới
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null))) {
break;
}
}
// Giá trị hash bằng MOVED đang trong quá trình mở rộng
else if ((fh = f.hash) == MOVED) {
tab = helpTransfer(tab, f);
}
// Vị trí điểm có giá trị
else {
V oldVal = null;
// Sử dụng synchronized khóa điểm hiện tại, đảm bảo an toàn đồng thời
synchronized (f) {
if (tabAt(tab, i) == f) {
// Nếu là dạng danh sách liên kết
if (fh >= 0) {
binCount = 1;
// Duyệt danh sách liên kết
for (Node<K, V> e = f; ; ++binCount) {
K ek;
// Nếu phát hiện key đã tồn tại, thì phán đoán có cần phủ định không, sau đó trả về
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent) {
e.val = value;
}
break;
}
Node<K, V> pred = e;
// Đến cuối danh sách liên kết cũng không phát hiện key, cho biết trước đó không tồn tại, thì thêm giá trị mới vào cuối danh sách liên kết
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
}
// Nếu là dạng cây đỏ-đen
else if (f instanceof TreeBin) {
Node<K, V> p;
binCount = 2;
// Gọi phương thức putTreeVal để thêm dữ liệu vào cây đỏ-đen
if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent) {
p.val = value;
}
}
}
}
}
if (binCount != 0) {
// Kiểm tra có đáp ứng điều kiện không và chuyển đổi danh sách liên kết thành dạng cây đỏ-đen, ngưỡng TREEIFY_THRESHOLD mặc định là 8
if (binCount >= TREEIFY_THRESHOLD) {
treeifyBin(tab, i);
}
// Trả về của putVal là giá trị cũ trước khi thêm, nên trả về oldVal
if (oldVal != null) {
return oldVal;
}
break;
}
}
}
addCount(1L, binCount);
return null;
}
Qua phân tích mã nguồn trên, chúng ta đã có hiểu biết chi tiết về phương thức putVal, có thể thấy rằng trong phương thức sẽ từng bước theo tình huống hiện tại của điểm xám là chưa khởi tạo, rỗng, mở rộng rộng, danh sách liên kết, cây đỏ-đen... đưa ra xử lý khác nhau.
-
Phân tích mã nguồn phương thức get
Phương thức get tương đối đơn giản, chúng ta cũng sử dụng cách chú thích mã nguồn để phân tích:
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// Tính giá trị hash
int h = spread(key.hashCode());
// Nếu toàn bộ mảng là rỗng, hoặc dữ liệu điểm xám hiện tại là rỗng, cho biết value tương ứng với key không tồn tại, trả về null trực tiếp
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// Phán đoán nút đầu có phải là nút chúng ta cần không, nếu là thì trả về trực tiếp
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// Nếu giá trị hash của nút đầu nhỏ hơn 0, cho biết là cây đỏ-đen hoặc đang mở rộng rộng, thì sử dụng phương thức find tương ứng để tìm kiếm
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// Duyệt danh sách liên kết để tìm kiếm
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Tóm tắt quá trình get:
- Tính giá trị Hash, và từ giá trị này tìm đến điểm xám tương ứng;
- Nếu mảng là rỗng hoặc vị trí này là null, thì trực tiếp trả về null là được rồi;
- Nếu vị trí này chính là nút chúng ta cần, trực tiếp trả về giá trị của nút này;
- Nếu vị trí này là cây đỏ-đen hoặc đang mở rộng rộng, thì sử dụng phương thức find để tiếp tục tìm kiếm;
- Bằng không thì đó là danh sách liên kết, thì tiến hành duyệt danh sách liên kết để tìm kiếm.
So sánh điểm giống và khác nhau giữa Java 7 và Java 8
Cấu trúc dữ liệu
Java 7 sử dụng Segment phân đoạn khóa để thực hiện,
Còn ConcurrentHashMap trong Java 8 sử dụng mảng + danh sách liên kết + cây đỏ-đen, về điểm này sự khác biệt của chúng rất lớn.
Độ đồng thời
Trong Java 7, mỗi Segment độc lập thêm khóa, số lượng đồng thời tối đa chính là số lượng Segment, mặc định là 16.
Nhưng đến Java 8, độ mịn của khóa càng nhỏ, trong điều kiện lý tưởng số lượng phần tử của mảng table (cũng là độ dài mảng) chính là số lượng đồng thời tối đa nó hỗ trợ, độ đồng thời so với trước đây có tăng lên.
Nguyên lý đảm bảo an toàn đồng thời
Java 7 sử dụng Segment phân đoạn khóa để đảm bảo an toàn, còn Segment là kế thừa từ ReentrantLock.
Java 8 từ bỏ thiết kế Segment, sử dụng Node + CAS + synchronized để đảm bảo an toàn luồng.
Gặp xung đột Hash
Java 7 khi xung đột Hash, sẽ sử dụng phương pháp xích, cũng là dạng danh sách liên kết.
Java 8 trước tiên sử dụng phương pháp xích, khi độ dài danh sách liên kết vượt qua ngưỡng nhất định, sẽ chuyển đổi danh sách liên kết thành cây đỏ-đen, để nâng cao hiệu suất tìm kiếm.
Độ phức tạp thời gian tìm kiếm
Java 7 độ phức tạp thời gian duyệt danh sách liên kết là O(n), n là độ dài danh sách liên kết.
Java 8 nếu trở thành duyệt cây đỏ-đen, thì độ phức tạp thời gian giảm xuống còn O(log(n)), n là số lượng nút của cây.