数据结构玩转数据结构 7-8 映射的复杂度分析和更多映射相关问题

标签：node Node null return 映射复杂度 value key 数据结构

0　　　　课程地址

https://coding.imooc.com/lesson/207.html#mid=13710

1　　　　重点关注

1.1　　　　结论

使用二叉树实现集合Set性能优于使用链表实现集合Set.

1.2　　　　链表和二叉树实现集合类复杂度分析

链表的时间复杂度为O(n),n为元素个数，

包含元素，contains方法时间复杂度为O(n),

增加元素，要首先用contains方法判断链表中是否有该元素，contains方法时间复杂度为O(n),

删除元素，while循环判断元素是否存在，存在则删除，所以复杂度也为O(n)

二叉树的时间复杂度为O(h),h为二叉树深度

包含元素，contains方法时间复杂度为O(h),每次基本上能过滤一半元素，时间复杂度为O(h),

增加元素，add方法递归调用，每次基本上能过滤一半元素，时间复杂度为O(h),

删除元素，每次基本上能过滤一半元素，时间复杂度为O(h),

h和n的关系

满二叉树的情况，推导见1.3

n=2^h-1;

h = log2(n)

如果二叉树按照顺序排列，复杂度和链表复杂度一样，如何解决这种情况

使用平衡二叉树

1.3　　　　h和n的关系推导

2　　　　课程内容

3　　　　Coding

3.1　　　　链表和二叉树实现映射的性能测试

需求

分别使用链表和二叉树实现的映射统计傲慢与偏见的英文词汇量,比较二者性能差异

结论：

二叉树性能要优于链表

接口

package com.company;

public interface Map<K,V> {

    /**
     *  是否为空
     * @author weidoudou
     * @date 2022/12/26 17:50
     * @return boolean
     **/
    boolean isEmpty();

    /**
     * 获取元素个数
     * @author weidoudou
     * @date 2022/12/26 17:51
     * @return int
     **/
    int getSize();

    /**
     * 是否包含
     * @author weidoudou
     * @date 2022/12/26 17:52
     * @param key 请添加参数描述
     * @return boolean
     **/
    boolean contains(K key);

    /**
     * 获取元素
     * @author weidoudou
     * @date 2022/12/26 17:59
     * @param key 请添加参数描述
     * @return V
     **/
    V get(K key);

    /**
     * 新增元素
     * @author weidoudou
     * @date 2022/12/26 17:53
     * @param key 请添加参数描述
     * @param  value 请添加参数描述
     * @return void
     **/
    void add(K key,V value);

    /**
     * 修改元素
     * @author weidoudou
     * @date 2022/12/26 17:54
     * @param key 请添加参数描述
     * @param  value 请添加参数描述
     * @return void
     **/
    void set(K key,V value);

    /**
     * 删除元素
     * @author weidoudou
     * @date 2022/12/26 17:55
     * @param key 请添加参数描述
     * @return V
     **/
    V remove(K key);
}

链表类

package com.company;

public class LinkedListMap<K,V> implements Map<K,V>{

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

        public Node(){
            this(null,null,null);
        }

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

        public Node(K key){
           this(key,null,null);
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("key=").append(key);
            sb.append(", value=").append(value);
            sb.append('}');
            return sb.toString();
        }
    }

    private Node dummyHead;
    private  int size;

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



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

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

    //公用方法判断是否包含
    private Node containsKey(K key){
        Node curNode = dummyHead.next;
        while(curNode!=null){
            //想想这里为什么不用 =
            if(curNode.key.equals(key)){
                return curNode;
            }
            curNode = curNode.next;
        }
        return null;
    }

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

    @Override
    public V get(K key) {
        //这里没有考虑到空指针的情况，每次.方法的时候都需要注意
        return (null == containsKey(key)) ? null : (containsKey(key).value);
    }

    @Override
    public void add(K key, V value) {
        Node node = containsKey(key);
        //设计问题，这里，如果传入已有的key,则更新value,否则，新增（也可以传入已有的key后抛异常）
        if(null!=node){
            node.value = value;
        }else{
            dummyHead.next = new Node(key,value,dummyHead.next);
            size++;
        }
    }

    @Override
    public void set(K key, V value) {
        Node node = containsKey(key);
        if(null==node){
            throw new IllegalArgumentException("键值不存在");
        }
        node.value = value;
    }

    @Override
    public V remove(K key) {
        //1 是否包含
        //设计问题，如果key不存在，则不做任何操作
        if(!contains(key)){
            return null;
        }

        //2 定位
        Node preNode = dummyHead;
        while(preNode.next!=null){
            if(key.equals(preNode.next.key) ){
                break;
            }
            preNode = preNode.next;
        }

        //3 删除操作
        Node delNode = preNode.next;
        preNode.next = delNode.next;
        delNode.next = null;
        size--;
        return delNode.value;
    }
}

二叉树类

package com.company;

/**
 * 用二分搜索树实现 映射Map
 * @author weidoudou
 * @date 2023/1/1 10:38
 **/
public class BSTMap<K extends Comparable<K>,V> implements Map<K,V>{

    //1     定义Node
    class Node{
        private K key;
        private V value;
        private Node left,right;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("key=").append(key);
            sb.append(", value=").append(value);
            sb.append('}');
            return sb.toString();
        }
    }

    //2     定义属性
    private int size;
    private Node root;

    /**
     * 无参构造函数
     * @author weidoudou
     * @date 2023/1/1 11:09
     * @return null
     **/
    public BSTMap(){
        this.size = 0;
        this.root = null;
    }



    @Override
    public boolean isEmpty() {
        return size==0?true:false;
    }

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

    //3     定义包含函数
    private Node containsKey(K key,Node node){
        //结束条件
        if(null==node){
            return null;
        }

        //循环条件
        if(key.compareTo(node.key)<0){
            return containsKey(key,node.left);
        }else if(key.compareTo(node.key)>0){
            return containsKey(key, node.right);
        }else{//key.compareTo(node.key)=0 其实这个也是结束条件
            return node;
        }
    }

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

    @Override
    public V get(K key) {
        Node node = containsKey(key,root);
        if(null!=node){
            return node.value;
        }
        return null;
    }


    //3     递归，添加元素
    public void add(K key,V value,Node root){
        //3.1   终止条件
        //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断，因为已经调了containsKey方法判断了
        /*if(key.equals(root.e)){
            return;
        }*/

        //3.1.2 最终插入左孩子
        if(key.compareTo(root.key)<0 && root.left==null){
            root.left = new Node(key,value);
            size++;
            return;
        }

        //3.1.2 最终插入右孩子
        if(key.compareTo(root.key)>0 && root.right == null){
            root.right = new Node(key,value);
            size++;
            return;
        }

        //3.2   递归
        //3.2.1 递归左孩子
        if(key.compareTo(root.key)<0){
            add(key,value,root.left);
        }

        //3.2.2 递归右孩子
        if(key.compareTo(root.key)>0){
            add(key,value,root.right);
        }
    }

    @Override
    public void add(K key, V value) {
        Node node = containsKey(key,root);
        //未找到，插值
        if(node==null){
            //2.1   考虑特殊情况,如果是第一次调用，root为null
            if(root==null){
                root = new Node(key,value);
                size++;
            }else{
                //2.2   添加递归方法
                add(key,value,root);
            }
        }else{
            node.value = value;
        }
        //找到后，更新值
    }

    @Override
    public void set(K key, V value) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        node.value = value;
    }

    private Node remove(Node node,K key){
        //终止条件1 基本判断不到，因为已经判断了containskey
        /*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{
            //已找到要删除的元素
            //1 如果只有左子节点或只有右子节点，则直接将子节点替换
            if(node.left==null){
                return node.right;
            }else if(node.right==null){
                return node.left;
            }else{
                //2 如果有左子节点和右子节点，则寻找前驱或后继 对当前节点替换掉
                Node nodeMain = findMin(node.right);
                nodeMain.right = removMin(node.right);//这块一箭双雕，既把后继节点问题解决了，也把后继删除了
                nodeMain.left = node.left;
                node.left = node.right = null;
                return node;
            }
        }
    }

    private Node findMin(Node node){
        //1     终止条件
        if(node.left==null){
            return node;
        }

        //2     递归
        return findMin(node.left);
    }

    private Node removMin(Node node){
        //终止条件
        if(node.left==null){
            Node rightNode = node.right;
            node.right = null;
            return rightNode;
        }

        //递归
        node.left = removMin(node.left);
        return node;
    }

    /**
     * 删除任意元素 若删除元素节点下只有一个节点直接接上即可，若有两个节点，则找前驱或后继，本节找前驱
     * @author weidoudou
     * @date 2023/1/1 11:52
     * @param key 请添加参数描述
     * @return V
     **/
    @Override
    public V remove(K key) {
        Node node = containsKey(key,root);
        if(node == null){
            throw new IllegalArgumentException("要修改的值不存在");
        }
        size--;
        return remove(root, key).value;
    }
}

文件处理类：

package com.company;

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Locale;
import java.io.File;
import java.io.BufferedInputStream;
import java.io.IOException;

// 文件相关操作
public class FileOperation {

    // 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
    public static boolean readFile(String filename, ArrayList<String> words){

        if (filename == null || words == null){
            System.out.println("filename is null or words is null");
            return false;
        }

        // 文件读取
        Scanner scanner;

        try {
            File file = new File(filename);
            if(file.exists()){
                FileInputStream fis = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                scanner.useLocale(Locale.ENGLISH);
            }
            else
                return false;
        }
        catch(IOException ioe){
            System.out.println("Cannot open " + filename);
            return false;
        }

        // 简单分词
        // 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
        // 在这里只做demo展示用
        if (scanner.hasNextLine()) {

            String contents = scanner.useDelimiter("\\A").next();

            int start = firstCharacterIndex(contents, 0);
            for (int i = start + 1; i <= contents.length(); )
                if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
                    String word = contents.substring(start, i).toLowerCase();
                    words.add(word);
                    start = firstCharacterIndex(contents, i);
                    i = start + 1;
                } else
                    i++;
        }

        return true;
    }

    // 寻找字符串s中，从start的位置开始的第一个字母字符的位置
    private static int firstCharacterIndex(String s, int start){

        for( int i = start ; i < s.length() ; i ++ )
            if( Character.isLetter(s.charAt(i)) )
                return i;
        return s.length();
    }
}

测试类：

    private static double testTime(String fileName,Map<String,Integer> map){
        long time1 = System.nanoTime();

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile(fileName,words)){
            System.out.println("total words is "+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 words is "+map.getSize());
        System.out.println("pride size is"+map.get("pride"));
        System.out.println("prejudice size is"+map.get("prejudice"));


        long time2 = System.nanoTime();
        return (time2 - time1) / 1000000000.0;
    }

    public static void main(String[] args) {
        Map<String,Integer> map1 = new LinkedListMap<>();
        double time1 = testTime("pride-and-prejudice.txt",map1);
        System.out.println("time1==========="+time1);

        Map<String,Integer> map2 = new BSTMap<>();
        double time2 = testTime("pride-and-prejudice.txt",map2);
        System.out.println("time2==========="+time2);
    }

测试结果：

total words is 125901
different words is 6530
pride size is53
prejudice size is11
time1===========9.8596692
total words is 125901
different words is 6530
pride size is53
prejudice size is11
time2===========0.0791513

Process finished with exit code 0

标签：node,Node,null,return,映射,复杂度,value,key,数据结构
From： https://www.cnblogs.com/1446358788-qq/p/17019770.html

数据结构玩转数据结构 7-8 映射的复杂度分析和更多映射相关问题

0　　　　课程地址

1　　　　重点关注

1.1　　　　结论

1.2　　　　链表和二叉树实现集合类复杂度分析

1.3　　　　h和n的关系推导

2　　　　课程内容

3　　　　Coding

3.1　　　　链表和二叉树实现映射的性能测试

相关文章

赞助商

阅读排行

数据结构 玩转数据结构 7-8 映射的复杂度分析和更多映射相关问题

0 课程地址

1 重点关注

1.1 结论

1.2 链表和二叉树实现 集合类复杂度分析

1.3 h和n的关系推导

2 课程内容

3 Coding

3.1 链表和二叉树实现映射的性能测试

相关文章

赞助商

阅读排行

数据结构玩转数据结构 7-8 映射的复杂度分析和更多映射相关问题

0　　　　课程地址

1　　　　重点关注

1.1　　　　结论

1.2　　　　链表和二叉树实现集合类复杂度分析

1.3　　　　h和n的关系推导

2　　　　课程内容

3　　　　Coding

3.1　　　　链表和二叉树实现映射的性能测试