TreeSet课后练习

public class MyDate {
    //三个成员变量year,month,day
    private int year;
    private int month;
    private int day;

    public int getYear() {
        return year;
    }

    public void setYear(int year) {
        this.year = year;
    }

    public int getMonth() {
        return month;
    }

    public void setMonth(int month) {
        this.month = month;
    }

    public int getDay() {
        return day;
    }

    public void setDay(int day) {
        this.day = day;
    }

    public MyDate(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = day;
    }

    public MyDate() {
    }

    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }
}


public class Employee implements Comparable{
    //该类包含三个成员变量name，age，brithday,，其中brithday为MyDate类的对象
    private String name;
    private int age;
    private MyDate brithday;

    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;
    }

    public MyDate getBrithday() {
        return brithday;
    }

    public void setBrithday(MyDate brithday) {
        this.brithday = brithday;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", brithday=" + brithday +
                '}';
    }

    public Employee() {
    }

    public Employee(String name, int age, MyDate brithday) {
        this.name = name;
        this.age = age;
        this.brithday = brithday;
    }

    //按照名称从小到大排序
    @Override
    public int compareTo(Object o) {
        if(o instanceof Employee){
            Employee employee = (Employee) o;
            return this.name.compareTo(employee.name);
        }
//        return 0;
        throw new RuntimeException("传入的数据异常！");
    }
}


public class test {
    public static void main(String[] args) {
        //测试：使用自然排序
        TreeSet set = new TreeSet();
        set.add(new Employee("liangchaowei",56,new MyDate(1986,8,7)));
        set.add(new Employee("liudehua",55,new MyDate(1987,5,4)));
        set.add(new Employee("zhangxueyou",54,new MyDate(1988,9,13)));
        set.add(new Employee("guofucheng",45,new MyDate(1990,4,28)));
        set.add(new Employee("liming",48,new MyDate(1994,10,24)));
        
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //按照生日排序（定制排序）
        Comparator com = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Employee && o2 instanceof Employee){
                    Employee employee1 = (Employee) o1;
                    Employee employee2 = (Employee) o2;
                    if(employee1.getBrithday().getYear()==employee2.getBrithday().getYear()){
                        if(employee1.getBrithday().getMonth()==employee2.getBrithday().getMonth()){
                            return Integer.compare(employee1.getBrithday().getDay(),employee2.getBrithday().getDay());
                        }else {
                            return Integer.compare(employee1.getBrithday().getMonth(),employee2.getBrithday().getMonth());
                        }
                    }else {
                        return Integer.compare(employee1.getBrithday().getYear(),employee2.getBrithday().getYear());
                    }
                }
                throw new RuntimeException("数据输入异常！");
            }
        };
        TreeSet set0 = new TreeSet(com);
        set0.add(new Employee("liangchaowei",56,new MyDate(1986,8,7)));
        set0.add(new Employee("liudehua",55,new MyDate(1987,5,4)));
        set0.add(new Employee("zhangxueyou",54,new MyDate(1988,9,13)));
        set0.add(new Employee("guofucheng",45,new MyDate(1988,9,28)));
        set0.add(new Employee("liming",48,new MyDate(1988,10,24)));

        Iterator iterator1 = set0.iterator();
        System.out.println("======");
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }
    }
}

Set接口练习

练习一

在List内去除重复数字值，要求尽量简单
- 思路：将List转化为HashSet（通过addAll()方法转化），通过HashSet的特性不能有重复的值。来处理。

public class Demo02 {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new Integer(1));
        list.add(new Integer(1));
        list.add(new Integer(2));
        list.add(new Integer(3));
        list.add(new Integer(3));
        list.add(new Integer(4));
        List list1 = duplicateList(list);
        Iterator iterator = list1.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+"\t");//1	2	3	4	(去掉了重复的)
        }
    }
    public static List duplicateList(List list){
        HashSet hashSet = new HashSet();
        hashSet.addAll(list);
        return new ArrayList(hashSet);
    }
}

练习二

public class Person {
    String name;
    int age;

    public Person() {
    }

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

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;

        if (age != person.age) return false;
        return name != null ? name.equals(person.name) : person.name == null;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}
//Person类已经重写hashCode()方法和equals()方法了


//测试类
public class text {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        Person p1 = new Person("AA",1001);
        Person p2 = new Person("BB",1002);

        hashSet.add(p1);
        hashSet.add(p2);
        System.out.println(hashSet);//[Person{name='AA', age=1001}, Person{name='BB', age=1002}]

        p1.name = "CC";
        hashSet.remove(p1);
        System.out.println(hashSet);//[Person{name='CC', age=1001}, Person{name='BB', age=1002}]

        hashSet.add(new Person("CC",1001));
        System.out.println(hashSet);//[Person{name='CC', age=1001}, Person{name='CC', age=1001}, Person{name='BB', age=1002}]
        hashSet.add(new Person("AA",1001));
        System.out.println(hashSet);//[Person{name='CC', age=1001}, Person{name='CC', age=1001}, Person{name='AA', age=1001}, Person{name='BB', age=1002}]
    }
}

Map接口

Map接口继承树

在这里插入图片描述

Map：双列数据，存储key - value对的数据
- HashMap：作为Map的主要实现类；线程不安全的，效率高；可以存储null的key和value。
- ```
 Map map = new HashMap();
        map.put(null,123);
        map.put(null,null);
        System.out.println(map);//{null=null}
        Map map1 = new Hashtable();
        map1.put(null,123);//NullPointerException异常
        map1.put(123,null);//NullPointerException异常
        map1.put(null,null);//NullPointerException异常
        System.out.println(map1);
```
  - LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。好处：对于频繁的遍历操作，此类执行效率高于HashMap。
- TreeMap：按照添加的key - value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序。底层使用红黑树。
- Hashtable：作为古老的实现类；线程安全，效率低；不能存储null的key和value。
  - Properties：常用来处理配置文件，key和value都是String类型
- HashMap的底层：数组 + 链表（jdk 7 之前）
  
  ? 数组 + 链表 + 红黑树（jdk 8 ）

面试题：

HashMap的底层实现原理？
HashMap和Hashtable的异同？
CurrentHashMap 与 Hashtable异同？

Map结构的理解

Map中的key：是无序的，不可重复的，使用Set存储所有的key。这就要求：key所在的类要重写equals()方法和hashCode()（以HashMap为例）
Map中的value：无序的可重复的，使用Collection存储所有的value。这就要求value所在的类要重写equals()
一个键值对：key - value构成了一个Entry对象，
Map中的entry：无序的，不可重复的，使用Set存储所有的entry

在这里插入图片描述

HashMap的底层实现原理（重点）

以 jdk 7 为例说明：

		HashMap map = new HashMap();
//在实例化之后，底层创建了长度是16的一维数组Entry[] table。
//		...可能已经已经执行过多次put...
		map.put(key1,value);
//首先，调用key1所在类的hashCode()计算key1哈希值经过某种算法以后，得到在Entry数组中的存放位置，
//如果此位置上的数据为空，此时的key1 - value1添加成功。 --情况1
//如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据(以链表形式存在)），比较key1和已经存在的一个或多个数据的哈希值：
//		如果key1的哈希值与已经存在的数据的哈希值都不同，此时key1 - valueltion添加成功。	--情况2
//		如果key1的哈希值和已经存在的某一个数据(key2 - value2)的哈希值相同，继续比较：调用key1所在类的equals()方法，比较：
//		如果equals()返回false:此时key1 - value1添加成功。--情况3
//		如果equals()返回true:使用value1替换value2.

//		补充：关于情况2和情况3：此时key1 - value1和原来的数据以链表的方式存储。
//		在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，默认的扩容方式；扩容为原来
//容量的2 倍,并将原有的数据复制过来。

jdk 8 相较于jdk 7在底层实现方面的不同；

new HashMap()：底层没有创建一个长度为16 的数组
jdk 8 底层的数组是：Node[]，而非Entry[]
首次调用put()方法时，底层创建长度为16的数组
jdk 7 底层结构只有：数组 + 链表，jdk 8 中底层结构：数组 + 链表 + 红黑树。当数组某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所有数据改为使用红黑树存储。

HashMap源码中的重要常量

在这里插入图片描述

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOP : HashMap的默认加载因子：0.75
threshold：扩容的临界值，=容量*填充因子：16 * 0.75 = 12
TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值（8），转化为红黑树
MIN_TREEIFY_CAPACITY: 桶中的Node被树化时最小的hash表容量：64

LinkedHashMap的底层实现原理（了解）

public class Demo02 {
    public static void main(String[] args) {
        Map map =new HashMap();
        map.put(123,"AA");
        map.put(345,"BB");
        map.put(12,"CC");
        System.out.println(map);//{345=BB, 123=AA, 12=CC}

        Map map1 = new LinkedHashMap();
        map1.put(123,"AA");
        map1.put(345,"BB");
        map1.put(12,"CC");
        //LinkedHashMap输出时会记录你添加的顺序
        System.out.println(map1);//{123=AA, 345=BB, 12=CC}
    }
}

源码中：

static class Entry<K,V> extends HashMap.Node<K,V>{
    Entry<K,V> before,After;//能够记录添加元素的先后顺序
    Entry(int hash, K key, V value, Node<K,V> next){
        super(hash, key, value,next);
    }
}

Map中定义的方法

添加，删除，修改操作：
- Object put(Object key,Object value)：将指定key - value添加到（或修改）当前map对象中
- void putAll(Map m)：将m中的所有Key - value对存放到当前map中
- Object remove(Object key)：移除指定key的key - value对，并返回value
- void clear()：清空当前map中的所有数据
元素查询的操作：
- Object get(Object key)：获取指定key对应的value
- boolean contiansKey(Object key)：是否包含指定的key
- boolean contiansValue(Object value)：是否包含指定的key
- int size()：返回map中key - value对的个数
- boolean isEmpty()：判断当前map是否为空
- boolean equas(Object obj)：判断当前map和参数对象obj是否相等
元视图操作的方法：
- Set keySet():返回所有key构成的Set集合
- Collection values()：返回所有value构成的Collection集合
- Set entrySet()：返回所有key - value对构成的Set集合
总结：常用方法：
- 添加：put(Object key,Object value)
- 删除： remove(Object key)
- 修改： put(Object key,Object value)
- 查询：get(Object key)
- 长度： size()
- 遍历：KeySet() 、values() 、entrySet()

/*- 添加，删除，修改操作：
          - Object put(Object key,Object value)：将指定key - value添加到（或修改）当前map对象中
          - void putAll(Map m)：将m中的所有Key - value对存放到当前map中
          - Object remove(Object key)：移除指定key的key - value对，并返回value
          - void clear()：清空当前map中的所有数据
*/

Map map =new HashMap();

        //添加
        map.put("AA",123);
        map.put(45,123);
        map.put("BB",56);
        //体现修改
        map.put("AA",87);

        System.out.println(map);//{AA=87, BB=56, 45=123}

        HashMap map1 = new HashMap();
        map1.put("CC",123);
        map1.put("DD",123);

        map .putAll(map1);
        System.out.println(map);//{AA=87, BB=56, CC=123, DD=123, 45=123}

        //remove(Object key)
        Object value = map.remove("CC");
        System.out.println(value);//123
        System.out.println(map);//{AA=87, BB=56, DD=123, 45=123}

        //clear():清空里面的数据
        map.clear();//map = null
        System.out.println(map.size());//0
        System.out.println(map);//{}

public class Demo04 {
    public static void main(String[] args) {
        /*
        - 元素查询的操作：
          - Object get(Object key)：获取指定key对应的value
          - boolean contiansKey(Object key)：是否包含指定的key
          - boolean contiansValue(Object value)：是否包含指定的key
          - int size()：返回map中key - value对的个数
          - boolean isEmpty()：判断当前map是否为空
          - boolean equas(Object obj)：判断当前map和参数对象obj是否相等
         */

        Map map =new HashMap();
        map.put("AA",123);
        map.put(45,123);
        map.put("BB",56);

        //Object get(Object key)
        System.out.println(map.get(45));//123

        //contiansKey(Object key)
        boolean bb = map.containsKey("BB");
        System.out.println(bb);//true

        //contiansValue(Object value)
        boolean b = map.containsValue(123);//有两个值，他找到一个了，就不会接着往下找
        System.out.println(b);//true

        //isEmpty()
        map.clear();
        System.out.println(map.isEmpty());//true
    }
}

public class Demo05 {
    public static void main(String[] args) {
        /*
             - 元视图操作的方法：
          - Set keySet():返回所有key构成的Set集合
          - Collection values()：返回所有value构成的Collection集合
          - Set entrySet()：返回所有key - value对构成的Set集合
         */
        Map map =new HashMap();
        map.put("AA",123);
        map.put(45,123);
        map.put("BB",56);
        //遍历所有的key集，KeySet()
        Set set = map.keySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //遍历所有的value集：values()
        Collection values = map.values();
        for (Object value : values) {
            System.out.println(value);
        }

        //遍历所有的Key - value
        //方式一： entrySet()
        Set set1 = map.entrySet();
        Iterator iterator1 = set1.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry)obj;
            System.out.println(obj);
            System.out.println(entry.getKey()+"--->"+entry.getValue());
            /*
            AA=123
            AA--->123
            BB=56
            BB--->56
            45=123
            45--->123
             */
        }
        //方式二：
        Set set2 = map.keySet();
        Iterator iterator2 = set1.iterator();
        System.out.println("======");
        while (iterator2.hasNext()){
            Object Key = iterator2.next();
            Object value = map.get(Key);
            System.out.println(Key+"====="+value);
        }
    }
}