Set 集合详解

Comparable 和 Comparator 的区别

1. Comparable 接口只有一个方法 compareTo()，用于比较对象自身与另一个对象的大小关系。实现 Comparable 接口的类可以直接通过调用 Arrays.sort() 或 Collections.sort() 方法进行排序。 Comparator 接口有两个方法 compare() 和 equals()，其中 compare() 方法用于比较两个对象的大小关系，可以通过 Collections.sort() 方法的重载版本或者使用 TreeMap、PriorityQueue 等需要比较对象的集合类来进行排序。equals() 方法用于比较两个对象是否相等，但在比较大小时并不会使用到。
2. Comparable 接口是在类的定义时就实现的，实现 Comparable 接口意味着该类支持自然排序（natural ordering），即可以根据对象自身的属性进行排序。而 Comparator 接口是在排序时作为参数传递进去的，可以根据不同的比较规则进行排序，也就是说可以定义多个 Comparator 来比较同一个类的对象。
3. Comparable 接口的实现在集合类中被广泛使用，例如在 TreeSet、TreeMap 等集合类中需要比较元素的大小关系时，会首先尝试使用元素自身实现的 Comparable 接口进行比较。如果元素没有实现 Comparable 接口，则需要通过传递一个 Comparator 对象来进行比较。因此，实现 Comparable 接口可以使得类更加通用，因为它可以被广泛应用于不同的集合类中。
4. Comparable 接口是 Java 的内部接口，定义在 java.lang 包中，而 Comparator 接口是 Java 的标准类库中的接口，定义在 java.util 包中。 综上所述，Comparable 和 Comparator 都是用于比较对象的接口，但是它们之间的区别主要在于实现方式、应用场景和使用方式等方面。需要根据实际情况选择合适的接口来进行对象的比较。

综上所述，Comparable 和 Comparator 都是用于比较对象的接口，但是它们之间的区别主要在于实现方式、应用场景和使用方式等方面。需要根据实际情况选择合适的接口来进行对象的比较。

Comparator 定制排序（直接方法中重写）

ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
System.out.println("原始数组:");
System.out.println(arrayList);
// void reverse(List list)：反转
Collections.reverse(arrayList);
System.out.println("Collections.reverse(arrayList):");
System.out.println(arrayList);

// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);
// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
});
System.out.println("定制排序后：");
System.out.println(arrayList);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

重写 compareTo 方法实现按年龄来排序（在实体类中重写方法）

// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他
// 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了
public  class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

 public static void main(String[] args) {
        TreeMap<Person, String> pdata = new TreeMap<Person, String>();
        pdata.put(new Person("张三", 30), "zhangsan");
        pdata.put(new Person("李四", 20), "lisi");
        pdata.put(new Person("王五", 10), "wangwu");
        pdata.put(new Person("小红", 5), "xiaohong");
        // 得到key的值的同时得到key所对应的值
        Set<Person> keys = pdata.keySet();
        for (Person key : keys) {
            System.out.println(key.getAge() + "-" + key.getName());

        }
    }

Output：

5-小红
10-王五
20-李四
30-张三

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

源码解析

public class HashSet<E>  
   extends AbstractSet<E>  
   implements Set<E>, Cloneable, java.io.Serializable  
{  
   static final long serialVersionUID = -5024744406713321676L;  
 
   // 底层使用HashMap来保存HashSet中所有元素。  
   private transient HashMap<E,Object> map;  
     
   // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。  
   private static final Object PRESENT = new Object();  
 
   /** 
    * 默认的无参构造器，构造一个空的HashSet。 
    *  
    * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
    */  
   public HashSet() {  
   map = new HashMap<E,Object>();  
   }  
 
   /** 
    * 构造一个包含指定collection中的元素的新set。 
    * 
    * 实际底层使用默认的加载因子0.75和足以包含指定 
    * collection中所有元素的初始容量来创建一个HashMap。 
    * @param c 其中的元素将存放在此set中的collection。 
    */  
   public HashSet(Collection<? extends E> c) {  
   map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));  
   addAll(c);  
   }  
 
   /** 
    * 以指定的initialCapacity和loadFactor构造一个空的HashSet。 
    * 
    * 实际底层以相应的参数构造一个空的HashMap。 
    * @param initialCapacity 初始容量。 
    * @param loadFactor 加载因子。 
    */  
   public HashSet(int initialCapacity, float loadFactor) {  
   map = new HashMap<E,Object>(initialCapacity, loadFactor);  
   }  
 
   /** 
    * 以指定的initialCapacity构造一个空的HashSet。 
    * 
    * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。 
    * @param initialCapacity 初始容量。 
    */  
   public HashSet(int initialCapacity) {  
   map = new HashMap<E,Object>(initialCapacity);  
   }  
 
   /** 
    * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 
    * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 
    * 
    * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 
    * @param initialCapacity 初始容量。 
    * @param loadFactor 加载因子。 
    * @param dummy 标记。 
    */  
   HashSet(int initialCapacity, float loadFactor, boolean dummy) {  
   map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  
   }  
 
   /** 
    * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 
    *  
    * 底层实际调用底层HashMap的keySet来返回所有的key。 
    * 可见HashSet中的元素，只是存放在了底层HashMap的key上， 
    * value使用一个static final的Object对象标识。 
    * @return 对此set中元素进行迭代的Iterator。 
    */  
   public Iterator<E> iterator() {  
   return map.keySet().iterator();  
   }  
 
   /** 
    * 返回此set中的元素的数量（set的容量）。 
    * 
    * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
    * @return 此set中的元素的数量（set的容量）。 
    */  
   public int size() {  
   return map.size();  
   }  
 
   /** 
    * 如果此set不包含任何元素，则返回true。 
    * 
    * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 
    * @return 如果此set不包含任何元素，则返回true。 
    */  
   public boolean isEmpty() {  
   return map.isEmpty();  
   }  
 
   /** 
    * 如果此set包含指定元素，则返回true。 
    * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) 
    * 的e元素时，返回true。 
    * 
    * 底层实际调用HashMap的containsKey判断是否包含指定key。 
    * @param o 在此set中的存在已得到测试的元素。 
    * @return 如果此set包含指定元素，则返回true。 
    */  
   public boolean contains(Object o) {  
   return map.containsKey(o);  
   }  
 
   /** 
    * 如果此set中尚未包含指定元素，则添加指定元素。 
    * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2)) 
    * 的元素e2，则向此set 添加指定的元素e。 
    * 如果此set已包含该元素，则该调用不更改set并返回false。 
    * 
    * 底层实际将将该元素作为key放入HashMap。 
    * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key 
    * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true）， 
    * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变， 
    * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中， 
    * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。 
    * @param e 将添加到此set中的元素。 
    * @return 如果此set尚未包含指定元素，则返回true。 
    */  
   public boolean add(E e) {  
   return map.put(e, PRESENT)==null;  
   }  
 
   /** 
    * 如果指定元素存在于此set中，则将其移除。 
    * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e， 
    * 则将其移除。如果此set已包含该元素，则返回true 
    * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。 
    * 
    * 底层实际调用HashMap的remove方法删除指定Entry。 
    * @param o 如果存在于此set中则需要将其移除的对象。 
    * @return 如果set包含指定元素，则返回true。 
    */  
   public boolean remove(Object o) {  
   return map.remove(o)==PRESENT;  
   }  
 
   /** 
    * 从此set中移除所有元素。此调用返回后，该set将为空。 
    * 
    * 底层实际调用HashMap的clear方法清空Entry中所有元素。 
    */  
   public void clear() {  
   map.clear();  
   }  
 
   /** 
    * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。 
    * 
    * 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到  HashSet中。 
    */  
   public Object clone() {  
       try {  
           HashSet<E> newSet = (HashSet<E>) super.clone();  
           newSet.map = (HashMap<E, Object>) map.clone();  
           return newSet;  
       } catch (CloneNotSupportedException e) {  
           throw new InternalError();  
       }  
   }  
}

HashSet 特点

• 非线程安全
• 允许 null 值
• 添加值得时候会先获取对象的 hashCode 方法，如果 hashCode 方法返回的值一致，则再调用 equals 方法判断是否一致，如果不一致才 add 元素。

解析

add()

HashSet 里面的 add 方法使用的就是 HashMap 的 put 方法，map.put(e,PRESENT)==null; 将要存入的集合元素作为键，然后把 PRESENT 这个虚拟对象作为值，而这个值是一个固定常量。

查重

HashSet 查重的话，应该就是利用到了 HashMap 的键唯一性来去重，新的元素会覆盖掉旧的元素，== 号的判断结果来确定是否包含要添加的元素，不包含就添加元素并返回 true，包含就忽略此添加操作并返回 false，从而保证了 HashSet 中元素的唯一性。

HashSet 的实现

HashSet 实际上是基于 HashMap 实现的，它只使用了 HashMap 的键来存储数据。在 HashSet 中，元素被存储为 HashMap 的键，而值都是固定的一个常量对象。

因此，当我们向 HashSet 添加元素时，实际上是将这个元素作为键，常量对象作为对应的值存储在 HashMap 中。

在 HashSet 中，唯一性是通过 HashMap 中键的唯一性保证的，因为 HashMap 的键是唯一的。当我们使用 HashSet 来存储元素时，实际上是在利用 HashMap 的去重特性来保证 HashSet 中的元素唯一性。

参考

https://blog.csdn.net/fighterandknight/article/details/66585997