08.映射

映射 Map

在python中，这个东西叫做字典dict

key:value
键值对的数据结构
根据Key ，寻找Value

有序映射：键具有顺序性<--基于搜索树
无序映射：键没有顺序性<--基于哈希表

多重映射：多重映射，支持储存多个相同键的键值对

思考练习：集合和映射之间的关系，可以通过集合(映射)的底层实现，包装成相应的映射(集合)，
以映射底层为基础实现集合，只保存Key, Value置为 null
以集合底层实现映射，将Key和Value封装起来，当做集合的一个值

映射接口

Map.java

package setAndMap2;

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();
}

基于链表的映射

LinkedListMap.java

package setAndMap2;
import setAndMap.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 this.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 = this.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("Set failed, no such key -- '" + key + "'");

        node.value = newValue;
    }

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

        return null;
    }

    public static void main(String[] args){

        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)){
            System.out.println("Total words: " + words.size());

            LinkedListMap<String, Integer> map = new LinkedListMap<>();
            for(String word: words){
                if(map.contains(word))
                    map.set(word, map.get(word) + 1);
                else
                    map.add(word, 1);
            }

            System.out.println("Total: " + map.getSize());
            System.out.println("pride:" + map.get("pride"));
        }
    }
}

基于二分搜索树的映射

package setAndMap2;

import setAndMap.FileOperation;

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;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

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

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

    /**向二分搜索树中添加元素*/
    @Override
    public void add(K key, V value){
        root = add(root, 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 {
            node.value = value;
        }

        return node;
    }

    /**返回以node为根节点的二分搜索树中，key所在的节点,调用的时候传入root*/
    private Node getNode(Node node,K key){
        if(node == null)
            return null;

        if(key.compareTo(node.key) == 0)
            return node;
        else if(key.compareTo(node.key) < 0)
            return getNode(node.left, key);
        else
            return getNode(node.right, key);
    }

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

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

    @Override
    public void set(K key, V value){
        Node node = this.getNode(root, key);
        if(node == null)
            throw new IllegalArgumentException("Set failed, no such key");

        node.value = value;
    }

    /**返回以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 {
            /**综合考虑，分情况讨论
             * 待删除的节点左子树为空*/
            if(node.left == null){
                Node rightNode = node.right;
                size --;
                node.right = null;
                return rightNode;
            }

            /**待删除的节点右子树为空*/
            if(node.right == null){
                Node leftNode = node.left;
                size --;
                node.left = null;
                return leftNode;
            }

            /**待删除节点的左右均不为空
             * 在待删除的右子树上寻找最小的节点来代替当前节点的位置*/
            Node successor = minimum(node.right);
            node.right = removeMin(node.right);
            successor.left = node.left;
            successor.right = node.right;

            node.left = node.right = null;
            return successor;

        }
    }

    /**测试代码，入口函数*/
    public static void main(String[] args){
        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)){
            System.out.println("Total words:" + words.size());

            BSTMap<String, Integer> map = new BSTMap<>();
            for( String word : words){
                if(map.contains(word))
                    map.set(word, map.get(word) + 1);
                else
                    map.add(word, 1);
            }
            System.out.println("Total different words: " + map.getSize());
            System.out.println("Frequency of PRIDE: " + map.get("pride"));
            System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
        }

        System.out.println();
    }
}

基于二分搜索树与链表算法时间复杂度的比较

Main.java

package setAndMap2;

import setAndMap.FileOperation;

import java.util.ArrayList;

public class Main {

    public static double testMap(Map<String, Integer> map, String filename){
        long startTime = System.nanoTime();

        System.out.println(filename);
        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile(filename, words)) {
            System.out.println("Total words: " + words.size());

            for(String word : words){
                if(map.contains(word)){
                    map.set(word, map.get(word) + 1);
                } else
                    map.add(word, 1);
            }

            System.out.println("different: " + map.getSize());
            System.out.println("Frequency of PRIDE: " + map.get("pride"));
            System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));

        }

        return (System.nanoTime() - startTime) / 1000000000.0;
    }
    public static void main(String[] args){

        String filename = "pride-and-prejudice.txt";

        BSTMap<String, Integer> bstMap = new BSTMap<>();
        double time1 = testMap(bstMap, filename);

        System.out.println("BStMap: " + time1 + " s");
        System.out.println();

        LinkedListMap<String, Integer> linkedListMap = new LinkedListMap<>();
        double time2 = testMap(linkedListMap, filename);
        System.out.println("LinkedListMap: " + time2 + " s");
    }
}

leetCode

349.两个数据的交集

Solution.java

package setAndMap;
import java.util.ArrayList;
import java.util.TreeSet;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for(int num : nums1){
            treeSet.add(num);
        }

        ArrayList<Integer> arrayList = new ArrayList<>();
        for(int num : nums2){
            if(treeSet.contains(num)){
                arrayList.add(num);
                treeSet.remove(num);
            }
        }

        int[] array = new int[arrayList.size()];
        for(int i = 0; i < array.length; i++){
            array[i] = arrayList.get(i);
        }

        return array;
    }
}

350.两个数据的交集

Solution.java

package setAndMap2;

import java.util.ArrayList;
import java.util.TreeMap;
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int num : nums1){
            if(!map.containsKey(num))
                map.put(num, 1);
            else
                map.put(num, map.get(num) + 1);
        }

        ArrayList<Integer> list = new ArrayList<>();
        for(int num : nums2){
            if(map.containsKey(num)){
                list.add(num);
                map.put(num, map.get(num) - 1);
                if(map.get(num) == 0)
                    map.remove(num);
            }
        }

        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i ++){
            res[i] = list.get(i);
        }

        return res;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 转:golang实现线程安全的map
    转载自：https://halfrost.com/go_map_chapter_one/ https://half...
    HuJay阅读 6,183评论 1赞 5
  • Java学习总结之集合
    Java集合框架 Java中封装了许多常用的数据结构，称为集合框架，可以有效组织数据，提高程序性能。最初Java只...
    Steven1997阅读 967评论 0赞 2
  • Spring Cloud
    Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具（例如配置管理，服务发现，断路器，智...
    卡卡罗2017阅读 134,969评论 19赞 139
  • 冷，写成这样我也是醉了
    终于，找了这么久终于找到你了，在我一脸蒙圈的表情下，一个不知名的生物钻到我的体内， 黑暗慢慢的散去，随之而来的是熟...
    二十四twentyfour阅读 247评论 0赞 0
  • 穷游这件小事
    穷游网的CEO这样定义穷游：穷尽天下，要游遍世界。在这气吞山河的气势下，我解释一下我的穷游，就是字面意思：囊中...
    栋博阅读 467评论 0赞 1