首页 > 其他分享 >【数据结构】TreeMap和TreeSet

【数据结构】TreeMap和TreeSet

时间:2024-08-15 11:23:20浏览次数:15  
标签:Map Set key TreeMap value Key 数据结构 TreeSet

目录


前言

Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关。

一般把搜索的数据称为关键字(Key),
和关键字对应的称为值(Value),
将其称之为Key-value的键值对。

所以搜索有两种模型:

  • 纯key模型:
  • key-value 模型

Map中存储的就是key-value的键值对,并且key必须是唯一的,
Set中只存储了Key。

TreeMap

使用TreeMap必须导包import java.util.TreeMap;,底层是一棵红黑树。

实现的接口

  • 实现了SortedMap表示TreeMap可以排序,
  • 没有实现Collection接口,但是value的类型是Collection。

内部类

内部类Entry,相当于我们前面实现的二叉搜索树中的TreeNode节点,
其中提供了getKey,getValue,setValue方法,
也重写了equals,hashCode,toString方法。
但是Map.Entry<K,V>并没有提供设置Key的方法

方法解释
K getKey()返回 entry 中的 key
V getValue()返回 entry 中的 value
V setValue(V value)将键值对中的value替换为指定value

常用方法

方法解释
V get(Object key)返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)返回 key 对应的 value,key 不存在,返回默认值defaultValue
V put(K key, V value)设置 key 对应的 value
V remove(Object key)删除 key 对应的映射关系
Set keySet()返回所有 key 的不重复集合
Collection values()返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()返回所有的 key-value 映射关系
boolean containsKey(Object key)判断是否包含 key
boolean containsValue(Object value)判断是否包含 value

注意事项:

  • Map中存放键值对的Key是唯一的,value是可以重复的;
  • 在TreeMap中插入键值对时,key不能为空,否则就会抛NullPointerException异常,value可以为空;
  • Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复);
  • Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复);
  • Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行重新插入。

TreeSet

其实TreeSet的底层就是TreeMap,只不过在初始化时给的value值都是一个固定值。

实现的接口

  • TreeSet也是可以排序的,实现了sortedSet,带Tree的set和map其实可以排序的,
  • 实现了Collection,
  • 也实现了Iterable接口,所以可以使用迭代器遍历,如果要使用迭代器遍历TreeMap,必须先调用entrySet方法得到Set才行。

常用方法

方法解释
boolean add(E e)添加元素,但重复元素不会被添加成功
void clear()清空集合
boolean contains(Object o)判断 o 是否在集合中
Iterator iterator()返回迭代器
boolean remove(Object o)删除集合中的 o
int size()返回set中元素的个数
boolean isEmpty()检测set是否为空,空返回true,否则返回false
Object[] toArray()将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)集合c中的元素是否在set中全部存在,是返回true,否则返回
false
boolean addAll(Collection<? extends E> c)将集合c中的元素添加到set中,可以达到去重的效果

注意事项:

  • Set中只存储了key,并且要求key一定要唯一;
  • TreeSet的底层是使用Map来实现的,其使用key与Object的一个默认对象作为键值对插入到Map中的;
  • Set最大的功能就是对集合中的元素进行去重;
  • 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序;
  • Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入;
  • TreeSet中不能插入null的key。

标签:Map,Set,key,TreeMap,value,Key,数据结构,TreeSet
From: https://blog.csdn.net/yj20040627/article/details/140986620

相关文章

  • 知识改变命运 数据结构【顺序表】
    1.线性表线性表(linearlist)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列…线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组......
  • 高阶数据结构(Java):AVL树插入机制的探索
    目录1、概念1.1什么是AVL树2.1平衡因子3、AVL树节点的定义4、AVL树的插入机制4.1初步插入节点4.2更新平衡因子4.3 提升右树高度4.3.1右单旋4.3.2左右双旋4.4 提升左树高度4.4.1左单旋 4.4.2右左双旋5、AVL树的验证6、AVL树的删除1、概念1.1什......
  • 【数据结构】详细介绍线性表中的顺序表,带你复盘实现细节,附上顺序表编程练习题
    目录一.线性表二.顺序表 1.静态顺序表与动态顺序表2.动态顺序表的接口实现 2.1顺序表初始化 2.2判断是否需要扩容  2.3 顺序表指定位置插入2.4 顺序表头插2.5 顺序表尾插2.6 顺序表指定位置删除2.7 顺序表头删2.8 顺序表尾删2.9 顺序表查找2.1......
  • TreeMapTest1
    packagecom.shujia.day15;importjava.util.Map;importjava.util.Set;importjava.util.TreeMap;/*"aababcabcdabcde",获取字符串中每一个字母出现的次数要求结果:a(5)b(4)c(3)d(2)e(1)*/publicclassTreeMapTest1{publicstaticvoidmain(String[]args)......
  • 数据结构之链表超详解(1)
     一人我饮酒醉醉把佳人成双对两眼是独相随只求他日能双归娇女我轻扶琴燕嬉我紫竹林痴情红颜心甘情愿千里把你寻说红颜我痴情笑曲动我琴声妙轻狂高傲懵懂无知只怪太年少弃江山我忘天下斩断情丝无牵挂千古留名传佳话我两年征战已白发一生征战何人陪谁是谁非谁相随戎马一......
  • 一次函数最优化数据结构
    哎呀没写完,明天再补吧李超线段树一个节点维护递归到这个点,包含整个区间,并且在mid处取值最大的线段。若有两条线段,其中x比y在mid处值更大,如果x在l和r处值都比y大,显然y没有用。否则y只可能在左区间或右区间比x优。李超线段树利用单侧递归保证时间复杂度。但是李超线段树不便于......
  • 嵌入式软件--数据结构与算法 DAY 12
    数据结构和算法是程序的核心,虽然在嵌入式应用中很少会用到,但了解认知这种思维过程是非常有必要的。一个好的程序员应该把数据结构和算法看的比代码更重要。1.数据结构是什么?定义1(宏观):数据结构是为了高效访问数据而设计出的一种数据的组织和存储方式。定义2(微观):数据结构......
  • 嵌入式软件--数据结构与算法 DAY 13
    在嵌入式中,对算法的要求不高,但顺序查找和冒泡排序是经典算法,必须掌握。1.算法定义算法是一个用于解决特定问题的有限指令序列(计算机可以执行的操作)。通俗的理解就是可以解决特定问题的方法。2.时间复杂度时间复杂度不是执行完一段程序的总时间,而是描述为一个算法中基本操作......
  • [OI] 可持久化数据结构
    学了一年OI才看懂这句话:\(\logn\)是以什么为底的?其实没什么区别因为我们自动忽略常数,因此\(\log_{a}n=\frac{\log_{x}n}{\log_{x}a}=\log_{x}n\)可持久化数组可持久化数组是基于可持久化线段树的一种数据结构.它可以支持如下操作:单点修改查询历史版本在历史版......
  • 25版王道数据结构课后习题详细分析 第五章 树与二叉树 5.1 树的基本概念
     一、单项选择题————————————————————————————————————————解析:树是一种分层结构,它特别适合组织那些具有分支层次关系的数据。正确答案:D————————————————————————————————————————解......