前言

本文是学习笔记，也有配套源码实例，主要是针对本人对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这两个方法来保证。可以重写这两个方法来重新定义“对象重复” 这个概念。
  • 如何重写Object.equals，和 Object.hashCode这两个方法呢？可以看我的历史文章：Stream distinct 根据list某个字段去重
• 无序性。存取和插入顺序不一。也因此它无法调用.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，大家需要可自取

如有疏漏，恳请指正。