• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题

极客笔记 Geekerstar 11个月前 (05-18) 364次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

首先来测试一下

import java.util.ArrayList;

public class Main {

    private 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("Total different words: " + map.getSize());
            System.out.println("Frequency of PRIDE: " + map.get("pride"));
            System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
        }

        long endTime = System.nanoTime();

        return (endTime - 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("BST Map: " + time1 + " s");

        System.out.println();

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

    }
}

现在我们就可以运行一下我们的程序,对于二分搜素树BSTMap很快就得出了结果,而对于LinkedListMap则等了很长时间才出结果


对于这个十几万的数据,基于二分搜索树的映射用了0.74秒。

而对于链表的映射用了32秒

映射的时间复杂度总结


前面基于代码的方式我们直观的看到了基于二分搜素树实现的映射和基于链表的映射他们的时间复杂度的差距。

有序映射和无序映射

  • 有序映射中的键具有顺序性<--基于搜索树的实现
  • 无序映射中的键没有顺序性<--基于哈希表的实现

集合和映射的关系

这一章我们学习了集合和映射两种相对比较高层的数据结构,在具体实现这两种数据结构的时候,都可以既使用链表,又使用二分搜素树。

实现过程中,其实有很多相同之处,甚至可以理解为:对于映射来说,本身就是一个集合

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(6.8)映射的复杂度分析和更多映射相关问题
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00