Tại sao một số cấu trúc dữ liệu bộ sưu tập không duy trì thứ tự chèn? Điều gì đặc biệt đạt được so với việc duy trì trật tự? Chúng ta có thể đạt được điều gì đó nếu chúng ta không duy trì trật tự không?Bộ sưu tập Java duy trì thứ tự chèn
Hiệu suất. Nếu bạn muốn thứ tự chèn ban đầu có các lớp LinkedXXX, trong đó duy trì một danh sách liên kết bổ sung trong thứ tự chèn. Hầu hết thời gian bạn không quan tâm, vì vậy bạn sử dụng một HashXXX, hoặc bạn muốn một thứ tự tự nhiên, vì vậy bạn sử dụng TreeXXX. Trong một trong những trường hợp đó, tại sao bạn phải trả thêm chi phí của danh sách được liên kết?
Phụ thuộc vào những gì bạn cần triển khai để thực hiện tốt. Thứ tự chèn thường không phải là thú vị vì vậy không cần phải duy trì nó để bạn có thể sắp xếp lại để có được hiệu suất tốt hơn.
Đối với Bản đồ, nó thường là HashMap và TreeMap được sử dụng. Bằng cách sử dụng mã băm, các mục có thể được đặt trong các nhóm nhỏ dễ dàng để tìm kiếm. TreeMap duy trì thứ tự sắp xếp của các mục được chèn vào với chi phí tìm kiếm chậm hơn, nhưng dễ sắp xếp hơn HashMap.
Khi bạn sử dụng dữ liệu HashSet (hoặc HashMap) được lưu trữ trong "nhóm" dựa trên giá trị băm của đối tượng của bạn. Bằng cách này, dữ liệu của bạn dễ truy cập hơn vì bạn không phải tìm kiếm dữ liệu cụ thể này trong toàn bộ Tập hợp, bạn chỉ cần tìm trong nhóm bên phải.
Bằng cách này bạn có thể tăng hiệu suất trên các điểm cụ thể.
Mỗi triển khai Bộ sưu tập đều có tính đặc thù của nó để sử dụng tốt hơn trong một điều kiện nhất định. Mỗi đặc điểm đó đều có chi phí. Vì vậy, nếu bạn không thực sự cần nó (ví dụ như thứ tự chèn) bạn tốt hơn sử dụng một thực hiện mà không cung cấp nó và phù hợp hơn với yêu cầu của bạn.
Tôi không thể trích dẫn tham chiếu, nhưng bằng cách thiết kế các giao diện List và Set của giao diện Collection về cơ bản có thể mở rộng Array s. Dưới dạng Collections theo các phương thức cung cấp mặc định để động thêm và xóa yếu tố tại bất kỳ điểm nào - trong đó Array không có thứ tự chèn có thể không được giữ nguyên. Vì vậy, vì có nhiều phương pháp cho thao tác nội dung hơn, cần có các triển khai đặc biệt để duy trì trật tự.
Một điểm khác là hiệu suất, vì hiệu suất hoạt động tốt nhất Collection có thể không thực hiện được, giữ nguyên thứ tự chèn của nó. Tuy nhiên, tôi không chắc chắn, cách chính xác Collections quản lý nội dung của họ để tăng hiệu suất.
Vì vậy, trong ngắn hạn, hai lý do chính tôi có thể nghĩ ra lý do tại sao có lệnh giữ gìn Collection triển khai là:
Lưu ý rằng 'Mảng' là một lớp thực tế, trong khi mảng là một loại đối tượng chứa đặc biệt. Tôi cũng khá chắc chắn 'LinkedList' thực sự sử dụng một danh sách liên kết nhưng tôi đã không đọc mã. :-) – wds
Ok, lấy điểm, tôi đã chỉnh sửa bài đăng của mình. Giới thiệu về nhận xét 'LinkedList' của bạn: đâu là mâu thuẫn với những gì tôi đã đăng? – FK82
Để làm rõ: Một 'LinkedList' afaik là một' List' (có thể đọc được 'Mảng') có thứ tự chèn được duy trì trong một' Danh sách' khác (hai trong số đó là * liên kết *, do đó tên). Hoặc, tôi có sai về điều đó không? – FK82
LinkedHashMap), nhưng điều đó cần nhiều mã hơn, và khi chạy nhiều bộ nhớ hơn và nhiều thời gian hơn. Việc mất hiệu suất thường không đáng kể, nhưng nó có thể được.TreeSet/Map, lý do chính để sử dụng chúng là thứ tự lặp lại tự nhiên và chức năng khác được thêm vào trong giao diện SortedSet/Map.+1 Để đề cập đến "nhưng cần nhiều mã hơn". – helpermethod
Chỉ cần lưu ý một cách nhanh chóng: nghiêm chỉnh việc thực hiện 'Map' không phải là' Bộ sưu tập 'vì chúng không triển khai giao diện' Bộ sưu tập'. Họ có phương pháp tương tự, nhưng đó là nó. Kiểm tra: http://download.oracle.com/javase/1.4.2/docs/guide/collections/overview.html (#Collection Interface) Rất có thể câu hỏi của OP sẽ xử lý các bản đồ. – FK82
Tại sao cần duy trì thứ tự chèn? Nếu bạn sử dụng HashMap, bạn có thể nhận được mục nhập theo số key. Nó không có nghĩa là nó không cung cấp các lớp học làm những gì bạn muốn.
Bộ sưu tập không duy trì thứ tự chèn. Một số chỉ là mặc định để thêm một giá trị mới ở cuối. Duy trì thứ tự chèn chỉ hữu ích nếu bạn ưu tiên các đối tượng bằng cách sử dụng nó hoặc sử dụng nó để sắp xếp các đối tượng theo một cách nào đó.
Đối với lý do tại sao một số bộ sưu tập duy trì nó theo mặc định và những người khác thì không, điều này chủ yếu là do việc triển khai và đôi khi chỉ là một phần của định nghĩa tập hợp.
Lists duy trì trật tự chèn như chỉ thêm một mục mới ở cuối hoặc đầu là việc thực hiện nhanh nhất của phương thức add (Object).
Đặt Việc triển khai HashSet và TreeSet không duy trì thứ tự chèn khi các đối tượng được sắp xếp để tra cứu nhanh và duy trì thứ tự chèn sẽ yêu cầu bộ nhớ bổ sung. Điều này dẫn đến hiệu suất đạt được vì thứ tự chèn gần như không bao giờ thú vị đối với Bộ.
ArrayDeque một deque có thể sử dụng cho que đơn giản và chồng, do đó bạn muốn có '' đầu tiên trong lần đầu tiên ra '' hoặc '' đầu tiên trong cuối cùng ra khỏi '' hành vi, cả hai yêu cầu rằng ArrayDeque duy trì trật tự chèn. Trong trường hợp này, thứ tự chèn được duy trì như một phần trung tâm của hợp đồng các lớp học.
rất thông tin, đặc biệt là về ArrayDeque. – Jayy
Đó là một phần trong sách dạy nấu ăn của O'Reilly Java có tên "Tránh thôi thúc sắp xếp" Câu hỏi mà bạn nên hỏi thực sự ngược lại với câu hỏi ban đầu của bạn ... " " Phải mất rất nhiều nỗ lực để sắp xếp và duy trì thứ tự đó. Phân loại chắc chắn là dễ dàng nhưng nó thường không quy mô trong hầu hết các chương trình. Nếu bạn định xử lý hàng nghìn hoặc hàng chục nghìn yêu cầu (insrt, del, get, etc) mỗi giây cho dù bạn đang sử dụng cấu trúc dữ liệu được sắp xếp hay không được sắp xếp thì sẽ rất quan trọng.
Được rồi ... vì vậy các bài đăng này cũ hơn so với bây giờ, nhưng yêu cầu chèn là tùy thuộc vào nhu cầu hoặc yêu cầu ứng dụng của bạn, vì vậy chỉ cần sử dụng đúng loại bộ sưu tập. Đối với hầu hết các phần, nó là không cần thiết, nhưng trong một tình huống mà bạn cần phải sử dụng các đối tượng theo thứ tự chúng được lưu trữ, tôi thấy một nhu cầu nhất định. Tôi nghĩ rằng trật tự quan trọng khi bạn đang tạo ví dụ như một thuật sĩ hoặc một động cơ dòng chảy hoặc một cái gì đó của bản chất đó, nơi bạn cần phải đi từ nhà nước đến nhà nước hoặc một cái gì đó. Theo nghĩa đó, bạn có thể đọc nội dung từ danh sách mà không cần theo dõi những gì bạn cần tiếp theo hoặc duyệt qua danh sách để tìm những gì bạn muốn. Nó giúp với hiệu suất trong ý nghĩa đó. Nó không quan trọng hoặc những bộ sưu tập khác sẽ không có ý nghĩa nhiều.
một số Bộ sưu tập không duy trì thứ tự vì, chúng tính hàm băm của nội dung và lưu trữ theo đó trong nhóm thích hợp.
Ví dụ: Tại sao 'java.util.HashSet' cần duy trì thứ tự chèn? –
no .. i am ask ..does chúng tôi mất bất cứ điều gì trong khi duy trì trật tự ..contrary làm chúng ta đạt được một cái gì đó nếu chúng ta không duy trì thứ tự – JavaUser
ví dụ: LinkedList. Hãy suy nghĩ về nó, nó sẽ không được dễ dàng hơn để nối/thêm vào một danh sách liên kết hơn chèn nó ở giữa? – st0le