JDK8：HashMap源码解析：replacementTreeNode方法、TreeNode类

落日映苍穹つ 2024-04-20 08:19 25阅读 0赞

一、概述

HashMap中每一个键值对都是以一个HashMap.Node<K,V>对象实例进行存储的，当不同的键对应的多个键值对路由到元素数组的同一个位置时，这多个键值对对应的Node对象之间会以链表的方式组织起来。这是默认的组织方式。

当我们恰好要根据key寻找一个在链表上的对象的时候，就涉及到遍历链表，逐个调用key对象的equals方法来比对我们要查找的到底是哪个键值对了。可想当链表的长度越长，匹配的时间复杂度就越高，和链表的长度成正比。这也就是HashMap内部实现时会根据链表的长度超过限定的阈值时，会将链表结构转换为红黑树结构，用来提升查询性能。replacementTreeNode方法就是此时被调用。TreeNode类也就是红黑树的节点对象。

二、方法解析

// 该方法只是调用了TreeNode类的构造方法，依据当前节点信息构造一个树节点对象
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

接下来看下TreeNode类的定义

/**
     * 首先该类是HashMap类的一个静态内部类
     * 包内可见、不可被继承
     * 该类继承了LinkedHashMap.Entry，而LinkedHashMap.Entry继承了HashMap.Node
     * PS：要知道LinkedHashMap是HashMap的子类，然而目前的状况是HashMap作为父类，他的一个静态内部类（TreeNode）居然继承了子类LinkedHashMap的一个静态内部类
     *（LinkedHashMap.Entry），这个设计不太理解。
     * 红黑树是一个二叉树，父节点、左节点、右节点、红黑标识都是二叉树中的元素
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next); // 此处调用 LinkedHashMap.Entry的构造方法
        }
     
        // 以下省略了很多方法，后文会逐步解析
    }

接下来再看下LinkedHashMap.Entry类的定义

/**
     * 首先该类是LinkedHashMap的一个静态内部类
     * 包内可见、又因为没有final修饰符（所以HashMap中的TreeNode类才能继承到他）
     * 该类除了增加了before、after两个实例变量之外，没有任何的行为扩展，也就是说他的所有行为都继承自HashMap.Node
     * 该类也只有一个构造方法，且该构造方法就是通过调用HashMap.Node的构造方法构造一个HashMap.Node对象
     * PS：看到这里就更加不理解为何HashMap.TreeNode不直接继承HashMap.Node，而要绕个弯来继承LinkedHashMap.Entry，难道是为了使用before、after？可貌似也没有使用到。
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }