Implement HashMap using BST

把核心的逻辑都放在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"));
    }

}