0061 Set接口

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/*
    Set接口
    1.无序（添加和取出的顺序不一样），没有索引
    2.不允许重复元素，最多包含一个null
    3.实现类主要有 TreeSet，HashSet....

    常用方法
    Set接口也是Collection的子接口，因此方法和Collection接口一样

    遍历方式（不能使用索引的方式来获取）
    1.使用迭代器
    2.增强for
 */
@SuppressWarnings({"all"})
public class Set_ {
    public static void main(String[] args) {
        Set set = new HashSet();//以Set接口的实现类HashSet来演示方法
        set.add("john");
        set.add("lucy");
        set.add("john");//重复
        set.add("jack");
        set.add("mary");
        set.add(null);//
        set.add(null);// 再次添加 null
        //存放无序，且不允许重复元素，最多包含一个null
        System.out.println("set=" + set);//set=[null, mary, john, lucy, jack]

        //遍历
        System.out.println("=====使用迭代器=====");
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            System.out.println("obj=" + obj);
        }

        System.out.println("=====增强for=====");
        for (Object obj : set) {
            System.out.println("obj=" + obj);
        }
    }
}

import java.util.HashSet;

/*
     HashSet
     1.HashSet实现了Set接口
     2.HashSet实际上是HashMap
     3.可以存放null，但最多只能存放一个，不能有重复元素
     4.HashSet不保证元素是有序的

 */
@SuppressWarnings({"all"})
public class Set02 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
    /*      构造器源码
            public HashSet() {
                map = new HashMap<>();
            }HashSet实际上是HashMap
    */
        hashSet.add(null);
        hashSet.add(null);
        //可以存放null，但最多只能存放一个，不能有重复元素
        System.out.println(hashSet);//[null]

        HashSet set = new HashSet();
        set.add("lucy");
        set.add("lucy");
        set.add(new Dog("tom"));
        set.add(new Dog("tom"));//添加成功
        System.out.println("set=" + set);//set=[tom, tom, lucy]

        set.add(new String("huang"));
        set.add(new String("huang"));//添加失败-->底层机制
        System.out.println("set=" + set);//set=[tom, tom, lucy, huang]
    }
}

class Dog {
    private String name;
    public Dog(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return name;
    }
}

/*
    HashSet底层是HashMap，HashMap底层是（数组+链表+红黑树）
 */
//模拟底层 数组+链表结构
@SuppressWarnings({"all"})
public class Set03 {
    public static void main(String[] args) {
        //创建数组，类型Node[]
        Node[] table = new Node[16];
        System.out.println(table);
        //创建结点
        Node node1 = new Node("jack", null);
        table[2] = node1;//把node1放到table表索引为2的位置
        Node node2 = new Node("mary", null);
        node1.next = node2;//将node1结点挂载到node2
        Node node3 = new Node("smith", null);
        node2.next = node3;//将node2结点挂载到node3

        Node node4 = new Node("lucy", null);
        table[3] = node4;//把node4放到table表索引为3的位置
        System.out.println(table);
    }
}
class Node{//创建结点
    Object item;//存放数据
    Node next;//指向下一结点

    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }
}

import java.util.HashSet;

/*
    HashSet源码解读
      1.添加一个元素时，先得到hash值，会转成索引值
    2.找到存储数据表table，看这个索引位置是否已存入元素
      如果没有则直接加入
      如果有，调用equals比较，如果相同，则放弃添加，如果不相同，则添加到最后（.next）
    3.第一次添加时，table数组扩容到16，临界值是16*加载因子（0.75）=12
      如果table数组到了临界值12，就会扩容到16*2=32，新的临界值为32*0.75=24，以此类推..
    4.在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认为8），且table大小>=MIN_TREEIFY_CAPACITY(默认64)
      就会进行树化（红黑树），否则仍然采用数组扩容机制
 */
@SuppressWarnings({"all"})
public class Set04 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");//
        hashSet.add("hello");
        hashSet.add("java");
        System.out.println("set=" + hashSet);
    }
}
/*
        1.执行 HashSet()
        public HashSet() {
        map = new HashMap<>();
        }

        2. 执行 add()
        public boolean add(E e) {//e = "java"
        return map.put(e, PRESENT)==null;   //(static) PRESENT = new Object();
         }

        3.执行 put(),该方法会执行 hash(key) 得到 key 对应的 hash 值 算法 h = key.hashCode()) ^ (h >>> 16)
         public V put(K key, V value) {//key = "java", value = PRESENT 共享
         return putVal(hash(key), key, value, false, true); }

        4.执行 putVal
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;//定义了辅助变量
        //table就是HashMap的一个数组，类型是Node[]
        //if语句表示当前table为Null或大小为0，则第一次扩容，16个空间
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //根据key得到hash，计算该key应存放到table表的哪个索引位置，并把这个位置的对象赋给p
        //判断p是否为空，如果为空，则创建一个Node（key="java",value=PRESENT）
        //放在该位置tab[i] = newNode(hash, key, value, null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;//定义辅助变量
            //如果当前索引位置对应的链表的第一个元素和准备添加的key和hash一样
            //且满足准备加入的key和p指向Node结点的key是同一个对象
            //或p指向Node结点的key的equals()和准备的加入key相同
            //就不能加入
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断p是不是一颗红黑树，如果是，则调用putTreeVal来添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            //如果table对应索引位置，已经为一个链表，就使用for循环比较
            //依次和每一个元素比较，如果都不相同，则加入链表的最后
            //立即判断该链表是否已达到8个结点，调用treeifyBin，对当前这个链表进行树化
            //树化时进行判断
            //if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
            //                  resize();
            //如果上面条件成立，先 table 扩容
            //只有上面条件不成立时，才进行转成红黑树
            //如果有相同的，直接break
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//修改次数
        //size 就是我们每加入一个结点 Node(k,v,h,next), size++
        if (++size > threshold)
            resize();//扩容
        afterNodeInsertion(evict);
        return null;
    }

 */

import java.util.HashSet;
import java.util.Objects;
/*
    HashSet练习1
    定义一个Employee类，包含private成员属性name，age
    要求创建三个Employee对象放入HashSet中
    当name和age值相同时，认为是同一个员工，不能添加到HashSet集合中
 */
@SuppressWarnings({"all"})
public class Set05 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("jack",18));
        hashSet.add(new Employee("john",18));
        hashSet.add(new Employee("jack",18));
        System.out.println(hashSet);

    }
}
class Employee{
    private String name;
    private int age;
    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    //因为hash值不同，所以有三个对象--->重写hashCode
    //重写equals和hashCode
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age &&
                Objects.equals(name, employee.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

import java.util.LinkedHashSet;
import java.util.Set;
/*
    LinkedHashSet
    1.LinkedHashSet是HashSet的子类
    2.LinkedHashSet底层是一个LinkedHashMap，底层维护了一个 数组+双向链表（pre,next）
    3.LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序
      使元素看起来是以插入顺序来保存的
    4.LinkedHashSet不允许添加重复元素
 */
@SuppressWarnings({"all"})
public class Set06 {
    public static void main(String[] args) {
        Set set = new LinkedHashSet();
        set.add(123);
        set.add(456);
        set.add(123);
        set.add("jack");
        set.add(789);
        System.out.println(set);//[123, 456, jack, 789]
        //加入顺序和取出元素顺序一致
    }
}