重学JavaSE —— Map、Set、Iterator(迭代器) 简单笔记

前言

本文是学习笔记,也有配套源码实例,主要是针对本人对Map、Set、Iterator进行的简单学习和笔记总结。

本文源代码已上传至Gitee:https://gitee.com/da-ji/full-stack-developer,大家需要可自取

集合类的继承关系

下面的文章和图片展示了所有集合类的继承关系!

https://blog.csdn.net/weixin_50999696/article/details/115410914

在这里插入图片描述

Map

分为:HashMap、Hashtable、LinkedHashMap和TreeMap
参考文章:
https://zhuanlan.zhihu.com/p/21673805

HashMap

参考文章:写的很明白:https://baijiahao.baidu.com/s?id=1719030639741078030&wfr=spider&for=pc
看完了这个之后,看美团技术团队出品的下篇:https://zhuanlan.zhihu.com/p/21673805

重点看(https://zhuanlan.zhihu.com/p/21673805): 分析HashMap的put方法 这一章

相关重点概念介绍:

其实底层就是 哈希桶数组+链表+红黑树

  • 哈希桶数组(Node[] table)
    • 这个数组就是一个单纯的数组,只不过存放的数据类型是 哈希桶 类型
    • 这个数组其实与HashMap的容量密切相关,它用光之后可以扩容
    • HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。
    • HashMap初始默认长度为16且长度必须是2的幂的原因,也在上面的漫画中解释了
  • LoadFactor
    • 默认为0.75 : static final float DEFAULT_LOAD_FACTOR = 0.75f;
    • 它决定HashMap所能容纳的最大数据量的Node(键值对)个数。在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。
    • 如果HashMap一直put(),直到超过了最大数据量,那么就会自动进行扩容
  • 哈希函数(哈希算法)
    • 当 put() 时,根据键key来调用Hash函数计算出其对应的哈希值 —— 就是【哈希桶数组】中的索引i
    • 然后该元素就插入到【哈希桶数组】的第i号位置。
    • Hash算法的选择决定了Hash冲突的概率,Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。
  • 哈希碰撞
    • 上面的哈希算法,可能不同的key计算出了同一个【哈希桶数组】的内存位置。
      • 比如key为”monkey”和key为”tiger”的两个键,都映射到了【哈希桶数组】的第6号位置。
    • 这就是哈希碰撞。解决的方法就是 【链表】+【红黑树】。
    • 遍历哈希桶数组table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

线程安全性:

在多线程使用场景中,应该尽量避免使用线程不安全的HashMap,而使用线程安全的ConcurrentHashMap。

TreeMap

参考文章:
https://zhuanlan.zhihu.com/p/76740300

TreeMap 和 HashMap 的区别

/**
* TreeMap 和 HashMap 的区别
* 他俩最大的区别是:TreeMap是有序的。
* TreeMap它是有序的Map,这个有序不是说它按照插入元素的顺序来排序,而是按key值来递增排序
* 对于key是Integer类对象时,是按照数值大小递增顺序排的,而自定义的类的对象,如果要比较大小,必须实现Comparable接口,重写compareTo方法。
* 我们自定义的类的对象也可以比较大小——通过Comparable接口的compareTo重写方法来实现自定义排序。
*
*
* 假如key不可比较,那么就不能向TreeMap中塞入该key。
* 假如key不可比较,那么就不能向TreeMap中塞入该key。
* 假如key不可比较,那么就不能向TreeMap中塞入该key。
* 假如key不可比较,那么就不能向TreeMap中塞入该key。
*/

    @Test
    void test1() {
        Map<Integer, String> treemap = new TreeMap<>();
        treemap.put(2, "hello");
        treemap.put(3, "world");
        treemap.put(1, "!");
        //测试输出TreeMap的排序是按照Key递增顺序排的
        for (Integer key : treemap.keySet()) {
            System.out.println(key + "-->value:" + treemap.get(key));
        }
// TODO 注意! 这个UserPojo已经实现了Comparable接口,所以这里按照我给的顺序塞入treemap并成功按顺序打印!
        UserPojo m1 = new UserPojo(1, "lbw", "山东省青岛市", 19);
        UserPojo m2 = new UserPojo(2, "lbw2", "山东省济南市", 20);
        UserPojo m3 = new UserPojo(3, "lbw3", "北京市", 22);
        UserPojo m4 = new UserPojo(4, "lbw4", "上海市", 23);

        Map<UserPojo, String> treemap1 = new TreeMap<>();
        treemap1.put(m1, "m1");
        treemap1.put(m2, "m2");
        treemap1.put(m3, "m3");
        treemap1.put(m4, "m4");
        //测试输出TreeMap的排序按照key对象的排序方法递增排序
        Set<Map.Entry<UserPojo, String>> entries = treemap1.entrySet();
        for (Map.Entry<UserPojo, String> entry : entries) {
            System.out.println("该Map遍历后的键值对key是:"+entry.getKey()+";value是:"+entry.getValue());
        }


        System.out.println("=========分割线,上面会打印,但是下面就报错了===============");
        System.out.println("=========分割线,上面会打印,但是下面就报错了===============");
        System.out.println("=========分割线,上面会打印,但是下面就报错了===============");

        Map<WithoutCompareTo_User, String> treemap2 = new TreeMap<>();
        //TODO 报错!原因是因为,key没有实现Comparable接口,没有重写 CompareTo方法。
        // java.lang.ClassCastException: com.daji.pojo.WithoutCompareTo_User cannot be cast to java.lang.Comparable
        // 因此TreeMap不知道该如何排序。所以报错
        treemap2.put(new WithoutCompareTo_User(1, "lbw", "山东省青岛市", 19),"m1");
        treemap2.put(new WithoutCompareTo_User(2, "lbw2", "山东省济南市", 20),"m2");
        treemap2.put(new WithoutCompareTo_User(3, "lbw3", "北京市", 22),"m3");
        treemap2.put(new WithoutCompareTo_User(4, "lbw4", "上海市", 23),"m4");

        Set<Map.Entry<UserPojo, String>> entries0 = treemap1.entrySet();
        for (Map.Entry<UserPojo, String> entry : entries0) {
            System.out.println("该Map遍历后的键值对key是:"+entry.getKey()+";value是:"+entry.getValue());
        }

    }

Set

HashSet,和TreeSet的底层是基于HashMap和TreeMap来实现的。

基本上是调用了HashMap和TreeMap的方法。

值得一提的是,Map想要使用Iterator迭代器进行遍历,需要将其转换成单列集合Set。使用Map.keySet()和 Map.entrySet()就可以做到。

既然它们和Map差不多,那我们就看看Set对比List吧。

  • 效率上:Set和List对比:
    Set:查找元素效率低,增删元素效率高。插入和删除不会引起元素位置改变。
    List:查找元素效率高,增删元素效率低。
  • 唯一性(不可重复性)这个不可重复性,由Object.equals,和 Object.hashCode这两个方法来保证。可以重写这两个方法来重新定义“对象重复” 这个概念。
  • 无序性。存取和插入顺序不一。也因此它无法调用.get(i)来进行下标式访问。(但是TreeSet有序!)
    • TreeSet底层数据结构采用TreeMap红黑树来实现,元素唯一且已经排好序;唯一性同样需要重写hashCode和equals()方法,二叉树结构保证了元素的有序性。根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造),自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法,元素通过比较返回的int值来判断排序序列,返回0说明两个对象相同,不需要存储;比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象,或者采用匿名内部类的方式new一个Comparator对象,重写里面的compare()方法;

TreeSet有序性的实例:

/**
     * TreeSet的特性,被塞入的元素必须实现Comparable接口,重写compareTo方法。
     * TreeSet是有序不重复的。
     */
    @Test
    void test2() {
        Set<UserPojo> tree=new TreeSet();
        tree.add(new UserPojo(1, "lbw", "山东省青岛市", 19));
        tree.add(new UserPojo(2, "lbw2", "山东省济南市", 20));
        tree.add(new UserPojo(3, "lbw3", "北京市", 22));
        tree.add(new UserPojo(4, "lbw4", "上海市", 23));
        System.out.println("元素对象多少个"+tree.size());
        for (UserPojo userPojo : tree) {
            System.out.println(userPojo);
        }

        System.out.println("=========分割线,上面会打印,但是下面就报错了===============");
        System.out.println("=========分割线,上面会打印,但是下面就报错了===============");
        System.out.println("=========分割线,上面会打印,但是下面就报错了===============");

        Set<WithoutCompareTo_User> tree0=new TreeSet();
        //TODO java.lang.ClassCastException: com.daji.pojo.WithoutCompareTo_User cannot be cast to java.lang.Comparable
        //TODO 为什么报错?因为添加的是对象元素,必须实现一个排序,否则就会类型转换错误的问题
        tree0.add(new WithoutCompareTo_User(1, "lbw", "山东省青岛市", 19));
        tree0.add(new WithoutCompareTo_User(2, "lbw2", "山东省济南市", 20));
        tree0.add(new WithoutCompareTo_User(3, "lbw3", "北京市", 22));
        tree0.add(new WithoutCompareTo_User(4, "lbw4", "上海市", 23));

        System.out.println("元素对象多少个"+tree0.size());
        for (WithoutCompareTo_User userPojo : tree0) {
            System.out.println(userPojo);
        }

    }

LinkedHashMap和LinkedHashSet

参考资料:
https://blog.csdn.net/qq_40050586/article/details/105851970

最后还剩下不常用的一对。为什么放到最后说呢?因为理解了上面的东西,LinkedHashMap和LinkedHashSet这一对就非常好理解了。

先说LinkedHashMap,其实它就是HashMap+双向链表,使HashMap保证有序。

LinkedHashMap就是HashMap中将其node维护成了一个双向链表来保证有序。

LinkedHashMap可以实现LRU缓存,如有需要可自行百度。

最后,LinkedHashSet也是基于LinkedHashMap来实现的。所以这对概念其实差不多。

现在有一个问题,既然都是保证了有序性,那么用TreeMap 不就完了吗,用什么LinkedHashMap。。。

下面直接上实例,展示它们之间到底有啥不同!

对比TreeMap和LinkedHashMap


/**
     * 测试TreeSet,和LinkedHashSet之间的区别 (TreeMap和LinkedHashMap同理)
     * TreeSet和LinkedHashSet都是有序的。但是他们的主要区别就是:
     *
     * TreeSet / TreeMap 是根据CompareTo来决定遍历顺序的,与add()方法无关;
     * LinkedHashSet / LinkedHashMap 是根据add() / put() 方法的调用次序决定内部顺序的。
     * 原因是LinkedHashSet / LinkedHashMap的每个节点都维护了双向链表,决定其内部顺序。
     */
    @Test
    void test3() {
        Set<UserPojo> tree=new TreeSet();
        //第四个参数是age年龄
        tree.add(new UserPojo(1, "lbw", "山东省青岛市", 19));
        tree.add(new UserPojo(2, "lbw2", "山东省济南市", 20));
        tree.add(new UserPojo(4, "lbw4", "上海市", 23));
        tree.add(new UserPojo(3, "lbw3", "北京市", 22));
        //由于重写的方法是按照年龄排序的。所以最终打印一定会按照年龄顺序打印出来。
        for (UserPojo userPojo : tree) {
            System.out.println(userPojo);
        }
        /*
            打印结果:
            UserPojo(id=4, name=lbw4, address=上海市, age=23)
            UserPojo(id=3, name=lbw3, address=北京市, age=22)
            UserPojo(id=2, name=lbw2, address=山东省济南市, age=20)
            UserPojo(id=1, name=lbw, address=山东省青岛市, age=19)
        */

        System.out.println("=========分割线,上面是TreeSet测试,下面是LinkedHashSet测试===============");
        System.out.println("=========分割线,上面是TreeSet测试,下面是LinkedHashSet测试===============");

        LinkedHashSet<UserPojo> linkedHashSet = new LinkedHashSet<>();
        //第四个参数是age年龄
        linkedHashSet.add(new UserPojo(1, "lbw", "山东省青岛市", 19));
        linkedHashSet.add(new UserPojo(2, "lbw2", "山东省济南市", 20));
        linkedHashSet.add(new UserPojo(4, "lbw4", "上海市", 23));
        linkedHashSet.add(new UserPojo(3, "lbw3", "北京市", 22));
        //最终打印一定会按照插入add()的先后顺序打印出来。
        for (UserPojo userPojo : linkedHashSet) {
            System.out.println(userPojo);
        }
        /*
            打印结果:
            UserPojo(id=1, name=lbw, address=山东省青岛市, age=19)
            UserPojo(id=2, name=lbw2, address=山东省济南市, age=20)
            UserPojo(id=4, name=lbw4, address=上海市, age=23)
            UserPojo(id=3, name=lbw3, address=北京市, age=22)
        */

    }

HashTable,Vector

说到这里了再介绍完两个不常用的类吧。

HashTable:

  • Map的一员,比较古老,目前已经不推荐使用该类,效率比较低
  • 因为该方法是同步方法,可以保证线程安全性!
  • 现在一般用:ConcurrentHashMap 来替代。

Vector:

  • List的一员,JDK1.0的老方法,比较古老,目前已经不推荐使用该类,效率比较低
  • vector可以保证线程安全!

Iterator(迭代器)的简单介绍和使用

只有继承了Iterable接口才可以使用迭代器

Iterable 接口中有一个成员方法:iterator()

因此,List 和 Set可以使用.iterator()方法,得到一个迭代器

因为List和Set都继承了Collections,而Collections这个接口继承了Iterable

Map就不行,因为它没有继承Collections,自然也没有iterable.但是它可以通过转成set集合的方式来使用迭代器

Iterator的重要特性!一边遍历一边删除集合中元素!!

注意:其改变了原数组!

/**
     * Iterator的重要特性!一边遍历一边删除集合中元素!!
     */
    @Test
    void test3() {
        ArrayList<UserPojo> users = new ArrayList<>();
        users.add(new UserPojo(1, "lbw", "山东省青岛市", 19));
        users.add(new UserPojo(2, "lbw2", "山东省济南市", 20));
        users.add(new UserPojo(3, "lbw3", "北京市", 22));
        users.add(new UserPojo(4, "lbw4", "上海市", 23));
        Iterator<UserPojo> iterator = users.iterator();
        while (iterator.hasNext()){
            UserPojo element = iterator.next();
            if (element.getName().equals("lbw"))
                iterator.remove();
        }
        System.out.println(users);  //名字叫lbw的已经被删除!
    }

自定义实现迭代器

实现Iterable后,可以用“foreach”循环遍历你的对象。

这部分代码见:

在这里插入图片描述

好处就是:外部类就可以用增强for (foreach)来遍历你这个类了。

后记

本文完,如果想要Demo中的代码,可以去我的Gitee仓库自取:

本文源代码已上传至Gitee:https://gitee.com/da-ji/full-stack-developer,大家需要可自取

如有疏漏,恳请指正。


版权声明:本文为weixin_44757863原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。