TreeMap解析

TreeMap是一个二叉树的数据结构;TreeMap不允许出现相同的键。

源码解析:
TreeMap解析
一:
这是TreeMap的put源码。
可以看出有一个泛型对象实体Entry,Entry里面维持一个 左、右子树跟父树 的对象属性。依靠这个实体完成树形结构的构建,包括hashCode跟equals的生成。

TreeMap首先将第一个要put的值设为根节点,后续要put的值根据 TreeMap解析
来比较该对象应该要放置的位置,由于compare返回类型是int,所以比较器返回三种情况 > 0、< 0、== 0.
TreeMap解析

如果比较后获取的值< 0,则将该树的左子树设置为当前树,> 0 则为右子树,== 0 则将该树的值设置为当前要put的值,这也就是说明为什么TreeMap中,如果有相同的键put,
后续的键值会覆盖掉前边键的值。

然后
TreeMap解析
根据比较器将 当前节点 设置为父节点的左子树还是右子树

这样put操作也就形成了一棵二叉树!

二:
我们来看get源码。
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
具体操作位于getEntry中。
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}

final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
        K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

可以看得出来,这就是遍历二叉树,最终比较器获得的值==0的也就是相等的节点对象就是要获取的值。

大家应该可以看得出来,如果比较器出现 == 0 的情况才会返回,如果!= 0 则一直会进行遍历。

来看一个问题:
TreeMap解析
比较器是比较两个字符串的长度。
我们的put操作是没有问题的,因为键没有相同的,而且只存在两种类型>0或<0,所以所有的值都是分布在左右子树上;
但是get操作,那么问题来了,由于比较器返回三种类型的值>0、<0 、== 0
所以一旦存在有两个键的length相等,那么可以想一下,
每当到达匹配到相同值的时候,由于比较器返回的是>0或<0,不会直接return,所以这个操作会继续do-while循环,

TreeMap解析

当比较器的值相等的时候就会才会直接返回当前节点对象,但是毫无疑问该节点是没有值的,所以总是会返回null。

使用TreeMap首先需要 键唯一;

如果出现在比较器中的返回值对于0有三种情况,

put操作没有问题,会生成完整的二叉树,

get操作有问题,就会出现为null的情况!

上一篇:TreeMap自然排序和定制排序


下一篇:HashMap剖析及原理实现