网站建设基础教程视频,个人网站设计及实现论文,西安广告公司前十名,网站开发项目经验和教训在开始详解之前#xff0c;先来看看集合的框架#xff1a; 可以看到Set实现了Collection接口#xff0c;而Map又是一个单独存在的接口。
而最下面又分别各有两个类#xff0c;分别是TreeSet#xff08;Map#xff09;和 HashSet#xff08;Map#xff09;。
TreeSet先来看看集合的框架 可以看到Set实现了Collection接口而Map又是一个单独存在的接口。
而最下面又分别各有两个类分别是TreeSetMap和 HashSetMap。
TreeSetMap的底层是一颗搜索树红黑树我们在以后数据结构的进阶中会讲到HashSetMap的底层是一个哈希表这个我们等会就会说到。
那我们的Map和Set是用来干什么的呢其实就是用来查找和搜索的以后涉及到查找和搜索的可以选择使用这两个接口下面具体的类。
那么就正式进入本章节的正题(Tree)和(Hash)。
1.搜索树(Tree)
1.1 概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树1. 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 2. 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 3. 它的左右子树也分别为二叉搜索树 一颗简单的二叉搜索树 1.2 操作
1.2.1 查找
具体思路如下图
直到找到该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 插入 插入思路如下 这里也就解释了为什么一般情况下TreeSet 和 TreeMap 不可以插入相同的元素。 代码 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 待删除的右边为空 cur.left null
待删除的右边和右边均不为空 如果我们要删的是100那么放谁呢这个时候就需要使用替换法进行删除所谓的替换法删除即在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题。
cur的左树全部小于curcur的右树全部大于cur那么就找右树中的最小值。
那么问题就改为如何删除107这个树了。
大概思路 代码 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。 我们再次回到这个图TreeSetMap都是实现了SortedMapSet这个接口而Hash只实现了Map这个接口。
那么我们可以这么来写代码
MapObject,Object map1 new HashMap();
MapObject,Object map2 new TreeMap();
2.3 关于Map的说明
Map是一个接口类该类没有继承自Collection该类中存储的是K,V结构的键值对并且K一定是唯一的不能重复。
我们也可以来查看源码拿Map举例 我把常用的Map方法都放在下面
方法解释V get(Object key)返回 key 对应的 valueV getOrDefault(Object key, V defaultValue)返回 key 对应的 valuekey 不存在返回默认值V put(K key, V value)设置 key 对应的 valueV remove(Object key)删除 key 对应的映射关系SetK keySet()返回所有 key 的不重复集合CollectionV values()返回所有 value 的可重复集合SetMap.EntryK, V entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value
我们知道key - value 是一个键值对一 一对应那么我们如何去拿到这个对应关系呢
jdk提供了一个内部类Map.EntryK, V
说明
Map.EntryK, V 是Map内部实现的用来存放key, value键值对映射关系的内部类该内部类中主要提供了key, value的获取value的设置以及Key的比较方式
其内部类方法如下
方法解释K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV 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底层结构TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间 复杂度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 是否在集合中IteratorE iterator()返回迭代器boolean remove(Object o)删除集合中的 oint size()返回set中元素的个数boolean isEmpty()检测set是否为空空返回true否则返回falseObject[] toArray()将set中的元素转换为数组返回boolean containsAll(Collection? c)集合c中的元素是否在set中全部存在是返回true否则返回 falseboolean 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还有一个LinkedHashSetLinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。 6. Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入 7. TreeSet中不能插入null的keyHashSet可以。 8. TreeSet和HashSet的区别 Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。
Set底层结构TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间 复杂度O(1)是否有序关于Key有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行 插入和删除比较与覆写key必须能够比较否则会抛出 ClassCastException异常自定义类型需要覆写equals和 hashCode方法应用场景需要Key有序场景下Key是否有序不关心需要更高的 时间性能
当然我们说到这里还是没有讲到Hash因为篇幅有限只能留着下一章再继续。
