TreeMap分析

2023-12-05 23:30:28

TreeMap分析

TreeMap和HashMap不同点

  1. TreeMap的数据结构和HashMap不一样，TreeMap是基于红黑树实现的。而HahsMap是数组 + 链表（红黑树）来实现的。

  2. TreeMap不需要调用Hash方法来算hash值。

  3. TreeMap一开始就是红黑树，不像HashMap一样，达到特定的条件之后才会变为红黑树。

  4. TreeMap不需要扩容。但是HashMap会扩容。

  5. TreeMap没有负载因子，也没有初始容量。但是这些HashMap都有。

    数组和链表的差距，主要是同样的空间的前提下，链表结构的空间利用率高。数组需要连续的存储空间。这也就导致了慢。首先要知道，他是基于红黑树实现的，所以，他并不需要连续的存储空间。所以，从跟上就不会有扩容的问题出现，只有在内存不够的情况下，直接OOM。

  6. TreeMap里面存放的key必须要实现Comparable接口，或者在构造函数里面指定Comparator，并且key能在Comparator比较。而HashMap在hash冲突之后，并且链表变为红黑树，hash值一样的情况下，会调用Comparable接口来做比较，这就要求要key要实现Comparable接口。在日常的使用中，直接放就行， 但是自己可以仔细的看看，这些类上面都实现了Comparable接口。如果类型不一样或者不是Comparable接口，就会抛出异常ClassCastException

  7. TreeMap实现的接口比HashMap多。

TreeMap分析

​ （TreeMap）

TreeMap分析

​ （HashMap）

  1. Entry不一样。TreeMap的是TreeMap##Entry，他的这些属性都是红黑树所需要的。HashMap的是HashMap##Node，HashMap##TreeNode 其实我觉得TreeMap的Entry是可以复用HashMap的TreeNode的。

  2. 迭代器不一样

    Treemap的迭代器是TreeMap##EntryIterator

    HashMap的迭代器是HashMap##EntryIterator

    因为HashMap和TreeMap的实现不一样，所以迭代器的具体功能也是不一样的。

    具体放在下一章节说

  3. TreeMap不支持key为null，但是HashMap支持。TreeMap是需要用来做排序的，并且没有调用hashcode方法，所以key不能为null，HashMap在转为红黑树的时候，是用key里面的hash值来做比较的。对于null，HashMap产生的hash值是 0

    //HashMap里的hash方法  
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    以上是我能想到的，可能不太全面，如果有还有不一样的话，请补充补充。

TreeMap会有Hash冲突吗？

不会，因为他根本就不会调用hashcode方法。可以看看put的源码

    public V put(K key, V value) {
       //如果根节点没有值。这个if就是给根节点赋值。
        Entry<K,V> t = root;
        if (t == null) {
          //这个compare，就是为了检查类型和null
            compare(key, key); // type (and possibly null) check
           //简单的构建Entry，赋值给root
            root = new Entry<>(key, value, null);
            size = 1;
           // 快速失败，继续修改次数
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
      
      //下面就是在有根节点的情况下，遍历整个树，利用compare来比较，可以看到
      // 小于就是左
      // 大于就是右
      // 等于就是覆盖值。
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
      
      //在平衡
        fixAfterInsertion(e);
        size++;
      // 快速失败
        modCount++;
        return null;
    }

可以看到，压根和hash没有一点点的关系，所以就不会存在hash冲突的问题。主要是利用Comparable接口和Comparator。并且Comparator的优先级更高。

TreeMap遍历（迭代）顺序是什么？和HashMap有啥不一样

TreeMap的迭代

先上例子

     @Test
   public void testTreeMap(){
       TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        treeMap.put(1,1);
        treeMap.put(2,2);
        treeMap.put(3,3);
        treeMap.put(4,4);
        treeMap.put(5,5);
        treeMap.put(6,6);
        treeMap.put(7,7);
        treeMap.put(8,8);
        treeMap.put(9,9);
        treeMap.put(10,10);
        treeMap.put(11,11);
        treeMap.put(12,12);


       Iterator<Map.Entry<Integer, Integer>> iterator = treeMap.entrySet().iterator();
       while (iterator.hasNext()){
           System.out.print(iterator.next() + ",");
       }
   }

TreeMap分析

要知道在TreeMap的数据结构是红黑树。首先，他是一种二叉排序树。怎么遍历的时候就出现这种结果了。他是按照什么样的遍历顺序来遍历的呢？二叉排序树按照遍历根节点和子节点的顺序不同，可以分为好多种，经常用的是三种，中序遍历，先序遍历，后序遍历。这里用的是那种遍历？

直接debug，看看他生成的树的结构是什么。然后再看看迭代器相关的代码。就能确定了。

TreeMap分析

构建出来的树就是这个样子，在看看迭代器是怎么遍历的？

 //  Iterator<Map.Entry<TreeDo, Integer>> iterator = hashMap.entrySet().iterator();从这里debug进来。      
 public Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator(getFirstEntry());
        }
    
//  getFirstEntry() 看看第一个节点是什么？
// 这个方法很简单，从根节点开始，查找左子树，一直找到最左的子树。
  final Entry<K,V> getFirstEntry() {
        Entry<K,V> p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

// 在看看EntryIterator里面next方法

  final Entry<K,V> nextEntry() {
          // 这个next就是上面查找出来的最左的节点
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
     // 快速失败
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
    
     // 找到下一个要访问节点，重点就是这里
            next = successor(e);
            lastReturned = e;
            return e;
        }

//重点就是successor方法
  static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
    // 这里的逻辑就是重点中的重点，一块看看
    
     //如果说，右子树不为null，并且有左子树，就找到这个右子树最左的节点。
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
           //右子树为null
            Entry<K,V> p = t.parent; //父节点
            Entry<K,V> ch = t; //当前节点
          
           //如果p不为null并且当前的节点是p的右子树的话。一直往上找。
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

所以，结合图，还有这里的代码发现，这里的遍历顺序是中序遍历。

HashMap的迭代

hashMap都已经很熟悉了，就直接看他的迭代器的方法吧

主要分为两个部分，一个是new 迭代器的时候的赋值操作，一个是调用next方法的取值操作

  1. 赋值操作
 // 只要debug从下面的代码进去，就能看到，要注意EntryIterator可是继承HashIterator，所以得看到构造方法里面，这就是在构造方法里面赋值的
// Iterator<Map.Entry<TreeDo, Integer>> iterator = hashMap.entrySet().iterator();

HashIterator() {
          // 快速失败
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
  
           //看这里的操作，do里面没看什么事，重点是while。
  				// index初始为0，在hashmap的table里面一直找，找到了第一个下标不为null的元素就返回。
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

  1. next取值操作

     
// 这个方法还是在 HashIterator里面。
final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
           //快速失败
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
  
           // 重点是这里。do while里面的和上面一样。重点是if里面
       // 如果将e.next赋值给了next，只有当链表或者红黑树的没有节点了，才会再次获取hashMap中下一个索引位置不为null的值。
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

    问题？

    如果变为链表的话,next肯定是有的，自然而然的就是下一个节点，但是要是红黑树的话，next是啥？

    // 分为两种情况
// 1. 链表变为红黑树的时候
   final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                   //看这里next，这里的代码就是将node替换为TreeNode，别的什么都没有变。所以，这里的顺序还是链表的顺序。
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
// 2. 已经变为红黑树的时候,这里的代码比较长，我就不在这里写，在 HashMap#  final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) 中。
                //父节点
                TreeNode<K,V> xp = p; 
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //父节点的next赋值给new出来的节点的next
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                     // 当前节点变为父节点的next。
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
父节点之前next就是子节点的next，然后把子节点变为父节点next。 这好像是头插法。

关于TreeMap就分析到这里了。如有不正确的地方，欢迎指出。谢谢。

上一篇：ThreadLocal内存泄露的原因及避免 -- java面试


下一篇：Fault-Tolerant Virtual Machines阅读笔记