Day17_Set集合

一.Set集合

1.Set集合概述及其特点

public interface Set<E> extends Collection<E>,不包含重复元素的

List----存储顺序与取出顺序一致，可重复
Set----无序，存储和取出顺序不一致，唯一（比如哈希表的key是不会重复的）

HashSet（Set的实现子类）：不保证set的迭代顺序：特别是它不保证该顺序永久不变

二.HashSet

1.HashSet存储字符串并遍历

HashSet<String> hs = new HashSet<String>();
        hs.add("a");
        hs.add("b");
        hs.add("c");
        hs.add("a");

        for (String s : hs)
        {
            System.out.println(s);//a b c唯一性
        }

2.HashSet保证元素唯一性源码

interface Collection {
    ...
}

interface Set extends Collection {
    ...
}

class HashSet implements Set {
    private static final Object PRESENT = new Object();
    private transient HashMap<E,Object> map;
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) { //e=hello,world
        return map.put(e, PRESENT)==null;
    }
}

class HashMap implements Map {
    public V put(K key, V value) { //key=e=hello,world
    
        //看哈希表是否为空，如果空，就开辟空间
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        
        //判断对象是否为null
        if (key == null)
            return putForNullKey(value);
        
        int hash = hash(key); //和对象的hashCode()方法相关
        
        //在哈希表中查找hash值
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            //这次的e其实是第一次的world
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
                //走这里其实是没有添加元素
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
 //把元素添加
        return null;
    }
    
    transient int hashSeed = 0;
    
    final int hash(Object k) { //k=key=e=hello,
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode(); //这里调用的是对象的hashCode()方法

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
}


hs.add("hello");
hs.add("world");
hs.add("java");
hs.add("world");

也就是重复元素不会被添加（哈希值相同&&（key地址值相同 || key内容相同）时）

 * 步骤：
 *      首先比较哈希值
 *      如果相同，继续走，比较地址值或者走equals()
 *      如果不同,就直接添加到集合中  
 * 按照方法的步骤来说：   
 *      先看hashCode()值是否相同
 *          相同:继续走equals()方法
 *              返回true： 说明元素重复，就不添加
 *              返回false：说明元素不重复，就添加到集合
 *          不同：就直接把元素添加到集合
 * 如果类没有重写这两个方法，默认使用的Object()。一般来说不同相同。
 * 而String类重写了hashCode()和equals()方法，所以，它就可以把内容相同的字符串去掉。只留下一个。

以存储自定义对象为例

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Student other = (Student) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

哈希表.png

HashSet底层是哈希表结构，而哈希表结构底层依赖：hashCode()和equals()方法,如果你认为对象的成员变量值相同就是同一对象的话，你就应该重写这两个方法，可以自动生成

三.LinkedHashSet概述

HashSet的子类
特点：有序，数据结构：哈希表和链表，元素唯一

四.TreeSet类

1.概述和遍历1

public class TreeSet<E> extends AbstractSet;使用元素的 a 自然顺序对元素进行排序或根据创建set时提供的 b Comparator比较器排序，具体取决于使用的构造方法
自然排序(使用TreeSet的无参构造函数时候是根据元素自然顺序来排序)

TreeSet<Integer> hs = new TreeSet<Integer>();
        hs.add(12);
        hs.add(6);
        hs.add(56);
        hs.add(45);
        hs.add(12);

        for (Integer i : hs)
        {
            System.out.println(i);
            //唯一性和自然顺序排序
//            6
//            12
//            45
//            56

2.TreeSet保证元素排序源码解析

TreeSet的add方法最终要看TreeMap的put方法，

* interface Collection {...}

interface Set extends Collection {...}

interface NavigableMap {

}

class TreeMap implements NavigableMap {
     public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
//TreeSet的成员变量，无参构造没有初始化它
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
//比较器为空，走无参构造
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
}

class TreeSet implements Set {
    private transient NavigableMap<E,Object> m;
    
    public TreeSet() {
         this(new TreeMap<E,Object>());
    }

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

真正的比较是依赖于元素的compareTo()方法，而这个方法是定义在 Comparable里面的。
所以，你要想重写该方法，就必须是先 Comparable接口。这个接口表示的就是自然排序。

底层是红黑树实现

红黑树.png

3.自定义对象遍历

像上面一样直接遍历会报错
a：没有告诉怎么排序：
b：没有告诉怎么算唯一性：
所以，为了比较自定义对象，必须事项Comparable<Student>接口，重写compareTo方法；它返回一个int值，根据红黑树构造过程，返回负数作为左孩子，正数作为右孩子，相等不添加，按中序遍历输出，return -1就是倒序输出。

@Override
   public int compareTo(Student o) {
//主要条件：按年龄排序
       int num = this.age - o.age;
//次要条件：年龄相同时，对name比较
       if (this.age == o.age)
           num = this.name.compareTo(o.name);
       //String重写了compareTo方法
       return num;
   }

TreeSet<Student> hs = new TreeSet<Student>();
       Student s1 = new Student("linqingxia", 27);
       Student s2 = new Student("zhangguorong", 29);
       Student s3 = new Student("wanglihong", 23);
       Student s4 = new Student("linqingxia", 27);
       Student s5 = new Student("liushishi", 22);
       Student s6 = new Student("wuqilong", 40);
       Student s7 = new Student("fangqingyuan", 40);

       hs.add(s1);
       hs.add(s2);
       hs.add(s3);
       hs.add(s4);
       hs.add(s5);
       hs.add(s6);
       hs.add(s7);

       for (Student i : hs)
       {
           System.out.println(i.getAge() + "  " + i.getName());
       }
22  liushishi
23  wanglihong
27  linqingxia
29  zhangguorong
40  fangqingyuan
40  wuqilong

4.TreeSet有参构造和自定义排序

比较器排序&有参构造
此时需要实现Comparaor接口

建立MyComparaor类
public class MyComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        int num = o1.getAge() - o2.getAge();
        if (o1.getAge() == o2.getAge())
            num = o1.getName().compareTo(o2.getName());
        //String重写了compareTo方法
        return num;
    }
}

TreeSet<Student> hs = new TreeSet<Student>(new MyComparator());
即可


一般一个方法参数是接口，那么真正要的是接口的实现类对象，可以用匿名内部类。这时候该条件直接内部类里该就可以，不影响其他类
TreeSet<Student> hs = new TreeSet<Student>(new Comparator<Student>(){
            @Override
            public int compare(Student o1, Student o2) {
                int num = o1.getAge() - o2.getAge();
                if (o1.getAge() == o2.getAge())
                    num = o1.getName().compareTo(o2.getName());
                //String重写了compareTo方法
                return num;
            }

        });

源码

Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);

TreeSet
TreeSet集合保证元素排序和唯一性的原理
唯一性：是根据比较的返回是否是0来决定。
排序：
A:自然排序(元素具备比较性)
让元素所属的类实现自然排序接口 Comparable,重写compareto方法
B:比较器排序(集合具备比较性)
让集合的构造方法接收一个比较器接口的子类对象 Comparator，重写compare方法