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;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,948评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,371评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,490评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,521评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,627评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,842评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,997评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,741评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,203评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,534评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,673评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,339评论 4赞 330
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,955评论 3赞 313
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,770评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,000评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,394评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,562评论 2赞 349

推荐阅读更多精彩内容

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