Sử dụng API Java 8 luồng, có thể sắp xếp() được dựa vào khi gọi Collectors.toSet()?

Question

Đây là việc thực hiện các phương pháp toSet() lớp của java.util.stream.Collectors:

public static <T> 
Collector<T, ?, Set<T>> toSet() { 
    return new CollectorImpl<>((Supplier<Set<T>>) HashSet::new, Set::add, 
           (left, right) -> { left.addAll(right); return left; }, 
           CH_UNORDERED_ID); 
} 

Như chúng ta có thể thấy, nó sử dụng một HashSet và gọi add. Từ HashSetdocumentation, "Nó không đảm bảo về thứ tự lặp của tập hợp; đặc biệt, nó không đảm bảo rằng thứ tự sẽ không thay đổi theo thời gian".

Trong đoạn mã sau, một List của String được xem trực tiếp, sắp xếp và tổng hợp theo một Set:

public static void main(String[] args) { 
    Set<String> strings = Arrays.asList("c", "a", "b") 
      .stream() 
      .sorted() 
      .collect(Collectors.toSet()); 
    System.out.println(strings.getClass()); 
    System.out.println(strings); 
} 

này cung cấp kết quả:

class java.util.HashSet

[a, b, c]

Các đầu ra được sắp xếp. Điều tôi nghĩ đang xảy ra ở đây là mặc dù hợp đồng được cung cấp bởi tài liệu HashSet chỉ định rằng thứ tự không phải là thứ mà nó cung cấp, việc triển khai sẽ xảy ra để thêm vào thứ tự. Tôi cho rằng điều này có thể thay đổi trong các phiên bản tương lai/khác nhau giữa các JVM và cách tiếp cận khôn ngoan hơn là làm một cái gì đó như Collectors.toCollection(TreeSet::new).

Có thể sorted() được dựa vào khi gọi Collectors.toSet() không?

Ngoài ra, chính xác những gì "nó không đảm bảo rằng thứ tự sẽ không đổi theo thời gian" nghĩa là gì? (Tôi giả sử add, remove, việc thay đổi kích thước của mảng cơ bản?)

Answer 1

Câu trả lời là không. Khi bạn đã thêm các mục vào một Bộ, bạn không thể dựa vào bất kỳ thứ tự nào. Từ JDK sourcecode (HashSet.java):

/** 
* Returns an iterator over the elements in this set. The elements 
* are returned in no particular order. 
* 
* @return an Iterator over the elements in this set 
* @see ConcurrentModificationException 
*/ 
public Iterator<E> iterator() { 
    return map.keySet().iterator(); 
} 

Bây giờ, trong các phiên bản trước của JDK mặc dù một trật tự không được đảm bảo, bạn sẽ thường nhận được các mục trong theo thứ tự chèn (trừ trường hợp lớp của các đối tượng thực hiện hashCode() và sau đó bạn sẽ nhận được thứ tự được quyết định bởi hashCode()). hoặc thứ tự của việc tạo ra các đối tượng hoặc thứ tự gọi của hashCode() trên các đối tượng. Như @ Holgar đề cập đến trong các ý kiến ​​dưới đây, trong HotSpot đó là sau này. Và bạn thậm chí không thể dựa vào điều đó vì có ngoại lệ cho điều này vì số tuần tự không phải là thành phần duy nhất trong trình tạo hashCode.

Gần đây tôi đã nghe một cuộc nói chuyện từ Stuart Marks (người chịu trách nhiệm viết lại một phần chính của Bộ sưu tập trong Java 9) và nói rằng họ đã thêm ngẫu nhiên vào thứ tự lặp lại của Bộ (được tạo bởi set-factories) trong Java 9. Nếu bạn muốn nghe phiên, phần mà anh ta nói về bộ bắt đầu here - nói chuyện tốt, rất khuyến khích bằng cách này !.

Vì vậy, ngay cả khi bạn sử dụng để đếm thứ tự lặp lại của Bộ, khi bạn chuyển sang Java 9, bạn nên ngừng làm như vậy.

Tất cả những gì đã nói, nếu bạn cần để bạn nên xem xét sử dụng một SortedSet, LinkedHashSet hoặc TreeSet

Answer 2

Để trả lời câu hỏi đó, bạn cần phải biết một chút về cách HashSet được thực hiện. Như tên cho thấy, một HashSet được triển khai bằng cách sử dụng bảng băm . Về cơ bản, một bảng băm là một mảng được lập chỉ mục bởi các phần tử băm. Một hàm băm (trong Java, băm của một đối tượng được tính bằng cách object.hashCode()) về cơ bản là một chức năng đáp ứng một số tiêu chí:

• nó là (tương đối) nhanh chóng để tính toán cho một nguyên tố
• hai đối tượng mà .equals() nhau có băm giống hệt
• có một xác suất thấp mà các mặt hàng khác nhau có cùng bảng băm

vì vậy, khi bạn meed một HashSet được "sắp xếp" (được hiểu là "các iterator giữ gìn trật tự tự nhiên các yếu tố "), điều này là do một vài sự trùng hợp:

• trật tự tự nhiên của các yếu tố tôn trọng trật tự tự nhiên của bảng hashCode s
• băm của họ là đủ nhỏ để không có va chạm (hai yếu tố với cùng mã băm)

Nếu bạn nhìn vào String lớp phương pháp hashCode(), bạn sẽ thấy rằng đối với chuỗi một chữ, mã băm tương ứng với chỉ số Unicode (điểm mã) của bức thư - vì vậy trong cụ này trường hợp, miễn là bảng băm đủ nhỏ, các phần tử sẽ được sắp xếp. Tuy nhiên, đây là một sự trùng hợp rất lớn và

• sẽ không giữ cho bất kỳ thứ tự sắp xếp khác
• sẽ không giữ cho các lớp học mà hashcodes không theo trật tự tự nhiên của chúng
• sẽ không giữ hashtables với va chạm

và hơn thế nữa, điều này không liên quan gì đến thực tế là sorted() được gọi trên luồng - đơn giản là do cách thức hashCode() được triển khai và do đó thứ tự của bảng băm. Do đó, câu trả lời đơn giản cho câu hỏi là "không".