Java温故而知新-自定义Map工具类

实现原理：利用二叉树结构的高效查询。

接口

package com.itkey.javareview.util;

/**
 * 定义一个根据树状结构存储的接口，同时实现数据的保存和查询
 * @param  要保存数据的key类型（根据key找到value）
 * @param  要保存的核心的数据内容
 */
public interface IMap {        //实现树结构的数据查询

    /**
     * 向Map集合之中保存有相应的数据内容，所有的内容都不允许为空
     * @param key 要保存数据的key,key不允许重复
     * @param value 要保存的数据的value，内容不允许为空
     * @return 如果指定的key不存在返回null，如果key存在了，则将新的内容替换掉旧的内容，并返回旧信息
     */
    public V put(K key,V value);

    /**
     * 根据key查询对应的value数据
     * @param key 数据查询的key,如果不存在则不返回任何的结果
     * @return key 存在返回具体的数据，否则返回 null
     */
    public V get(K key);

    /**
     * 获取保存元素的数量
     * @return 元素个数
     */
    public int size();

    /**
     * 获取IMap的默认实例化对象
     * @param  与IMap接口K类型相同，一定要实现Comparable接口
     * @param  与IMap接口V类型相同
     * @return IMap对象实例
     */
    public static  IMap getInstance(){
        return new BinaryTreeMapImpl();
    }
}

实现类

package com.itkey.javareview.util;

public class BinaryTreeMapImpl implements IMap {
    //1、如果要想进行树状结构的存储，必须要想办法把key和value进行了一次包装处理
    private class Entry implements Comparable{     //用户不关注此类
        private K key;      //key所在的类必须实现Comparable接口
        private V value;

        public Entry(K key, V value){
            this.key = key;
            this.value = value;
        }
        @Override
        public int compareTo(Entry o) {                   //所有的数据依据key实现排序操作
            return ((Comparable)this.key).compareTo(o.key);
        }
    }

    //2、如果要想进行数据的存储肯定要有一个Node节点存在
    private class Node{
        private Entry data;        //每一个节点保存的是Entry对象实例
        private Node left;
        private Node right;
        public Node(Entry data){   //节点必须要包裹Entry对象
            this.data = data;
        }

        public V addNode(Node newNode){     //用递归方式实现
            if(this.data.compareTo(newNode.data) 0){
                if(this.left == null){
                    this.left = newNode;            //保存左节点
                }else {
                    return this.left.addNode(newNode);
                }
            }else{      //key 存在
                V old = this.data.value;    //获取旧的内容
                this.data.value = newNode.data.value;       //替换旧的信息
                return old;     //返回旧的数据
            }
            return null;
        }

        public V getNode(K key){
            if(this.data.key.equals(key)){          //key相同
                return this.data.value;     //返回对应的 value
            }else {
                if(((Comparable)this.data.key).compareTo(key)