java源码解析（java新手代码大全）

程序员文章站 2023-11-17 13:30:34

treemap简介treemap是一个直接由红黑树实现的结构，对于key值得比较来排序，显然得到：1.key的class必须实现comparable方法，不能抛出classcastexception...

treemap

简介

treemap是一个直接由红黑树实现的结构，对于key值得比较来排序，显然得到：

1.key的class必须实现comparable方法，不能抛出classcastexception异常，否则必须指定一个comprartor

2.由于treemap实现了serializable接口，所以默认的或者自定义的comparator也应该实现该接口

最重要的是，实现了navigablemap，我理解为导航map,提供了各种操作map视图的操作

public class treemap<k,v>
    extends abstractmap<k,v>
    implements navigablemap<k,v>, cloneable, java.io.serializable{}
复制代码

构造方法

四个构造方法，其实就是是否使用默认的compatator

对于无序map，直接调用putall,有序的sortedmap话递归调用buildfromsorted，提高效率

public treemap() {
    comparator = null;
}

public treemap(comparator<? super k> comparator) {
        this.comparator = comparator;
    }

public treemap(map<? extends k, ? extends v> m) {
    comparator = null;
    putall(m);
}

public treemap(sortedmap<k, ? extends v> m) {
    comparator = m.comparator();
    try {
        buildfromsorted(m.size(), m.entryset().iterator(), null, null);
    } catch (java.io.ioexception cannothappen) {
    } catch (classnotfoundexception cannothappen) {
    }
}
复制代码

但是putall依然判断了map instanceof sortedmap

具体的红黑树的操作在此不作赘述

remove(),put()最根本的操作是红黑树的操作，get()也是二叉搜索树比较直观的实现

方法详解

有关树的操作的方法，其实就是代码分支比较多，需要考虑各种情况然后转换为代码就好了
比较的话看如果有comparator就用，没有就用key默认的comparable

successor() 查找下个节点

在containsvalue()从第一个节点开始successor遍历
在foreach()从第一个节点开始successor遍历
replaceall()从第一个节点开始successor遍历赋值新的value
remove()遍历找出object删除

static <k,v> treemap.entry<k,v> successor(entry<k,v> t) {
    // 首先明确，下个节点是比当前节点大的节点，为当前节点右节点的左叶子节点
    if (t == null)
        return null;
    else if (t.right != null) {
        entry<k,v> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        entry<k,v> p = t.parent;
        entry<k,v> ch = t;
        // 当右节点为空，并且是父节点的右节点时，下个节点当前分支树的父节点
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        // 当右节点为空，并且是父节点的左节点时，下个节点当前节点的父节点
        return p;
    }
}
复制代码

getceilingentry()/getfloorentry 获取[low,key]/[key,high]的最大/小值，没有返回null

// 这个跟successor是相似的，其实如果根据搜索树没找到，就是找的下一个节点
final entry<k,v> getceilingentry(k key) {
    entry<k,v> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        //比当前节点小，再跟左子节点比较
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            //比当前节点大，再跟右子节点比较
            if (p.right != null) {
                p = p.right;
            } else {
                //这里跟successor相同，比最右叶子大，下一个为当前子树的父节点
                entry<k,v> parent = p.parent;
                entry<k,v> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            //相等的话返回当前节点
            return p;
    }
    return null;
}
//跟上面是镜像的过程
final entry<k,v> getfloorentry(k key) {
    entry<k,v> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        //比当前节点大，跟右子节点比较
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            //比当前节点小，再跟左子节点比较
            if (p.left != null) {
                p = p.left;
            } else {
                entry<k,v> parent = p.parent;
                entry<k,v> ch = p;
                //比最左叶子小，下一个为当前子树的父节点
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
             //相等的话返回当前节点
            return p;

    }
    return null;
}
复制代码

gethigherentry()/getlowerentry获取[low,key)/(key,high]的最大/小值，没有返回null

跟getceilingentry一样的只不过对于相等的情况，不考虑相等的情况

final entry<k,v> gethigherentry(k key) {
    entry<k,v> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                entry<k,v> parent = p.parent;
                entry<k,v> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}
复制代码

descendingmap()翻转map

底层由descendingsubmap()实现，其实还是这个map，只不过对于所有的操作，比如getfist()，会将其转换为getlast()来执行,所以对于descendingmap()的操作依然会影响原map

同样的，submap()的操作也会影响原map

static final class descendingsubmap<k,v>  extends navigablesubmap<k,v> {
    private static final long serialversionuid = 912986545866120460l;
    // m是当前map,fromstart是否从头开始为ture则lo为null，lo开始位置，loinclusive是否包含开始位置
    descendingsubmap(treemap<k,v> m,
                    boolean fromstart, k lo, boolean loinclusive,
                    boolean toend,     k hi, boolean hiinclusive) {
        super(m, fromstart, lo, loinclusive, toend, hi, hiinclusive);
    }
复制代码

//descendingsubmap一些方法的实现
treemap.entry<k,v> sublowest()       { return abshighest(); }
treemap.entry<k,v> subhighest()      { return abslowest(); }
treemap.entry<k,v> subceiling(k key) { return absfloor(key); }
treemap.entry<k,v> subhigher(k key)  { return abslower(key); }
treemap.entry<k,v> subfloor(k key)   { return absceiling(key); }
treemap.entry<k,v> sublower(k key)   { return abshigher(key); }
复制代码