TreeSet sử dụng nội bộ TreeMap, do đó, nó là cần thiết để thực hiện phương pháp Hashcode khi sử dụng Treeset

Question

Tôi muốn biết ý nghĩa của nó khi javadocs cho TreeSet nói 'Lớp này thực hiện giao diện Set, được hỗ trợ bởi một cá thể TreeMap'? Trong ví dụ dưới đây, tôi chưa triển khai phương thức Hashcode và nó vẫn hoạt động như mong đợi, tức là nó có thể sắp xếp các đối tượng. Lưu ý rằng tôi đã cố tình không triển khai thực hiện Equals nhất quán để kiểm tra hành vi TreeSet.

import java.util.TreeSet; 


public class ComparisonLogic implements Comparable<ComparisonLogic>{ 

String field1; 
String field2; 

public String toString(){ 
    return field1+" "+field2; 
} 

ComparisonLogic(String field1,String field2){ 
    this.field1= field1; 
    this.field2= field2; 

} 
public boolean equal(Object arg0){ 
    ComparisonLogic obj = (ComparisonLogic) arg0; 

    if(this.field1.equals(obj.field1)) 
     return true; 
    else 
     return false; 
} 

public int compareTo(ComparisonLogic arg0){ 
    ComparisonLogic obj = (ComparisonLogic) arg0; 
    return this.field2.compareToIgnoreCase(obj.field2); 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    ComparisonLogic x = new ComparisonLogic("Tom", "jon"); 
    ComparisonLogic y = new ComparisonLogic("Tom", "Ben"); 
    ComparisonLogic z = new ComparisonLogic("Tom", "Wik"); 

    TreeSet<ComparisonLogic> set = new TreeSet<ComparisonLogic>(); 
    set.add(x); 
    set.add(y); 
    set.add(z); 
    System.out.println(set); 
} 

} 

Ví dụ này in [Tom Ben, Tom jon, Tom Wik] Vì vậy, nó được phân loại dựa trên phương thức compareTo và hashcode() phương pháp trông giống như không đáng kể trong scenario.However này, TreeSet được hỗ trợ bởi TreeMap, nội bộ nếu TreeMap được sử dụng để phân loại, treeMap băm như thế nào?

Answer 1

ComparisonObject của bạn đang sử dụng phương thức hashCode được xác định trên Object. Hãy thử thêm một số khác nhau của ComparisonLogic 's, với các giá trị tương tự cho cả hai lĩnh vực, và xem những gì sẽ xảy ra.

Answer 2

Tôi nghĩ bạn đang đặt ra hai câu hỏi.

1, Tại sao mã của bạn hoạt động?

Như Avi viết tại this chủ đề:

Khi bạn không ghi đè lên phương thức hashCode(), lớp học của bạn được thừa hưởng hashCode mặc định() phương pháp từ Object, mang đến cho mỗi đối tượng một mã băm biệt . Điều này có nghĩa là t1 và t2 có hai mã băm khác nhau, ngay cả khi bạn so sánh chúng, chúng sẽ bằng nhau. Tùy thuộc vào việc triển khai băm cụ thể, bản đồ là miễn phí để lưu trữ chúng một cách riêng biệt.

Điều này có nghĩa là nó không phải lưu trữ riêng biệt nhưng có thể. Hãy thử mã này:

TreeSet<ComparisonLogic> set = new TreeSet<ComparisonLogic>(); 
    set.add(new ComparisonLogic("A", "A")); 
    set.add(new ComparisonLogic("A", "B")); 
    set.add(new ComparisonLogic("A", "C")); 
    set.add(new ComparisonLogic("B", "A")); 
    set.add(new ComparisonLogic("B", "B")); 
    set.add(new ComparisonLogic("B", "C")); 
    set.add(new ComparisonLogic("C", "A")); 
    set.add(new ComparisonLogic("C", "B")); 
    set.add(new ComparisonLogic("C", "C")); 
    set.add(new ComparisonLogic("A", "A")); 

    System.out.println(set.remove(new ComparisonLogic("A", "A"))); 
    System.out.println(set.remove(new ComparisonLogic("A", "B"))); 
    System.out.println(set.remove(new ComparisonLogic("A", "C"))); 
    System.out.println(set.remove(new ComparisonLogic("B", "A"))); 
    System.out.println(set.remove(new ComparisonLogic("B", "B"))); 
    System.out.println(set.remove(new ComparisonLogic("B", "C"))); 
    System.out.println(set.remove(new ComparisonLogic("C", "A"))); 
    System.out.println(set.remove(new ComparisonLogic("C", "B"))); 
    System.out.println(set.remove(new ComparisonLogic("C", "C"))); 

Sản lượng đối với tôi là như sau:

true 
true 
true 
false 
false 
false 
false 
false 
false 

Điều đó có nghĩa một số trong số họ đã có một số trong số họ không.

2, ý nghĩa của nó khi javadocs cho Treeset nói 'Lớp này triển khai giao diện Set, được hỗ trợ bởi một cá thể TreeMap'?

Nó có nghĩa là lớp TreeSet trong java 1.7 trông giống như sau:

public class TreeSet<E> extends AbstractSet<E> 
implements NavigableSet<E>, Cloneable, java.io.Serializable 
{ 
/** 
* The backing map. 
*/ 
private transient NavigableMap<E,Object> m; 

TreeSet(NavigableMap<E,Object> m) { 
    this.m = m; 
} 

... (lots of other code)  

public boolean contains(Object o) { 
    return m.containsKey(o); 
} 

etc. 

Điều này có nghĩa rằng có một bản đồ bên dưới lớp TreeSet và có rất nhiều các phương pháp mà chỉ giao cho nó .

Tôi hy vọng tôi có thể trợ giúp.

Answer 3

TreeSet nội bộ sử dụng đối tượng TreeMap 'm' để lưu trữ đối tượng như cặp khóa-giá trị trong đó hàm ý rằng cuộc gọi

set.add(x); 

nội bộ gọi phương thức đặt của TreeMap:

public boolean add(E e) { 
    return m.put(e, PRESENT)==null; 
} 

phương pháp Bây giờ đặt trong nội bộ các cuộc gọi hoặc so sánh nếu Comparator được cung cấp hoặc trong trường hợp của bạn sử dụng phương thức compareToic class "compareTo".

Không bao giờ sử dụng bằng hoặc hashcode thay vì sử dụng compareTo (Object o1) (được cung cấp trong khi thực hiện Comparable) hoặc đối sánh (Object o1, object o2) (cung cấp trong khi thực hiện Comparator) để xác định sự hiện diện của Object trong tập hợp.

để trả lời câu hỏi của bạn, bạn không bắt buộc phải triển khai phương thức hashcode() trừ khi bạn đang sử dụng phương pháp này trong việc so sánh phương thức so sánh (so sánh hoặc so sánh) của bạn.

Answer 4

Đúng là TreeSet sử dụng nội bộ TreeMap. TreeMap không cần phải có phương thức hashCode và equals được triển khai cho các đối tượng chính. TreeMap nội bộ sử dụng cây đỏ-đen là một cây tìm kiếm nhị phân tự cân bằng. Thứ tự trong cây này được duy trì bằng cách sử dụng phương thức compareTo (đối tượng khóa thực hiện giao diện Comparable) hoặc phương thức so sánh (trình so sánh được cung cấp được định nghĩa trong khi xây dựng TreeMap, trong trường hợp này là TreeSet). Hy vọng nó xóa.