映射Map

桃扇骨 2021-09-23 22:20 508阅读 0赞

## **数学理解：** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

## 接口实现： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]

package Map;
    
    public interface Map<K, V> { 
    
        void add(K key, V value);
    
        V remove(K key);
    
        boolean contains(K key);
    
        V get(K key);
    
        void set(K key, V newValue);
    
        int getSize();
    
        boolean isEmpty();
    }

## 1、基于链表实现映射 ##

package Map;
    
    import Set.FileOperation;
    
    import java.util.ArrayList;
    
    public class LinkedListMap<K, V> implements Map<K, V> { 
    
        private class Node{ 
            public K key;
            public V value;
            public Node next;
    
            public Node(K key, V value, Node next){ 
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public Node(K key, V value){ 
                this(key, value, null);
            }
    
            public Node(){ 
                this(null, null, null);
            }
    
            @Override
            public String toString(){ 
                return key.toString() + " : " + value.toString();
            }
        }
    
        private Node dummyHead;
        private int size;
    
        public LinkedListMap(){ 
            dummyHead = new Node();
            size = 0;
        }
    
        @Override
        public int getSize(){ 
            return size;
        }
    
        @Override
        public boolean isEmpty(){ 
            return size == 0;
        }
    
        private 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;
        }
    
        @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 void set(K key, V newValue){ 
            Node node = getNode(key);
            if(node == null)
                throw new IllegalArgumentException(key + " doesn't exist!");
    
            node.value = newValue;
        }
    
        @Override
        public V remove(K key){ 
    
            Node prev = dummyHead;
            while(prev.next != null){ 
                if(prev.next.key.equals(key))
                    break;
                prev = prev.next;
            }
    
            if(prev.next != null){ 
                Node delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
                size --;
                return delNode.value;
            }
    
            return null;
        }

## 2、基于二分搜索树实现映射 ##

package Map;
    
    import java.util.ArrayList;
    
    public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> { 
    
        private class Node { 
            public K key;
            public V value;
            public Node left, right;
    
            public Node(K key, V value) { 
                this.key = key;
                this.value = value;
                left = null;
                right = null;
            }
        }
    
        private Node root;
        private int size;
    
        public BSTMap() { 
            root = null;
            size = 0;
        }
    
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    
        // 向二分搜索树中添加新的元素(key, value)
        @Override
        public void add(K key, V value) { 
            root = add(root, key, value);
        }
    
        // 向以node为根的二分搜索树中插入元素(key, value)，递归算法
        // 返回插入新节点后二分搜索树的根
        private Node add(Node node, K key, V value) { 
    
            if (node == null) { 
                size++;
                return new Node(key, value);
            }
    
            if (key.compareTo(node.key) < 0)
                node.left = add(node.left, key, value);
            else if (key.compareTo(node.key) > 0)
                node.right = add(node.right, key, value);
            else // key.compareTo(node.key) == 0
                node.value = value;
    
            return node;
        }
    
        // 返回以node为根节点的二分搜索树中，key所在的节点
        private Node getNode(Node node, K key) { 
    
            if (node == null)
                return null;
    
            if (key.equals(node.key))
                return node;
            else if (key.compareTo(node.key) < 0)
                return getNode(node.left, key);
            else // if(key.compareTo(node.key) > 0)
                return getNode(node.right, key);
        }
    
        @Override
        public boolean contains(K key) { 
            return getNode(root, key) != null;
        }
    
        @Override
        public V get(K key) { 
    
            Node node = getNode(root, key);
            return node == null ? null : node.value;
        }
    
        @Override
        public void set(K key, V newValue) { 
            Node node = getNode(root, key);
            if (node == null)
                throw new IllegalArgumentException(key + " doesn't exist!");
    
            node.value = newValue;
        }
    
        // 返回以node为根的二分搜索树的最小值所在的节点
        private Node minimum(Node node) { 
            if (node.left == null)
                return node;
            return minimum(node.left);
        }
    
        // 删除掉以node为根的二分搜索树中的最小节点
        // 返回删除节点后新的二分搜索树的根
        private Node removeMin(Node node) { 
    
            if (node.left == null) { 
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
    
            node.left = removeMin(node.left);
            return node;
        }
    
        // 从二分搜索树中删除键为key的节点
        @Override
        public V remove(K key) { 
    
            Node node = getNode(root, key);
            if (node != null) { 
                root = remove(root, key);
                return node.value;
            }
            return null;
        }
    
        private Node remove(Node node, K key) { 
    
            if (node == null)
                return null;
    
            if (key.compareTo(node.key) < 0) { 
                node.left = remove(node.left, key);
                return node;
            } else if (key.compareTo(node.key) > 0) { 
                node.right = remove(node.right, key);
                return node;
            } else {    // key.compareTo(node.key) == 0
    
                // 待删除节点左子树为空的情况
                if (node.left == null) { 
                    Node rightNode = node.right;
                    node.right = null;
                    size--;
                    return rightNode;
                }
    
                // 待删除节点右子树为空的情况
                if (node.right == null) { 
                    Node leftNode = node.left;
                    node.left = null;
                    size--;
                    return leftNode;
                }
    
                // 待删除节点左右子树均不为空的情况
    
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node successor = minimum(node.right);
                successor.right = removeMin(node.right);
                successor.left = node.left;
    
                node.left = node.right = null;
                return successor;
            }
        }

## 映射的时间复杂度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/e42f8f02c1f64248a0cfaae144ed1dfb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/9fe0c6a17675494e862bb3ba12900a51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/92d66858e04e4020b78d5266d3224656.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/846ade5e3b144bc197357c9f1d035d4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]: /images/20210923/21a3c1787cef43d3b4b4d8c74b19e7c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]: /images/20210923/75baec4b10534d8d9fd5a37a5754a7d0.png