Java Collections là một trong những thư viện nền tảng được sử dụng thường xuyên nhất trong phát triển ứng dụng, đồng thời cũng là module được hỏi nhiều nhất trong phỏng vấn Java. Khi học collections, bạn cần vừa biết mỗi container phù hợp với trường hợp sử dụng nào, vừa hiểu các lựa chọn thiết kế phía sau việc mở rộng capacity, hash collision, iterator, thread safety và concurrent collections.
Lịch sử của blocking queue trong Java có thể bắt nguồn từ phiên bản JDK1.5. Khi đó nền tảng Java bổ sung java.util.concurrent, tức package JUC thường được nhắc đến, trong đó có nhiều công cụ điều khiển quy trình concurrency, container concurrency, atomic class... Blocking queue được thảo luận trong bài viết này cũng nằm trong đó.
Bài viết này do Mò code gửi: https://mp.weixin.qq.com/s/AHWzboztt53ZfFZmsSnMSw, JavaGuide đã cải tiến và tối ưu đáng kể bài viết gốc.
Bài viết trước đã giới thiệu source code HashMap và nhận được phản hồi khá tốt, đồng thời cũng có nhiều bạn đưa ra quan điểm của mình. Lần này chúng ta sẽ tìm hiểu ConcurrentHashMap, một HashMap thread-safe được sử dụng rất thường xuyên. Vậy cấu trúc lưu trữ và nguyên lý triển khai của nó như thế nào?
Trước JDK1.5, nếu muốn sử dụng List an toàn trong môi trường concurrent, bạn có thể chọn Vector hoặc synchronized wrapper được trả về bởi Collections.synchronizedList(). Vector là một collection cũ và đã lỗi thời. Hầu hết các method như thêm, xóa, sửa và tìm kiếm của Vector đều được thêm synchronized. Cách này tuy có thể đảm bảo synchronization, nhưng tương đương với việc đặt một big lock lên toàn bộ Vector, khiến mỗi method khi thực thi đều phải lấy lock và dẫn đến performance rất thấp.
Cảm ơn changfubai đã đóng góp cải tiến cho bài viết này!
Bài viết này tổng hợp các lưu ý thường gặp khi sử dụng collection và nguyên lý cụ thể đằng sau chúng dựa trên 《Alibaba Java Coding Guidelines》.
Bạn nên đọc kỹ vài lần để tránh mắc những lỗi cơ bản này khi tự viết code.
《Alibaba Java Coding Guidelines》 mô tả như sau:
Java Collections, còn gọi là container, chủ yếu được phát triển từ hai interface lớn: một là interface Collection, chủ yếu dùng để lưu trữ các phần tử đơn; một là interface Map, chủ yếu dùng để lưu trữ các cặp key-value. Bên dưới interface Collection còn có ba sub-interface chính: List, Set, Queue.
HashMap không thread-safe, còn Hashtable thread-safe, vì các method bên trong Hashtable về cơ bản đều được thêm synchronized. (Nếu bạn muốn bảo đảm thread-safe thì hãy dùng ConcurrentHashMap!);HashMap có hiệu suất cao hơn Hashtable một chút. Ngoài ra, Hashtable về cơ bản đã bị loại bỏ, không nên dùng nó trong code;HashMap có thể lưu trữ key và value là null, nhưng null làm key chỉ có thể có một, còn null làm value có thể có nhiều; Hashtable không cho phép key và value là null, nếu không sẽ ném NullPointerException.Hashtable mặc định có kích thước ban đầu là 11, sau đó mỗi lần mở rộng, dung lượng trở thành 2n+1. HashMap mặc định có kích thước ban đầu là 16. Sau đó mỗi lần mở rộng, dung lượng tăng gấp 2 lần. ② Nếu khi khởi tạo chỉ định giá trị ban đầu, Hashtable sẽ trực tiếp sử dụng kích thước bạn cung cấp, còn HashMap sẽ mở rộng nó thành lũy thừa của 2 (tableSizeFor() trong HashMap bảo đảm điều này, source code được cung cấp bên dưới). Nói cách khác, HashMap luôn dùng lũy thừa của 2 làm kích thước hash table, phần sau sẽ giải thích vì sao là lũy thừa của 2.HashMap có thay đổi khá lớn khi xử lý hash collision. Khi độ dài linked list lớn hơn ngưỡng (mặc định là 8), linked list sẽ được chuyển thành red-black tree (trước khi chuyển linked list thành red-black tree sẽ kiểm tra; nếu độ dài array hiện tại nhỏ hơn 64 thì sẽ ưu tiên mở rộng array thay vì chuyển thành red-black tree), nhằm giảm thời gian tìm kiếm (phần sau sẽ phân tích quy trình này cùng source code). Hashtable không có cơ chế này.HashMap trộn và làm nhiễu các bit cao và bit thấp của hash value để giảm collision, còn Hashtable trực tiếp sử dụng giá trị hashCode() của key.LinkedHashMap là một collection class do Java cung cấp. Class này kế thừa từ HashMap và duy trì thêm một doubly linked list trên nền HashMap, nhờ đó có các đặc điểm sau:
HashMap, nơi hiệu suất tỉ lệ thuận với capacity, hiệu suất iteration cao hơn nhiều.
LinkedList là một collection class được triển khai dựa trên doubly linked list, thường được so sánh với ArrayList. Phần Tổng hợp câu hỏi phỏng vấn Java Collections thường gặp (phần 1) có giới thiệu chi tiết về sự khác biệt giữa LinkedList và ArrayList.