Java TreeMap實現獲取和放置方法

我在寫一個TreeMap的實現，並且在get和put方法中遇到了問題。這裏是代碼：Java TreeMap實現獲取和放置方法

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語句不需要任何布爾語句爲真。

在測試put方法時，我得到了一個NPE。我認爲我的代碼有一些非常重要的邏輯錯誤，因爲我似乎無法弄清楚什麼是錯誤的。如果你可以請指出我正確的方向來解決這些各種錯誤，這將是有益的。謝謝。

來源

2012-11-02 user1547050

好了，第一個'if'需求 – irrelephant

如果你得到一個NPE，請發佈堆棧跟蹤... – home

你在哪裏設置key值？map有鍵的事實並不意味着它有一個'key'屬性（它們有一堆它們，不能存儲在它裏面）它是一個樹形地圖，因爲它是一個用樹實現的地圖，而不是其他的方式，所以它是一個地圖!! – SJuan76

關於「額外」 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所以你已經把所有的情況。但是，這不是因爲編譯器的情況下：

編譯器不知道的this.key.compareTo(key)值在所有三個執行相同。即使它具有檢查方法的智能，並且看到它沒有使用任何其他輸入來獲得結果（它不會），但編譯器無法知道另一個線程是否正在同時更改這些鍵的值。
即使你做了int value=this.key.compareTo(key)並且後來對value執行檢查，編譯器也不檢查連續的if-elsif是否覆蓋了所有的值範圍。無論如何，出於性能/併發的原因，我建議你使用這種方法只調用compareTo一次。

最簡單的解決將是隻是改變了過去else if (this.key.compareTo(key) > 0)只是else（你應該知道，如果執行該塊是因爲如果必須是真實的。

來源

2012-11-02 08:56:41 SJuan76

...因爲'this .key.compareTo（鑰匙） '可能是一個複雜的操作，你應該只計算一次表達式並將其存儲在局部變量中。 – Axel

Java TreeMap實現獲取和放置方法

回答

相關問題