HashSet vs. ArrayList

Question

Vì vậy, tôi có một lớp lớp tùy chỉnh sẽ có một tập hợp các lớp học tùy chỉnh khác. Vì vậy, nó sẽ giống như thế này:

public class Class { 
    private Set<Student> students; 

    // other methods 
} 

Bây giờ tôi sẽ thêm và loại bỏ nhiều sinh viên cho sinh viên thiết lập và tôi cũng sẽ được thay đổi rất nhiều các lĩnh vực tư nhân của một học sinh đã có trong bộ sinh viên.

CÂU HỎI: Tôi nên sử dụng cấu trúc dữ liệu nào để triển khai tốt nhất điều này? Vì tôi sẽ thay đổi thuộc tính của các đối tượng Sinh viên trong học sinh đã đặt (do đó thay đổi mã băm) nên tôi sử dụng một ArrayList thay thế?

Answer 1

Tôi nên sử dụng cấu trúc dữ liệu nào để triển khai tốt nhất điều này? Vì tôi sẽ thay đổi thuộc tính của các đối tượng Sinh viên trong học sinh đã đặt (do đó thay đổi mã băm) nên tôi sử dụng một ArrayList thay thế?

Nếu mã băm cho các yếu tố bộ chịu trách nhiệm thay đổi, thì bạn KHÔNG nên sử dụng HashSet. (Nếu bạn làm thế, cấu trúc dữ liệu sẽ phá vỡ, và các yếu tố trong tập phải chịu trách nhiệm để đi mất tích.)

Nhưng tôi nghi ngờ bạn nên sử dụng ArrayList một trong hai, bởi vì nếu hashcode() là nhạy cảm với những thay đổi cho đối tượng, sau đó equals(Object) rất có thể sẽ là quá. Và điều đó có nghĩa là contains(...) và các phương pháp tương tự sẽ không thể tìm thấy các đối tượng.

Tôi nghĩ bạn nên sử dụng loại Map và sử dụng "số nhận dạng sinh viên" làm khóa.

(Bạn cũng có thể ghi đè lên hashcode và equals nên bình đẳng đó có nghĩa là hai đối tượng có id giống nhau. Nhưng mà làm cho equals(Object) vô dụng cho mục đích khác.)

Answer 2

Đối với bộ sưu tập được băm như HashSet, khóa phải là immutable. Hashset sử dụng băm bên trong để quyết định xô lưu trữ đối tượng. Và cũng trong khi truy xuất đối tượng, nó sẽ sử dụng hàm băm để tìm nhóm đối tượng. Nếu bạn đang thay đổi đối tượng sau khi lưu trữ, nó có thể thay đổi mã băm của đối tượng và Set có thể không lấy được đối tượng chính xác. Nếu bạn cần phải thay đổi đối tượng ngay cả sau khi thêm nó vào bộ sưu tập thì sử dụng một bộ sưu tập băm không phải là một lựa chọn tốt. Thay vì đi cho Arraylist, nhưng lưu ý rằng với ArrayList bạn sẽ mất lợi thế để truy xuất sinh viên mong muốn một cách nhanh chóng, vì nó có thể là với một bộ.

Answer 3

Bạn không nên sử dụng Set khi kết quả của các đối tượng 'equals phương pháp sẽ thay đổi. Nếu bạn đang xác định sinh viên theo một số ID duy nhất ổn định và equals chỉ cần kiểm tra ID đó, sau đó sử dụng Set là tốt.

Lưu ý rằng HashSet sẽ sử dụng hashCode cho chỉ mục và so sánh, và hashCode nên kết hợp chính xác những lĩnh vực được sử dụng để xác định equals.

Answer 4

Điều đó tùy thuộc. Khi bạn đang nói về sinh viên, vì vậy phải có những thứ như id hoặc rollno là duy nhất. Nếu có thì ghi đè phương thức hashcode và triển khai mã băm trên cơ sở id của chúng. Sau đó, không có hiệu lực trên hashcode bằng cách thay đổi bất kỳ thuộc tính nào khác của sinh viên.

Để chọn Set hoặc List là totaly tùy thuộc vào yêu cầu của bạn. Đọc liên kết này, và nó sẽ làm rõ sự khác biệt giữa Set và danh sách
What is the difference between Set and List?

Và nếu bạn đang sử dụng các đối tượng trong một Set sau đó bạn có thể thử để ghi đè lên cả hashcode and the equals method để kiểm soát tính độc đáo là ở bạn tay.

Answer 5

Các javadoc cho Set nói

Lưu ý: Tuyệt vời chăm sóc phải được thực hiện nếu đối tượng có thể thay đổi được sử dụng như thiết yếu tố. Hành vi của tập hợp không được chỉ định nếu giá trị của đối tượng được thay đổi theo cách ảnh hưởng đến bằng so sánh trong khi đối tượng là một phần tử trong tập hợp. Trường hợp đặc biệt của lệnh cấm này là không được phép cho một tập hợp chứa chính nó làm yếu tố.

Vì vậy, nếu bạn đang sử dụng một HashSet nếu bạn thực hiện hashCode() và equals() dựa với các lĩnh vực inmutable sau đó bạn sẽ không phải vấn đề này. Ví dụ: sử dụng một ID sinh viên duy nhất cho mỗi trường hợp.

Answer 6

Từ yêu cầu của bạn, tôi nghĩ các cấu trúc tốt nhất nên Bản đồ . Thiết lập thực sự cơ bản sử dụng cấu trúc bản đồ bên trong, và bạn cũng cần chăm sóc ghi đè phương thức equals để tra cứu tốt hơn. Và thiết lập và arraylist tìm đối tượng mục tiêu cần có một số thuật toán tìm thấy vì vậy nó không phải như vậy hiệu quả như bạn mong đợi (đặc biệt là trong tình hình bộ sưu tập rất lớn). Ngay cả bản đồ sẽ lãng phí một số không gian, nhưng nếu ID của bạn là một loại kiểu nguyên thủy nào đó, bạn có thể xem xét kiểu triển khai bản đồ nguyên thủy trong số Trove library.

Answer 7

CÂU HỎI: Tôi nên sử dụng cấu trúc dữ liệu nào để triển khai tốt nhất điều này? Vì tôi sẽ thay đổi thuộc tính của các đối tượng Sinh viên trong tập hợp sinh viên (do đó thay đổi mã băm) nên tôi sử dụng một ArrayList thay thế?

Chắc chắn nếu bạn định thay đổi giá trị được sử dụng bởi hashCode hoặc bằng thì không thể sử dụng HashMap hoặc HashSet.

Bạn đang nói rằng bạn muốn xóa và thêm rất nhiều. Câu hỏi đặt ra là nếu bạn muốn làm điều đó một cách ngẫu nhiên hoặc ngẫu nhiên (dựa trên chỉ mục). Nếu bạn thêm, xóa tuần tự thì chắc chắn lựa chọn tốt nhất là LinkedList. Nếu bạn truy cập các đối tượng ngẫu nhiên thì ArrayList sẽ hiệu quả hơn nhiều.

Answer 8

Khi nói đến hành vi của ArrayList và HashSet, chúng là các lớp hoàn toàn khác nhau.

ArrayList

• ArrayList Không xác nhận bản sao.
• get() là O(1)

• là O(n) nhưng bạn đã hoàn toàn kiểm soát thứ tự của các mục.

       get add contains next remove(0) iterator.remove 
  ArrayList    O(1) O(1) O(n)  O(1) O(1)  O(1) 
  

• Không chủ đề an toàn và để làm cho nó chủ đề an toàn bạn phải sử dụng Collections.synchronizedList(...)

HashSet

• HashSet đảm bảo không có bản sao.

• Cung cấp cho bạn phương thức O(1) nhưng không bảo toàn đơn đặt hàng.

       add  contains next  notes 
  HashSet    O(1)  O(1)  O(h/n) h is the table 
  

• Không chủ đề an toàn và để làm cho nó chủ đề an toàn bạn phải sử dụng Collections.synchronizedSet(...)