目录
一、导论
二、Map
三、Set
本文找先不涉及两种数据结构的底层,目标是:
理解Map和Set的大体框架,了解他们有什么用,用在哪里的,然后再从浅层深入底层。
小编认为:
先了解也下Map和Set大体是用来做什么,如何用,用在那,是首先应该学的。
对底层的掌握固然重要,但实际上掌握底层的最终目的不就是为了让我们更好的运用这种数据结构吗?如果直接深入底层,可能啃到最后,还不直到Map和Set到底是个什么东西。
仅限小编个人观点。😘
本文找涉及的概念相对较多,大家忍忍,忍一下,就好咯。
一、导论
Map和Set是一种专门用来进行搜索的容器或者数据结构,其搜索效率与具体实例化的子类有关。
我们之前学过的常见搜索方式有:
常见方式:
1.直接遍历,时间复杂度为O(N),如果元素太多,效率就会太低。
2.二分查找,时间复杂度为O(logN),但是前提要求数据是有序的。
关于静态查找:
静态查找其实就是我们通俗意义上的查找,既查找一个特定的元素是否存在,既:
(1)查看某特定的关键字是否在表中(判断性查找)
(2)检索某特定关键字数据元素的各种属性(检索性查找)
上述查找方式比较适合静态查找,既:不会对元素进行插入和删除,但在实际应用场景中,比如:
场景:
1.按照名字查找此人的成绩。
2.在通讯录中,依照名字,查找某人的联系方式。
3.查询自己是否已被录取,既自己是否在名单中(不重复集合)。
关于动态查找:
(1)动态查找是指在一个动态数据集中搜索某个特定元素的过程。
(2)动态数据集是指在查找过程中数据集的内容可能会改变,即可以插入、删除、修改元素。
上述这三种是动态查找,显然前面那些静态查找不适合这种引用场景,为了解决这种问题,适用于动态查找的数据结构出现了,既Map和Set。
二、Map
刚刚阐释的都比较假大空,我们举个显示生活中的例子,来认识一下什么事Map
在中国,每个人的身份证号一定是不同的,前3位代表所属省份,7到14位代表出生日期等。
但是中国的人口很多,身份证号不同,但是名字却有很多人是一样的。
那么在国家的人员信息系统中,如何储存这些信息呢?
咱们先入为主,自然想到的就是Map。
Map的特点是:
一次储存一对元素,关键字(Key)和值(Val)。
Key就相当于身份证号,Val就相当于咱么自己的名字。
Key一定不能重复,而Val是可以重复的。(身份证号唯一,名字不一定唯一)
每一对Key和Val是 11对应的。(通过身份证号,就可以查询这个人的名字)
专业术语:
Map的这种储存模型我们称为:Key-Value模型
一对 Key-Value 我们称为:键值对
在java集合框架中的Map:
HashMap和TreeMap的底层分别是哈希表、红黑树。
HashMap的搜索效率可以达到恐怖的O(1)也就是常量级。
TreeMap的搜索效率是O(logN),也很快。
不过这两者都是用空间效率去换取的时间效率。
关于Map的注意事项:
1. Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap,这也印证了前文所说实例化不同对象,搜索效率是不同的。
2. Map中存放键值对的Key是唯一的,value是可以重复的
3. 在TreeMap中插入键值对时,key不能为空,否则就会抛NullPointerException异常,value可以为空。但是HashMap的key和value都可以为空。
5. Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行 重新插入。
三、Set
所以讲了Map,Set就好讲了。
Set只含有关键字Key,Key是唯一的,相当于Map的“阉割版本”。
这就说明Set失去了,把两个元素建立联系的能力(键值对的11映射)
但是他保留了Key,这也是Set的一个很大的特点:
在Set中的元素,一定没有重复的,因为每个Key是唯一的,可以达到去重的目的。
在java集合框架中的Set:
关于Set的一些注意事项:
1. Set是继承自Collection的一个接口类
2. Set中只存储了key,并且要求key一定要唯一
3. TreeSet的底层是使用Map来实现的,其使用key与Object的一个默认对象作为键值对插入到Map中的---》所以讲了Map,Set就好讲了
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入
7. TreeSet中不能插入null的key,HashSet可以。
8.. Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复)
以上就是了解Map和Set的全部内容了。
小编下一篇文章将会讲到Java中Map和Set的具体使用案例(语法),然后做一下相关的题目,加深对Map和Set的使用场景和印象。