day16_Set

今日内容

零、复习昨日
一、Set
二、Map

零、复习昨日

集合特点
长度不固定
存储的数据类型不限制
有丰富api方法可以调用
有些有序,无序,或者有些允许重复有些会去重

集合体系图
List 集合, 规定了所存储的元素有序且允许重复
常用的ArrayList
底层是数组,初始容量10
存满后扩容,1.5倍
查询或更新快

LinkedList
底层是双向链表
查找,更新较慢, 插入,删除较快

一、Set

Set是Collection的子接口
规定所存储的元素是不允许重复,且无序
HashSet的无序是将存储的元素随机排序
TreeSet的"无序" 是指将存储的元素给排序了

Set接口一般常用两个实现类
HashSet,存储的元素是无序且去重
TreeSet,存储的元素是去重且排序

二、HashSet

是Set接口的实现类,存储的元素是无序且去重,不保证线程安全

2.1 方法演示

HashSet() 空参构造,创建空集合

HashSet(Collection c) 创建带有元素的集合

方法都是常规方法,没有关于下标的操作

    public static void main(String[] args) {
        // 创建空集合
        HashSet<Integer> set = new HashSet<>( );
        System.out.println("初始空集合:" + set );

        // 添加元素(去重,且无序)
        boolean r1 = set.add(31);
        System.out.println("第1次添加元素:" + r1 );
        boolean r2 = set.add(31);
        System.out.println("第12次添加相同元素:" + r2 );

        set.add(21);
        set.add(11);
        set.add(51);
        set.add(41);
        System.out.println("加入元素后:" + set );

        int size = set.size( );
        System.out.println("集合大小:" + size );

        System.out.println("是否为空: "+ set.isEmpty() );

        System.out.println("是否包含:" + set.contains(11) );

        // set.clear();
        // System.out.println("清空集合后:"+ set );

        // 遍历
        for (Integer s : set){
            System.out.println(s );
        }
        // 通过指定集合创建Set
        HashSet<Integer> set2 = new HashSet<>(set);
        System.out.println("set2初始:" + set2 );
    }

2.2 底层实现原理

HashSet底层是HashMap,HashMap的底层实现是哈希表

// 创建HashSet时,会创建HashMap

// 向hashSet中存储元素,其实向HashMap中存储

HashSet(或者底层HashMap)创建时,默认容量是16,加载因子0.75

容量就是存储的个数
加载因子的作用是控制扩容的时机

什么时候触发开始扩容?

当存储的元素达到初始容量*加载因子时,即达到16 X 0.75 = 12,就会扩容,扩容成原来的2倍

通过调整初始容量和加载因子改变性能,但是建议是不要改

ps: hashMap的底层原理在jdk1.8后变样了,比较复杂,后续发资料

2.3 去重原理

需求: 创建学生类,定义2个属性,定义有参无参构造方法, 创建HashSet集合,泛型指定成Student,存储5个学生, 要求存储的学生如果属性一致要去重

// 学生类,正常的属性,封装,构造,toString

public class Student {

    private int age;
    private String name;
    // 略
}

// 测试

  public static void main(String[] args) {
        HashSet<Student> set = new HashSet<>( );
        set.add(new Student(18,"老王"));
        set.add(new Student(18,"老王"));
        set.add(new Student(19,"老李"));
        set.add(new Student(19,"老李"));
        set.add(new Student(20,"老刘"));
        set.add(new Student(20,"老刘"));

        for (Student student : set) {
            System.out.println(student );
        }
    }

// 结果是没有去重

为什么没有去重,通过源码发现,

存储的学生对象,其实是存储的存到hashmap的键上
然后通过存储的对象调用了hashcode方法,获得了地址值,但是学生类没有重写hashCode方法,所以调用的Object类的hashCode()方法,Object类的hashCode()方法是返回的对象地址,又因为每new一次地址值都不一样,所以即返回的每个对象地址值都不一样
然后继续,发现源码中有当正在存储的元素与集合中已经存在元素地址值如果相等时会再判断元素的equals方法
但是我们存储的元素的地址值都不一样,所以不会调用equals方法就直接存储到集合中了

去重原理:

先调用存储的元素的hashcode方法,获得哈希值
然后与集合中的元素的**地址值判断,如果不一样直接存储**
如果存储的元素的地址值与集合中存在的元素的**地址值一样,再比较equals方法**,判断对象属性是否相同
如果**equals也判断相同,即认为重复,不存储**
如果**equals判断不相同,即认为不重复,存储**

2.4 总结

记住HashSet会去重,想要去重记得重写hashCode和equals方法即可

至于原理,怎么做到去重的会说就行!(面试)

三、TreeSet

TreeSet是Set集合的实现类,也是不允许重复元素,但是它存储的元素有序!!会对存储的元素默认按照自然顺序排序,另外此类也是不保证线程安全

TreeSet底层是TreeMap

3.1 演示方法

大部分方法都是常规方法,正常使用(添加,遍历,删除,大小,清空…)

 public static void main(String[] args) {
        // 使用空参构造创建TreeSet集合
        // 没有指定排序规则,默认是按照元素的自然顺序排序
        TreeSet<Integer> ts = new TreeSet<>( );
        /**
         * 去重,且排序
         */
        ts.add(3);
        ts.add(3);
        ts.add(2);
        ts.add(5);
        ts.add(1);
        ts.add(4);

        for (Integer i : ts) {
            System.out.println(i );
        }
    }

3.2 排序去重的原理

需求: 创建学生类,定义2个属性,定义有参无参构造方法, 创建TreeSet集合,泛型指定成Student,存储5个学生, 要求存储的学生如果属性一致要去重,按照年龄从小到大

发现无法去重,报错!!!

要想利用TreeSet排序,存储的元素必须实现Comparable接口,重写comparTo方法
当调用add方法存储元素时,会调用元素的comparTo进行运算
1. 如果返回负数,放在二叉树左侧
2. 如果返回正数,放在二叉树右侧
3. 如果返回0,去除元素不放

// 学生类

public class Student implements Comparable<Student>{

    private int age;
    private String name;
    
    // set get 构造略写

    /**
     * compareTo方法的返回值决定了元素的顺序以及是否去重
     *
     * 返回值为 0 直接去重
     * 返回值为 负数 放根节点左侧
     * 返回值为 正数 放根节点右侧
     * -------------------------
     * 存储完,树按照中序遍历取值
     *------------------
     * o是树结构上以前存储过的元素
     * this是当前正在存的元素
     */
    @Override
    public int compareTo(Student o) {
        System.out.println("this:" + this );
        System.out.println("o:" + o );
        return  o.getAge() - this.getAge();
    }
}

// 测试

 public static void main(String[] args) {
        TreeSet<Student> ts = new TreeSet<>( );
        ts.add(new Student(18,"老王1"));
        ts.add(new Student(18,"老王2"));
        ts.add(new Student(19,"老李3"));
        ts.add(new Student(19,"老李4"));
        ts.add(new Student(20,"老刘5"));
        ts.add(new Student(20,"老刘6"));
        for (Student s : ts) {
            System.out.println(s );
        }
    }

总结: 以后想要利用TreeSet进行排序去重,那么就得实现Comparable接口,重写comparTo方法,根据情况去写算法(确定如何正负零,可以试出来)

3.3 自然排序&比较器排序[扩展|了解]

自然排序其实就是指实现了Comparable接口的,创建TreeSet集合时不指定排序规则,默认就是就这种自然排序

比较器排序, 在创建集合时传入自定义的比较器对象,存储元素时就会使用自定义的方法实现排序

演示: 自定义整型比较器,实现对存储整型Integer去重且倒序

// 自定义整型比较器

public class MyIntegerComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

// 创建集合时存入该比较器对象

public static void main(String[] args) {  
    // 创建集合时存入该比较器对象
	TreeSet<Integer> set = new TreeSet<>(new MyIntegerComparator());
        set.add(3);
        set.add(3);
        set.add(2);
        set.add(5);
        set.add(1);
        set.add(4);

        System.out.println(set );
    }

总结:

自然排序简单,且jdk中默认是使用这种,一般都是从小到大
比较器排序,更灵活,可以自定义规则
自然排序是需要类实现Comparable接口的,但是如果说源码无法改动,即无法实现Comparable接口完成排序,此时就可以使用比较器排序

四、Map

4.1 Map介绍

Map是一种映射关系的集合,能从键映射到值,它是一种特殊的集合,一次存储一对元素(键值对),即Map是双列集合

ps: 映射理解为就是查找

Map中不能包含重复的key(键)
Map中一个key只能找到一个值 (键找值)
Map中无法通过值找键的

Map是双列集合的接口,一般常用的是两个实现类: HashMap,TreeMap

4.2 HashMap[重点]

HashMap是Map的实现,

底层是基于Hash表(jdk1.8以后底层是数组+链表+红黑树)
允许存储null值null键
HashMap不保证线程安全
Hashtable是线程安全的,不允许null值null键,除此之外与HashMap

// 演示方法使用

    public static void main(String[] args) {
        // 创建空的map集合
        HashMap<Integer, String> map = new HashMap<>( );
        // 添加元素(键不允许重复,值可以重复)
        // 元素是无序
        String v1 = map.put(2, "二");
        System.out.println(v1 );// null,返回的是此key所对应之前的value

        String v2 = map.put(2, "贰");
        System.out.println(v2 );// 二

        map.put(22, "贰");
        map.put(32, "贰");
        map.put(42, "贰");
        map.put(52, "贰");
        // 输出结果
        System.out.println(map );

        // v get(Object key) // 通过键找值
        String v = map.get(22);
        System.out.println(v );

        // 判断是否包含某个键
        System.out.println(map.containsKey(22));
        // 判断是否包含某个值
        System.out.println(map.containsValue("22"));

        // 集合大小(尺寸),元素个数
        System.out.println(map.size() );

        // 根据键删除整个键值对,返回v
        String remove = map.remove(22);
        System.out.println("删除键22,返回对应的值:"+remove );
        System.out.println("删除后:" + map );

        // 清空集合
        map.clear();
        System.out.println("清空后:" + map );
    }

4.3 迭代遍历[重点]

Map集合没有提供直接的遍历Map集合的方法,但是提供了

键集 Set keySet(),专门遍历键
值集 Collection values.专门遍历值
键值映射集 Set<Map.Entry<K,V>> entrySet,专门遍历键值对

演示遍历值集

		HashMap<String,Integer> map = new HashMap<>( );
        map.put("A",1);
        map.put("B",2);
        map.put("C",3);
        map.put("D",4);

        // 获得键的集合
        Set<String> keySet = map.keySet();
        // 遍历集合,得到所有的键
        for(String key:keySet){
            System.out.println(key );
        }

演示遍历值集

		// 获得值的集合
        Collection<Integer> values = map.values( );
        // 遍历
        for (Integer v : values){
            System.out.println(v );
        }

演示遍历键值映射集合

		// 获得键值映射集合
        // Map.Entry是Map内的内部接口,代表一项键值对
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        // 遍历
        for(Map.Entry<String,Integer> entry : entrySet) {
            String key = entry.getKey( );
            Integer value = entry.getValue( );
            System.out.println(key+"="+value );
        }

五、总结重点

今天重点

记住HashSet的去重无序效果,熟练使用常用方法api即可
记住HashMap的特点,熟练使用方法,以及三种遍历方式
读背 hashset去重原理,treeset排序去重原理
// Map.Entry是Map内的内部接口,代表一项键值对
Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
// 遍历
for(Map.Entry<String,Integer> entry : entrySet) {
String key = entry.getKey( );
Integer value = entry.getValue( );
System.out.println(key+“=”+value );
}
``