Java TreeMap实现get和put方法

Question

我正在编写 TreeMap 的实现，但在使用 get 和 put 方法时遇到了问题。这是代码:

public class MyTreeMap<K extends Comparable<? super K>,V> extends AbstractMap<K,V>  {


K key;
V value;
int height;
MyTreeMap<K,V> left,right;
int size;

private V get(K searchKey) {
    if(this.isEmpty())
        return null;//it needs an exception

    if(this.key.compareTo(searchKey) == 0)
        return this.value;
    else if(this.key.compareTo(searchKey) > 0)
        return this.left.get(searchKey);
    else
        return this.right.get(searchKey);
}

public V put(K key, V value) {

    if(this.containsKey(key)) {
        if(this.key.compareTo(key) == 0) {
            V temp = this.value;
            this.value = value;
            return temp;
        }

        else if(this.key.compareTo(key) < 0)
            return this.right.put(key, value);
        else if(this.key.compareTo(key) > 0)
            return this.left.put(key, value);
    }

    else {
        if(this.isLeaf() || this.isEmpty()) {
            if(this.key.compareTo(key) > 0) //this line gives NPE during tests
                this.left = new MyTreeMap(key,value,null,null);
            else
                this.right = new MyTreeMap(key,value,null,null);

               //check for balance and rebalance if needed
            this.size++;
            this.setHeight();
            return null;
        }

        else {
            if(this.key.compareTo(key) > 0)
                return this.left.put(key, value);
            else
                return this.right.put(key, value);
        }
    }
}

最疯狂的错误是 put 方法需要另一个 return 语句。多次检查代码，在我看来不应该是这种情况，因为有一个 return 语句不需要任何 boolean 语句为真。

在测试 put 方法时，我遇到了 NPE。我认为我的代码存在一些非常重要的逻辑错误，因为我似乎无法弄清楚哪里出了问题。如果您能指出正确的方向来修复这些各种错误，那将很有帮助。谢谢。

Answer 1

关于“额外”return声明:

if(this.containsKey(key)) {
    if(this.key.compareTo(key) == 0) {
        V temp = this.value;
        this.value = value;
        return temp;
    }

    else if(this.key.compareTo(key) < 0)
        return this.right.put(key, value);
    else if(this.key.compareTo(key) > 0)
        return this.left.put(key, value);
}

您的逻辑是您正在检查 this.key.compareTo(key)反对<0 , >0和 ==0所以你已经涵盖了所有的案例。但对于编译器来说情况并非如此，因为:

1. 编译器不知道this.key.compareTo(key) 的值是否为在所有三个执行中都是相同的。即使它具有检查方法并看到它没有使用任何其他输入来获取结果的智能(它没有)，编译器也无法知道是否另一个线程正在同时更改键的值。

2. 即使你这样做了int value=this.key.compareTo(key)然后对 value 执行检查，编译器不会检查连续的 if-elsif 是否覆盖所有值范围。无论如何，出于性能/并发原因，我建议您使用这种方法只调用 compareTo一次。

最简单的修复方法就是更改最后一个 else if (this.key.compareTo(key) > 0)只为 else (正如您应该知道的那样，如果该 block 被执行是因为 if 必须为真。