Map和Set(Java详解)

简介: Map和Set(Java详解)

在开始详解之前,先来看看集合的框架:


e31f40d247b049259ccad2e3f523c696.png


可以看到Set实现了Collection接口,而Map又是一个单独存在的接口。


而最下面又分别各有两个类,分别是TreeSet(Map)和 HashSet(Map)。


TreeSet(Map)的底层是一颗搜索树(红黑树),我们在以后数据结构的进阶中会讲到;HashSet(Map)的底层是一个哈希表,这个我们等会就会说到。

那我们的Map和Set是用来干什么的呢,其实就是用来查找和搜索的;以后涉及到查找和搜索的可以选择使用这两个接口下面具体的类。


那么就正式进入本章节的正题(Tree)和(Hash)。

1.搜索树("Tree")

1.1 概念:

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

1. 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树


一颗简单的二叉搜索树:




0fabbef94d93496b9c97197ab7912942.png




1.2 操作

1.2.1 查找

具体思路如下图:


4081385d1f434cf4b19433a114dfc39c.png


直到找到该key或者找到null就结束。

代码如下:

public TreeNode find(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            }
            if (cur.val == val) {
                return cur;
            }
        }


1.2.2 插入

插入思路如下:


96b582cd5ac44214bca31aef97f296e1.png




这里也就解释了为什么一般情况下TreeSet 和 TreeMap 不可以插入相同的元素。


6335c1dbe6804f96821f9d57ecf67d04.png



代码:

 public void insert(int val) {
        if (root == null) {
            new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(val > root.val) {
                parent = cur;
                cur = cur.right;
            } else if (val < root.val) {
                parent = cur;
                cur = cur .left;
            } else {
                return;
            }
        }
        if (val > parent.val) {
            parent.right = new TreeNode(val);
        } else if (val < parent.val) {
            parent.left = new TreeNode(val);
        }
    }


1.2.3 删除


删除是个重难点,删除有很多种情况,我们一个个来分析。

1. 如果我们待删除的左边为空 cur.left == null

2. 如果我们待删除的右边为空 cur.left == null

3. 如果我们待删除的右边和右边均不为空

每种情况下都还有情况需要考虑

画图说明:

待删除的左边为空 cur.left == null :


ecbdc0bebb0d4080a1b1d3a086d00b85.png



待删除的右边为空 cur.left == null :


e3b0db30a19d40b5827b226a751cbfcc.png

待删除的右边和右边均不为空:


e1f0b15278df4217af463c8e273321aa.png


如果我们要删的是100,那么放谁呢?

这个时候就需要使用替换法进行删除,所谓的替换法删除即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题。


cur的左树全部小于cur,cur的右树全部大于cur,那么就找右树中的最小值。


那么问题就改为如何删除107这个树了。


大概思路:


69ed3bace9634a96b956af00d0bdc695.png


12c8aa1e38b84b408412625e57e2285f.png



代码:

 public void remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.val == val) {
                removeNode(parent,cur);
                return;
            }else if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }
private void removeNode(TreeNode parent, TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }


二叉搜索树与Set和Map的关系:


TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set;实际上用的是红黑树,而红黑树是一棵近似平衡的二叉搜索树,即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证,关于红黑树的内容后序再进行讲解。


2. 搜索("Hash")


2.1 概念


Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关。之前学的ArrayList也可以用来搜索,为什么还需学习Set和Map呢?这里就涉及到效率的问题,不同的情况下,使用的效率会不同。


以前常见的搜索方式有:

1. 直接遍历,时间复杂度为O(N),元素如果比较多效率会非常慢

2. 二分查找,时间复杂度为 ,但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找,即一般不会对区间进行插入和删除操作了,而现实中的查找比如:

1. 根据姓名查询考试成绩

2. 通讯录,即根据姓名查询联系方式


2.2 模型


一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称之为Key-value的键值对,所以模型会有两种:

1. 纯 key 模型,比如:

有一个英文词典,快速查找一个单词是否在词典中快速查找某个名字在不在通讯录中

2. Key-Value 模型,比如:

统计文件中每个单词出现的次数,统计结果是每个单词都有与其对应的次数:<单词,单词出现的次数>

梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号

而Map中存储的就是key-value的键值对,Set中只存储了Key



91d62998d63b4e95b0ab53108c97a1c4.png


我们再次回到这个图,TreeSet(Map)都是实现了SortedMap(Set)这个接口,而Hash只实现了Map这个接口。

那么我们可以这么来写代码:

Map<Object,Object> map1 = new HashMap<>();
Map<Object,Object> map2 = new TreeMap<>();



2.3 关于Map的说明


Map是一个接口类,该类没有继承自Collection,该类中存储的是<K,V>结构的键值对,并且K一定是唯一的,不能重复。

我们也可以来查看源码:拿Map举例:



d1d8d15480b4410599b890fb222fb7d6.png

我把常用的Map方法都放在下面:


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



我们知道key - value 是一个键值对,一 一对应,那么我们如何去拿到这个对应关系呢?


jdk提供了一个内部类:Map.Entry<K, V>;


说明:

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类,该内部类中主要提供了<key, value>的获取,value的设置以及Key的比较方式

其内部类方法如下:


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


注意:

1. Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap

2. Map中存放键值对的Key是唯一的,value是可以重复的

3. 在TreeMap中插入键值对时,key不能为空,否则就会抛NullPointerException异常,value可以为空。但是HashMap的key和value都可以为空。

4. Map中的Key可以全部分离出来,存储到Set中来进行访问(因为Key不能重复)。

5. Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复)。

6. Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行重新插入。


7. TreeMap和HashMap的区别


Map底层结构 TreeMap HashMap
底层结构 红黑树 哈希桶
插入/删除/查找时间
复杂度
O(1)
是否有序 关于Key有序 无序
线程安全 不安全 不安全
插入/删除/查找区别 需要进行元素比较 通过哈希函数计算哈希地址
比较与覆写 key必须能够比较,否则会抛出
ClassCastException异常
自定义类型需要覆写equals和
hashCode方法
应用场景 需要Key有序场景下 Key是否有序不关心,需要更高的
时间性能



2.4 Set 的说明


Set 的官方文档:https://docs.oracle.com/javase/8/docs/api/java/util/Set.html

常见方法说明:


方法 解释
boolean add(E e) 添加元素,但重复元素不会被添加成功
void clear() 清空集合
boolean contains(Object o) 判断 o 是否在集合中
Iterator<E> 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中,可以达到去重的效果


注意:

1. Set是继承自Collection的一个接口类

2. Set中只存储了key,并且要求key一定要唯一

3. TreeSet的底层是使用Map来实现的,其使用key与Object的一个默认对象作为键值对插入到Map中的

4. Set最大的功能就是对集合中的元素进行去重

5. 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础

上维护了一个双向链表来记录元素的插入次序。

6. Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入

7. TreeSet中不能插入null的key,HashSet可以。

8. TreeSet和HashSet的区别


Set与Map主要的不同有两点:Set是继承自Collection的接口类,Set中只存储了Key。

Set底层结构 TreeSet HashSet
底层结构 红黑树 哈希桶
插入/删除/查找时间
复杂度
O(1)
是否有序 关于Key有序 不一定有序
线程安全 不安全 不安全
插入/删除/查找区别 按照红黑树的特性来进行插入和删除 1. 先计算key哈希地址 2. 然后进行
插入和删除
比较与覆写 key必须能够比较,否则会抛出
ClassCastException异常
自定义类型需要覆写equals和
hashCode方法
应用场景 需要Key有序场景下 Key是否有序不关心,需要更高的
时间性能

当然我们说到这里还是没有讲到Hash,因为篇幅有限,只能留着下一章再继续。

相关文章
|
21天前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
55 18
你对Collection中Set、List、Map理解?
|
14天前
|
存储 缓存 安全
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
51 20
|
1月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对,每个键唯一;而`set`存储唯一元素,不包含值。两者均基于红黑树实现,支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口,并简要对比了`map`与`set`的主要差异。此外,还介绍了允许重复元素的`multiset`和`multimap`。
30 3
【C++】map、set基本用法
|
1月前
|
JSON Java 关系型数据库
Java更新数据库报错:Data truncation: Cannot create a JSON value from a string with CHARACTER SET 'binary'.
在Java中,使用mybatis-plus更新实体类对象到mysql,其中一个字段对应数据库中json数据类型,更新时报错:Data truncation: Cannot create a JSON value from a string with CHARACTER SET 'binary'.
70 4
Java更新数据库报错:Data truncation: Cannot create a JSON value from a string with CHARACTER SET 'binary'.
|
1月前
|
存储 算法 C++
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
22 5
|
1月前
|
存储 算法 Java
Java Set深度解析:为何它能成为“无重复”的代名词?
Java的集合框架中,Set接口以其“无重复”特性著称。本文解析了Set的实现原理,包括HashSet和TreeSet的不同数据结构和算法,以及如何通过示例代码实现最佳实践。选择合适的Set实现类和正确实现自定义对象的hashCode()和equals()方法是关键。
33 4
|
1月前
|
Java
那些与Java Set擦肩而过的重复元素,都经历了什么?
在Java的世界里,Set如同一位浪漫而坚定的恋人,只对独一无二的元素情有独钟。重复元素虽屡遭拒绝,但通过反思和成长,最终变得独特,赢得了Set的认可。示例代码展示了这一过程,揭示了成长与独特性的浪漫故事。
21 4
|
1月前
|
Java 开发者
Java Set:当“重复”遇见它,秒变“独宠”!
在Java编程中,Set接口确保集合中的元素不重复,每个元素都是独一无二的“独宠”。本文介绍了Set的两种常见实现:HashSet和TreeSet。HashSet基于哈希表实现,提供高效的添加、删除和查找操作;TreeSet基于红黑树实现,不仅去重还能对元素进行排序。通过示例代码,展示了这两种集合的具体应用,帮助开发者更好地理解和使用Set。
27 4
|
1月前
|
存储 Java
判断一个元素是否在 Java 中的 Set 集合中
【10月更文挑战第30天】使用`contains()`方法可以方便快捷地判断一个元素是否在Java中的`Set`集合中,但对于自定义对象,需要注意重写`equals()`方法以确保正确的判断结果,同时根据具体的性能需求选择合适的`Set`实现类。
|
1月前
|
存储 Java 开发者
Java 中 Set 类型的使用方法
【10月更文挑战第30天】Java中的`Set`类型提供了丰富的操作方法来处理不重复的元素集合,开发者可以根据具体的需求选择合适的`Set`实现类,并灵活运用各种方法来实现对集合的操作和处理。