实现映射

Aug 02, 2018 Homxu

映射也就是Map,这里是指一对一的映射。也成为字典。

映射迎来存储键值数据对(Key,Value)
根据Key寻找对应的Value
用链表或者二分搜索树实现比较简单

BST的结构:

class Node {
  K key;
  V value;
  Node left;
  Node right;
}

链表的结构:

class Node {
  K key;
  V value;
  Node next;
}

即本来存储一个数据的节点现在存储两个(Key,Value).

定义Map接口:

public interface Map<K,V> {
    void add(K key,V value);
    V remove(K key);            //删除key对应的键值对,并返回值
    boolean contains(K key);  //是否存已在key
    V get(K key);               //获得key对应的value值
    void set(K key,V newValue); //更新值
    int getSize();
    boolean isEmpty();
}

基于链表实现Map

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 node){
            this.key = key;
            this.value = value;
            this.next = null;
        }
        public Node(K key){
            this(key,null,null);
        }
        public Node(){
            this(null,null,null);
        }

        public String toString(){
            return key.toString() + ":" + value.toString();
        }
    }

    private Node dummyHead;
    private int size;
    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    @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 prev = dummyHead;
        while(prev.next != null){
            if(prev.next.key.equals(key))
                break;
            prev = prev.next;
        }
        Node delNode;
        if(prev.next != null){
            delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

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

    @Override
    public void set(K key, V newValue) {
        Node result = getNode(key);
        if(result != null)
            result.value = newValue;
        else
            throw new IllegalArgumentException(key + "doesn't exists");
    }

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

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

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

基于二分搜索树实现Map

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;
            this.left = null;
            this.right = null;
        }
    }
    private Node root;
    private int size;
    @Override
    //向二分搜索树中添加新元素(key,value)
    public void add(K key, V value) {
        root = add(root,key,value);
    }

    @Override
    //借助辅助函数remove(Node node,K key)
    public V remove(K key) {
        Node node = getNode(root,key);
        if(node != null){
            root = remove(root,key);
            return node.value;
        }
        return null;
    }

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

    @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;
    }

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

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

    //向以node为根的二分搜索树中插入元素,采用递归算法
    //返回插入新节点后二分搜索树的根
    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);
        }
        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.compareTo(node.key) == 0){
            return node;
        }
        if(key.compareTo(node.key) < 0){
            return getNode(node.left,key);
        }
        else{ //key.compareTo(node.key) > 0)
            return getNode(node.right,key);
        }
    }

    //删除掉以node为根的二分搜索树中键为key的节点
    //返回删除节点后新的二分搜索树的根
    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 = minmum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

    //返回以node为根的二分搜索树的最小值所在的节点
    private Node minmum(Node node){
        if(node.left == null){
            return node;
        }
        return minmum(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;
    }
}

其实明显可以感受到BSTMap的存储速度要快于LinkedListMap

基于链表的Map和基于二分搜索树的Map的时间复杂度对比

操作	LinkedListMap	BSTMap(平均)	BSTMap最差)
增add	O(n)	O(logn)	O(n)
删remove	O(n)	O(logn)	O(n)
改set	O(n)	O(logn)	O(n)
查get	O(n)	O(logn)	O(n)
查contains	O(n)	O(logn)	O(n)

映射也就是Map,这里是指一对一的映射。也成为字典。

映射迎来存储键值数据对(Key,Value)
根据Key寻找对应的Value
用链表或者二分搜索树实现比较简单

BST的结构:

class Node {
  K key;
  V value;
  Node left;
  Node right;
}

链表的结构:

class Node {
  K key;
  V value;
  Node next;
}

即本来存储一个数据的节点现在存储两个(Key,Value).

定义Map接口:

public interface Map<K,V> {
    void add(K key,V value);
    V remove(K key);            //删除key对应的键值对,并返回值
    boolean contains(K key);  //是否存已在key
    V get(K key);               //获得key对应的value值
    void set(K key,V newValue); //更新值
    int getSize();
    boolean isEmpty();
}

基于链表实现Map

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 node){
            this.key = key;
            this.value = value;
            this.next = null;
        }
        public Node(K key){
            this(key,null,null);
        }
        public Node(){
            this(null,null,null);
        }

        public String toString(){
            return key.toString() + ":" + value.toString();
        }
    }

    private Node dummyHead;
    private int size;
    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    @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 prev = dummyHead;
        while(prev.next != null){
            if(prev.next.key.equals(key))
                break;
            prev = prev.next;
        }
        Node delNode;
        if(prev.next != null){
            delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

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

    @Override
    public void set(K key, V newValue) {
        Node result = getNode(key);
        if(result != null)
            result.value = newValue;
        else
            throw new IllegalArgumentException(key + "doesn't exists");
    }

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

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

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

基于二分搜索树实现Map

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;
            this.left = null;
            this.right = null;
        }
    }
    private Node root;
    private int size;
    @Override
    //向二分搜索树中添加新元素(key,value)
    public void add(K key, V value) {
        root = add(root,key,value);
    }

    @Override
    //借助辅助函数remove(Node node,K key)
    public V remove(K key) {
        Node node = getNode(root,key);
        if(node != null){
            root = remove(root,key);
            return node.value;
        }
        return null;
    }

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

    @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;
    }

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

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

    //向以node为根的二分搜索树中插入元素,采用递归算法
    //返回插入新节点后二分搜索树的根
    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);
        }
        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.compareTo(node.key) == 0){
            return node;
        }
        if(key.compareTo(node.key) < 0){
            return getNode(node.left,key);
        }
        else{ //key.compareTo(node.key) > 0)
            return getNode(node.right,key);
        }
    }

    //删除掉以node为根的二分搜索树中键为key的节点
    //返回删除节点后新的二分搜索树的根
    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 = minmum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

    //返回以node为根的二分搜索树的最小值所在的节点
    private Node minmum(Node node){
        if(node.left == null){
            return node;
        }
        return minmum(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;
    }
}

其实明显可以感受到BSTMap的存储速度要快于LinkedListMap

基于链表的Map和基于二分搜索树的Map的时间复杂度对比

操作	LinkedListMap	BSTMap(平均)	BSTMap最差)
增add	O(n)	O(logn)	O(n)
删remove	O(n)	O(logn)	O(n)
改set	O(n)	O(logn)	O(n)
查get	O(n)	O(logn)	O(n)
查contains	O(n)	O(logn)	O(n)