2

我正在编写 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 语句。多次检查代码，在我看来这不应该是这种情况，因为有一个返回语句不需要任何布尔语句为真。

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

4

1 回答 1

0

关于“额外”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)for just else（您应该知道，如果执行该块是因为 if 必须为真。

于 2012-11-02T08:56:41.200 回答