登录 立即注册
安币:

查看: 214|回复: 0

红黑树在HashMap中的应用

[复制链接]

3

主题

4

帖子

28

安币

初级码农

Rank: 1

发表于 2018-1-11 15:50:01 | 显示全部楼层 |阅读模式
如果对本篇文章感兴趣,请前往,原文地址:http://www.apkbus.com/blog-817034-76855.html

##红黑树在HashMap中的应用在上一篇文章:[红黑树(Red-Black Tree)解析](http://blog.csdn.net/Troy_kfrozen/article/details/78890297) 中我们了解了二叉查找树以及红黑树的概念和特性,并且对查找、插入和删除操作的实现源码进行了详细的剖析。其复杂的操作流程保证了红黑树的五条特性始终能够被满足,从而使得红黑树操作的时间复杂度为O(logN)。也正因为如此,Java的很多集合框架都引入了红黑树结构以提高性能。在JDK1.8中,我们常用的HashMap也成功傍身红黑树策马奔腾,下面就让我们一起看看HashMap是如何入手红黑树的。这里我们依然从查找,插入和删除三个常用操作来进行分析。除去这三个操作之外还有一个地方与红黑树结构密切相关--**resize扩容操作**,关于HashMap的扩容我们在另一篇文章中有详述,这里就不再重复,有兴趣的童鞋[请戳这里(Java中集合的扩容策略及实现)](http://blog.csdn.net/Troy_kfrozen/article/details/78889947)。- **相关成员变量**        首先,先介绍一下相关的成员变量        ```                //哈希表中的数组,JDK 1.8之前存放各个链表的表头。1.8中由于引入了红黑树,则也有可能存的是树的根                transient Node[] table;                                //树化阈值。JDK 1.8后HashMap对冲突处理做了优化,引入了红黑树。                //当桶中元素个数大于TREEIFY_THRESHOLD时,就需要用红黑树代替链表,以提高操作效率。此值必须大于2,并建议大于8                static final int TREEIFY_THRESHOLD = 8;                                //非树化阈值。在进行扩容操作时,桶中的元素可能会减少,这很好理解,因为在JDK1.7中,                //每一个元素的位置需要通过key.hash和新的数组长度取模来重新计算,而1.8中则会直接将其分为两部分。                //并且在1.8中,对于已经是树形的桶,会做一个split操作(具体实现下面会说),在此过程中,                //若剩下的树元素个数少于UNTREEIFY_THRESHOLD,则需要将其非树化,重新变回链表结构。                //此值应小于TREEIFY_THRESHOLD,且规定最大值为6                static final int UNTREEIFY_THRESHOLD = 6;                             //最小树化容量。当一个桶中的元素数量大于树化阈值并请求treeifyBin操作时,             //table的容量不得小于4 * TREEIFY_THRESHOLD,否则的话在扩容过程中易发生冲突            static final int MIN_TREEIFY_CAPACITY = 64;                        ```- **查找**        HashMap中的查找是最常用到的API之一,调用方法为map.get(key),我们就从这个get方法看起:                ```        public V get(Object key) {        Node e;        return (e = getNode(hash(key), key)) == null ? null : e.value;    }        ```                可以看到这个方法调用了两个内部方法:**hash和getNode**,下面依次来看这两个方法:                ```        //hash方法对传入的key进行了哈希值优化,具体做法为将key的哈希值h无符号右移16位之后与h本身按位异或,        //相当于将h的高16位于低16位按位异或。这样做的原因在于一个对象的哈希值即使分布再松散,其低几位发生冲突的概率也较高,        //而HashMap在计算index时正是用该方法的返回值与(length-1)按位与,结果就是哈希值的高位全归零,只保留低几位。        //这样一来,此处的散列值优化就显得尤为重要,它混合了原始哈希值的高位与低位,以此来加大低位的松散性。        static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }        /**     * Implements Map.get and related methods     *     * @param hash hash for key  //此处传入的就是上面hash方法的返回值,是经过优化的哈希值     * @param key the key     * @return the node, or null if none     */    final Node getNode(int hash, Object key) {        Node[] tab; Node first, e; int n; K k;        //上文提到的计算index的方法:(n - 1) & hash,first是这个数组table中index下标处存放的对象        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {            if (first.hash == hash && // always check first node                    //如果first对象匹配成功,则直接返回                ((k = first.key) == key || (key != null && key.equals(k))))                return first;            if ((e = first.next) != null) {                    //否则就要在index指向的链表或红黑树(如果有的话)中进行查找                if (first instanceof TreeNode)                        //如果first节点是TreeNode对象,则说明存在的是红黑树结构,这是我们今天要关注的重点                    return ((TreeNode)first).getTreeNode(hash, key);                 //否则的话就是一个普通的链表,则从头节点开始遍历查找                do {                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        return e;                } while ((e = e.next) != null);            }        }        return null;    }        ```                重点来了,这里关注下**TreeNode.getTreeNode(hash, key)**方法,这是1.8中引入红黑树后新增的操作,它对于HashMap在哈希冲突多发,产生长链表的情况下的查找效率有着极大的提升:                ```        /**    * Calls find for root node.    */    //定位到树的根节点,并调用其find方法    final TreeNode getTreeNode(int h, Object k) {        return ((parent != null) ? root() : this).find(h, k, null);    }        final TreeNode find(int h, Object k, Class kc) {        TreeNode p = this; //p赋值为根节点,并从根节点开始遍历        do {            int ph, dir; K pk;            TreeNode pl = p.left, pr = p.right, q;            if ((ph = p.hash) > h) //查找的hash值h比当前节点p的hash值ph小                p = pl; //在p的左子树中继续查找            else if (ph < h)                p = pr; //反之在p的右子树中继续查找            else if ((pk = p.key) == k || (k != null && k.equals(pk)))                return p; //若两节点hash值相等,且节点的key也相等,则匹配成功,返回p                        /****---- 下面的情况是节点p的hash值和h相等,但key不匹配,需继续在p的子树中寻找 ----****/                    else if (pl == null)                p = pr; //若p的左子树为空,则直接在右子树寻找。若右子树也为空,则会不满足循环条件,返回null,即未找到            else if (pr == null)                p = pl; //反之若左子树不为空,同时右子树为空,则继续在左子树中寻找            else if ((kc != null || (kc = comparableClassFor(k)) != null) &&                         (dir = compareComparables(kc, k, pk)) != 0)                //若k的比较函数kc不为空,且k是可比较的,则根据k和pk的比较结果来决定继续在p的哪个子树中寻找                p = (dir < 0) ? pl : pr;            //若k不可比,则只能分别去p的左右子树中碰运气了,先在p的右子树pr中寻找,结果为q            else if ((q = pr.find(h, k, kc)) != null)                return q; //若q不为空,代表匹配成功,则返回q,结束            else                p = pl; //到这里表示未能在p的右子树中匹配成功,则在左子树中继续        } while (p != null);        //各种寻找均无果,返回null,表示查找失败。        return null;    }        ```        对于HashMap的查找操作来说,如果数据足够分散,则查找效率是非常高的(时间复杂度O(1))。但是再优秀的hash算法也没法保证不发生哈希冲突,而且随着数据量的增大冲突会越发严重。由于在1.8之前是将冲突节点连成一个链表,所以在最坏情况下查找的时间复杂度会变为O(N),红黑树的引入就是为了优化这一部分,当一个桶中的元素个数大于TREEIFY_THRESHOLD时,HashMap会将链表转变为红黑树结构,从而将操作的复杂度降为O(logN)。        - **插入**        HashMap的插入操作,API为map.put(key, value)。上面我们看到了getTreeNode方法对查找操作性能的提升,这个提升得益于构建红黑树时的各种平衡操作,而构建红黑树便是在向HashMap插入节点时完成的。                首先我们来看一下HashMap插入操作的流程,其实这里也是分两步走:先进行查找,如果key已经存在,则覆盖value;否则的话通过第一步查找定位到合适的插入位置,新建节点并完成插入。下面就来看put方法的源码:                ```        public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }        ```                可以看到其实是调用了内部的putVal方法,这里的hash(key)跟上文所述的是同一个方法,下面继续看putVal**(注:下文中有关resize扩容的源码在[这篇文章](http://blog.csdn.net/Troy_kfrozen/article/details/78889947)中已有详述,在此就不再重复)**:                ```        /**     * Implements Map.put and related methods     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node[] tab; Node p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length; //若当前哈希数组table的长度为0,则进行扩容        //确定输入的hash在哈希数组中对应的下标i        if ((p = tab[i = (n - 1) & hash]) == null)                //若数组该位置之前没有被占用,则新建一个节点放入,插入完成。            tab = newNode(hash, key, value, null);        else {            Node e; K k;            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))                //若该位置上存放的第一个节点p能与输入的节点信息匹配,则将p记录为e并结束查找                e = p;            else if (p instanceof TreeNode)                    //若该位置的第一个节点p为TreeNode类型,说明这里存放的是一棵红黑树,p为根节点。                    //于是交给putTreeVal方法来完成后续操作,该方法下文会有详述                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);            else {                    //走到这里,说明p不匹配且是一个链表的头结点,该遍历链表了                for (int binCount = 0; ;   binCount) {                        //e指向p的下一个节点                    if ((e = p.next) == null) {                            //若e为空,则说明已经到表尾了还未能匹配,则在表尾处插入新节点                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                                //若插入后,该桶中的节点个数已达到了树化阈值                                //则对该桶进行树化。该部分源码下文会有详述                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))                            //匹配成功,我们需要用新的value来覆盖e节点                        break;                                        p = e; //循环继续                }            }            //若执行到此时e不为空,则说明在map中找到了与key相匹配的节点e            if (e != null) { // existing mapping for key                V oldValue = e.value; //暂存e节点当前的值为oldValue                if (!onlyIfAbsent || oldValue == null)                    //若onlyIfAbsent==true,则已存在节点的value不能被覆盖,除非其value为null                    //否则的话,用输入的value覆盖e.value                    e.value = value;                //钩子方法,这在HashMap中是个空方法,但是在其子类LinkedHashMap中会被Override                //通知子类:节点e被访问过了                afterNodeAccess(e);                //返回已被覆盖的节点e的oldValue                return oldValue;            }        }                /****--执行到此处说明没有匹配到已存在节点,一定是有新节点插入--****/                  modCount; //结构操作数加一        if (  size > threshold)            resize(); //插入后,map中的节点数加一,若此时已达阈值,则扩容        afterNodeInsertion(evict); //同样的钩子方法,通知子类有新节点插入        return null; //由于是新节点插入,没有节点被覆盖,故返回null    }        ```                通过上面的代码可以清楚的看到插入操作的整体流程:                a. 先通过key的hash定位到table数组中的一个桶位;                b. 若此桶没有被占用,则新建节点,占坑,记录,考虑扩容,结束。若已被占用,则总是先与第一个节点进行一次匹配,若成功则无需后续的遍历操作,直接覆盖;否则的话需进行遍历;                c. 若桶中的第一个节点p是TreeNode类型,则表示桶中存在的是一棵红黑树,于是后续操作将由**putTreeVal**方法来完成。否则的话说明桶中的是一个链表,则对该链表进行遍历;                d. 若遍历过程中匹配到了节点e,则进行覆盖。否则的话通过遍历定位到合适的插入位置,新建节点插入,对于链表结构需考虑是否**树化**。最后进行操作记录,考虑扩容,结束。                JDK1.8在上述流程对红黑树的应用体现在两个地方,**treeifyBin和putTreeValue**,分别是树化操作和向树中插入节点,对照两个方法的源码可以发现二者的实现十分相似,其实构建树的过程就是由多个插入操作组成的,此处我们通过treeifyBin方法的源码来分析下HashMap中对于红黑树插入和树化操作的实现:                ```        /**     * Replaces all linked nodes in bin at index for given hash unless     * table is too small, in which case resizes instead.     */     //这是HashMap类的实例方法,作用是将一个链表结构转化为红黑树结构    final void treeifyBin(Node[] tab, int hash) {        int n, index; Node e;        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)            resize(); //若table数组为空或其容量小于最小树化值,则用扩容取代树化        else if ((e = tab[index = (n - 1) & hash]) != null) { //定位到hash对应的桶位,头结点记为e            TreeNode hd = null, tl = null; //声明两个指针分别指向链表头尾节点            do {                TreeNode p = replacementTreeNode(e, null); //将Node类型的节点e替换为TreeNode类型的p                if (tl == null)                    hd = p; //若当前链表为空,则赋值头指针为p                else {                    p.prev = tl; //否则将p添加到链表尾部                    tl.next = p;                }                tl = p; //后移尾指针            } while ((e = e.next) != null); //循环继续                        if ((tab[index] = hd) != null) //将链表头节点放入table的index位置                hd.treeify(tab); //通过treeify方法将链表树化        }    }            /**    * Forms tree of the nodes linked from this node.    * @return root of tree    */    //这是TreeNode类的实例方法,以调用节点this为根节点,将链表树化    final void treeify(Node[] tab) {        TreeNode root = null; //声明root变量以记录根节点        for (TreeNode x = this, next; x != null; x = next) { //从调用节点this开始遍历            next = (TreeNode)x.next; //暂存链表中的下一个节点,记为next            x.left = x.right = null; //当前节点x的左右子树置空            if (root == null) {                x.parent = null; //若root仍为空,则将x节点作为根节点                x.red = false; //红黑树特性之一:根节点为黑色                root = x; //赋值root            }            else { //否则的话需将当前节点x插入到已有的树中                K k = x.key;                int h = x.hash;                Class kc = null;                //第二层循环,从根节点开始寻找适合x插入的位置,并完成插入操作。                //putTreeVal方法的实现跟这里十分相似。                for (TreeNode p = root;;) {                     int dir, ph;                    K pk = p.key;                    if ((ph = p.hash) > h) //若x的hash值小于节点p的,则往p的左子树中继续寻找                        dir = -1;                    else if (ph < h) //反之在右子树中继续                        dir = 1;                    //若两节点hash值相等,且key不可比,则利用System.identityHashCode方法来决定一个方向                    else if ((kc == null && (kc = comparableClassFor(k)) == null) ||                            (dir = compareComparables(kc, k, pk)) == 0)                       dir = tieBreakOrder(k, pk);                     TreeNode xp = p; //将当前节点p暂存为xp                    //根据上面算出的dir值将p向下移向其左子树或右子树,若为空,则说明找到了合适的插入位置,否则继续循环                    if ((p = (dir
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

站长推荐

通过邮件订阅最新安卓weekly信息
上一条 /4 下一条

下载安卓巴士客户端

全国最大的安卓开发者社区

广告投放| 下载客户端|申请友链|手机版|站点统计|安卓巴士 ( 粤ICP备15117877号 )

快速回复 返回顶部 返回列表