TreeMap和ConcurrentHashMap总结

TreeMap底层是红黑树，能够实现该Map集合有序~

如果在构造方法中传递了Comparator对象，那么就会以Comparator对象的方法进行比较。否则，则使用Comparable的compareTo(T o)方法来比较。

• 值得说明的是：如果使用的是compareTo(T o)方法来比较，key一定是不能为null，并且得实现了Comparable接口的。
• 即使是传入了Comparator对象，不用compareTo(T o)方法来比较，key也是不能为null的

    public static void main(String[] args) {
        TreeMap<Student, String> map = new TreeMap<Student, String>((o1, o2) -> {
            //主要条件
            int num = o1.getAge() - o2.getAge();

            //次要条件
            int num2 = num == 0 ? o1.getName().compareTo(o2.getName()) : num;

            return num2;
        });

        //创建学生对象
        Student s1 = new Student("潘安", 30);
        Student s2 = new Student("柳下惠", 35);

        //添加元素进集合
        map.put(s1, "宋朝");
        map.put(s2, "元朝");
        map.put(null, "汉朝");

        //获取key集合
        Set<Student> set = map.keySet();

        //遍历key集合
        for (Student student : set) {
            String value = map.get(student);
            System.out.println(student + "---------" + value);
        }
    }

image.png

我们从源码中的很多地方中发现：Comparator和Comparable出现的频率是很高的，因为TreeMap实现有序要么就是外界传递进来Comparator对象，要么就使用默认key的Comparable接口(实现自然排序)

最后我就来总结一下TreeMap要点吧：

1. 由于底层是红黑树，那么时间复杂度可以保证为log(n)
2. key不能为null，为null为抛出NullPointException的
3. 想要自定义比较，在构造方法中传入Comparator对象，否则使用key的自然排序来进行比较
4. TreeMap非同步的，想要同步可以使用Collections来进行封装

ConcurrentHashMap的核心要点

• 底层结构是散列表(数组+链表)+红黑树，这一点和HashMap是一样的。
• Hashtable是将所有的方法进行同步，效率低下。而ConcurrentHashMap作为一个高并发的容器，它是通过部分锁定+CAS算法来进行实现线程安全的。CAS算法也可以认为是乐观锁的一种~
• 在高并发环境下，统计数据(计算size...等等)其实是无意义的，因为在下一时刻size值就变化了。
• get方法是非阻塞，无锁的。重写Node类，通过volatile修饰next来实现每次获取都是最新设置的值
• ConcurrentHashMap的key和Value都不能为null