Triển khai giao diện Set và Queue

"Chà, bộ xử lý của bạn thế nào?"

"Không sao đâu. Tôi đã ngồi trong nitơ lỏng cả tiếng đồng hồ, nên giờ tôi khỏe như mới!"

"Tuyệt. Vậy thì tiếp tục nào."

"Đặt bộ sưu tập."

Về mặt toán học, một tập hợp là một nhóm các phần tử duy nhất. Do đó, trong lập trình, Set là một tập hợp các phần tử duy nhất, tức là một tập hợp không cho phép bạn lưu trữ các phần tử giống hệt nhau.

"Tôi không biết liệu Ellie có cho bạn xem hệ thống phân cấp thừa kế của Set hay không. Nếu không, đây là:"

"Một HashSet là một bộ sưu tập lưu trữ các phần tử bên trong bằng cách sử dụng các giá trị băm được trả về bởi phương thức hashCode ()."

"Để đơn giản, HashSet<E> lưu trữ một đối tượng HashMap<E, Object> lưu trữ các giá trị của HashSet dưới dạng khóa."

"Ái chà!"

"Sử dụng mã băm cho phép bạn nhanh chóng tìm kiếm, thêm và xóa các phần tử khỏi Tập hợp."

"Nhưng hãy nhớ rằng lớp của bạn phải triển khai đúng các phương thức hashCode & equals để thêm các đối tượng của các lớp của bạn vào Tập hợp và để tìm thấy chúng ở đó một cách chính xác."

"Cả hai phương pháp được sử dụng rất nhiều bên trong HashSet/HashMap. "

"Nếu bạn quên triển khai phương thức hashCode (), thì bạn có nguy cơ không thể tìm thấy đối tượng của mình trong Tập hợp, ngay cả khi nó có mặt."

"Vâng, tôi nhớ, tôi nhớ. Lúc trước anh đã nói với tôi chuyện này. Tôi đã nghe hết rồi."

"OK. Sau đây là một số thông tin hữu ích hơn cho bạn."

"Giả sử bạn đã triển khai chính xác mã băm và bằng  trong lớp của mình và bạn vui vẻ lưu trữ các đối tượng của mình trong Tập hợp."

"Nhưng sau đó, bạn thay đổi một trong các đối tượng và bằng cách đó, bạn thay đổi dữ liệu nội bộ được sử dụng để tính hàm băm của nó . Vì vậy, hàm băm của đối tượng thay đổi."

"Và điều này có nghĩa là khi bạn tìm kiếm nó trong Bộ, bạn có thể sẽ không tìm thấy nó."

"Chà! Nó hoạt động như thế nào?"

"Đây là một cạm bẫy nổi tiếng khi làm việc với các giá trị băm. Về cơ bản, các tìm kiếm HashSet (và HashMap) chỉ được đảm bảo hoạt động bình thường nếu các đối tượng là bất biến ."

"Ồ! Và cái gì, không ai làm gì cả?"

"Mọi người giả vờ rằng vấn đề không tồn tại. Nhưng điều này thường xuất hiện trong các cuộc phỏng vấn, vì vậy có thể đáng để ghi nhớ..."

" LinkedHashSet là một HashSet có các phần tử cũng được lưu trữ trong danh sách được liên kết. HashSets bình thường không hỗ trợ thứ tự của các phần tử. Đầu tiên, nó đơn giản không phải là một hoạt động chính thức. Thứ hai, ngay cả thứ tự bên trong cũng có thể thay đổi đáng kể khi một phần tử được thêm vào."

Nhưng bạn có thể lấy một trình vòng lặp từ LinkedHashSet và sử dụng nó để duyệt qua tất cả các phần tử theo thứ tự chúng được thêm vào LinkedHashSet . Nó không xảy ra thường xuyên, nhưng đôi khi điều này là rất cần thiết."

"Tôi hiểu rồi. Tôi thích khi có các lớp học dành cho những tình huống «đề phòng» này. Những trường hợp như vậy không phải là hiếm."

" TreeSet là một bộ sưu tập lưu trữ các phần tử dưới dạng cây được sắp xếp theo giá trị. TreeSet <E> chứa TreeMap <E, Object> lưu trữ tất cả các giá trị này. Và TreeMap này sử dụng cây đỏ - đen cân bằng để lưu trữ phần tử . Do đó, nó hỗ trợ các thao tác thêm, xóa và chứa rất nhanh."

"Vâng, tôi nhớ. Chúng tôi vừa mới thảo luận về điều đó. Và tôi cũng đã nghĩ về việc nó được sử dụng ở đâu."

"Và hóa ra là một số bộ sưu tập phổ biến nhất của Java sử dụng nó."

"Vâng. Nhân tiện, những người phỏng vấn thường hỏi về TreeSet . Họ thường cố lừa bạn. Họ sẽ nói, 'nếu TreeSet sử dụng cây nhị phân, thì tất cả các phần tử có thể tạo thành một nhánh dài, vì vậy việc tìm kiếm sẽ mất một «Đây chính là lúc để đặt kẻ xấc xược vào vị trí của mình bằng cách tuyên bố, "Ngay cả một đứa trẻ cũng biết rằng TreeSet và TreeMap sử dụng cây đỏ đen cân bằng , vì vậy tình huống đó thực sự là không thể.""

"À. Tôi muốn nhìn thấy khuôn mặt của người đã hỏi câu hỏi đó. Tôi thậm chí có thể ghi nhớ cụm từ đó...."

"Nhưng trong thực tế, Set hóa ra không đơn giản như tôi nghĩ ban đầu."

"Mặt khác, tình huống với Hàng đợi đơn giản hơn nhiều:"

" Queue triển khai một hàng đợi. Các phần tử được thêm vào cuối hàng đợi và lấy từ phía trước."

" PriorityQueue thực sự là triển khai cổ điển duy nhất của giao diện Hàng đợi , không tính LinkedList , về mặt kỹ thuật cũng là một hàng đợi."

"Được rồi, tôi đang mệt mỏi. Đó là tất cả cho ngày hôm nay. Cho đến lần sau."