https://warmland.gitbooks.io/algorithm/content/interview/implement_hashmap_using_bst.html
把核心的逻辑都放在Node里面
所以Node的代码是：
public class MapNode<K extends Comparable<K>, V> {
private K key;
private V value;
private MapNode<K, V> left;
private MapNode<K, V> right;
public MapNode(K key, V value) {
this.key = key;
this.value = value;
}
public V put(K key, V value) {
if(this.key.compareTo(key) == 0) {
V oldValue = this.value;
this.value = value;
return oldValue;
} else if(this.key.compareTo(key) < 0) {
if(right == null) {
right = new MapNode(key, value);
return null;
} else {
return right.put(key, value);
}
} else {
if(left == null) {
left = new MapNode(key, value);
return null;
} else {
return left.put(key, value);
}
}
}
public V get(K key) {
if(this.key.compareTo(key) == 0) {
return this.value;
} else if(this.key.compareTo(key) < 0) {
return right == null? null: right.get(key);
} else {
return left == null? null: left.get(key);
}
}
}
Map部分的代码是：
public class ImplementHashmapUsingBST<K extends Comparable<K>, V> {
MapNode<K, V> root;
int size;
public ImplementHashmapUsingBST() {
size = 0;
}
public V get(K key) {
if(root == null) {
return null;
}
return root.get(key);
}
public V put(K key, V value) {
if(root == null){
root = new MapNode(key, value);
return null;
} else {
V oldValue = root.put(key, value);
if(oldValue == null) {
size++;
return null;
}
return oldValue;
}
}
public static void main(String[] args) {
ImplementHashmapUsingBST<String, String> sample = new ImplementHashmapUsingBST();
sample.put("Apple", "Fruit");
sample.put("Pork", "Meat");
System.out.println(sample.get("Apple"));
}
}
