思维导图

什么是映射：

  映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。

  在很多特定的数学领域中，这个术语用来描述具有与该领域相关联的特定性质函数，例如，在拓扑学中的连续函数，线性代数中的线性变换等等
说的通俗点：

即存储(键，值)数据对的数据结构(Key,Value),我们可以根据键(Key)来寻找值(Value)

映射的分类

  根据其底层实现的不同，分为链表映射、二叉树映射等等。

实现步骤：

代码部分:

链表实现:

public class LinkedListMap<K, V> implements Map<K, V> {
    private class Node {
        public K key;
        public V value;
        public Node next;

        public Node() {

        }

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        this.dummyHead = new Node();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public Node getNode(K key) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) == null ? false : true;
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            dummyHead.next = new Node(key, value, dummyHead.next);
            size++;
        } else {
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        Node pre = dummyHead;
        while (pre.next != null) {
            if (pre.next.key.equals(key)) {
                Node delNode = pre.next;
                pre.next = delNode.next;
                delNode.next = null;
                size--;
                return delNode.value;
            }
            pre = pre.next;
        }
        return null;
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            throw new IllegalArgumentException("doesn't exist");
        }
        node.value = value;
    }
}

二叉搜索树实现:

public class BinarySearchTreeMap<K extends Comparable<K>, V> implements Map<K, V> {
    private class TreeNode {
        public K key;
        public V value;
        public TreeNode left, right;

        public TreeNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private TreeNode root;
    private int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(K key, V value) {
        root = add(root, key, value);
    }

    private TreeNode add(TreeNode treeNode, K key, V value) {
        if (treeNode == null) {
            size++;
            treeNode = new TreeNode(key, value);
        } else if (key.compareTo(treeNode.key) < 0) {
            treeNode.left = add(treeNode.left, key, value);
        } else if (key.compareTo(treeNode.key) > 0) {
            treeNode.right = add(treeNode.right, key, value);
        } else {
            treeNode.value = value;
        }
        return treeNode;
    }

    public TreeNode getTreeNode(TreeNode treeNode, K key) {
        if (treeNode == null) {
            return null;
        }
        if (key.compareTo(treeNode.key) == 0) {
            return treeNode;
        } else if (key.compareTo(treeNode.key) < 0) {
            return getTreeNode(treeNode.left, key);
        } else {
            return getTreeNode(treeNode.right, key);
        }
    }

    @Override
    public V get(K key) {
        TreeNode treeNode = getTreeNode(root, key);
        return treeNode == null ? null : treeNode.value;
    }

    @Override
    public boolean contains(K key) {
        return getTreeNode(root, key) == null ? false : true;
    }

    @Override
    public void set(K key, V value) {
        TreeNode treeNode = getTreeNode(root, key);
        if (treeNode != null) {
            treeNode.value = value;
        } else throw new IllegalArgumentException(key + "doesn't exist");
    }


    private TreeNode getMiniumTreeNode(TreeNode node) {
        if (node.left == null) {
            return node;
        }
        return getMiniumTreeNode(node.left);
    }

    //删除以treeNode为根的二叉搜索树的最小节点
    //返回删除最小节点后的树
    private TreeNode removeMiniumTreeNode(TreeNode treeNode) {
        if (treeNode.left == null) {
            TreeNode rightTreeNode = treeNode.right;
            treeNode.right = null;
            size--;
            return treeNode;
        }
        treeNode.left = removeMiniumTreeNode(treeNode.left);
        return treeNode;
    }

    @Override
    public V remove(K key) {
        TreeNode treeNode = getTreeNode(root, key);
        if ((treeNode != null)) {
            root = remove(root, key);
            return treeNode.value;
        }
        return null;
    }

    private TreeNode remove(TreeNode treeNode, K key) {
        if (treeNode == null) {
            return null;
        }
        if (key.compareTo(treeNode.key) < 0) {
            treeNode.left = remove(treeNode.left, key);
            return treeNode;
        } else if (key.compareTo(treeNode.key) > 0) {
            treeNode.right = remove(treeNode.right, key);
            return treeNode;
        } else {
            if (treeNode.left == null) {
                TreeNode rightTreeNode = treeNode.right;
                treeNode.right = null;
                size--;
                return rightTreeNode;
            }
            if (treeNode.right == null) {
                TreeNode leftTreeNode = treeNode.left;
                treeNode.left = null;
                size--;
                return leftTreeNode;
            }

            TreeNode successor = getMiniumTreeNode(treeNode);
            successor.right = removeMiniumTreeNode(treeNode);
            successor.left = treeNode.left;
            treeNode.left = treeNode.right = null;
            return successor;
        }
    }
}

复杂度分析