范县网站建设价格,东莞市公共资源交易中心,网站的功能有哪些,旅游小程序页面设计模板目录1. 二叉排序树(二叉搜索树)1.1 二叉搜索树的查找1.2 二叉搜索树的插入1.3 二叉搜索树的删除#xff08;7种情况#xff09;1.4 二叉搜索树和TreeMap、TreeSet的关系2. Map和Set的区别与联系2.1 从接口框架的角度分析2.2 从存储的模型角度分析【2种模型】3. 关于Map3.1 Ma…
目录1. 二叉排序树(二叉搜索树)1.1 二叉搜索树的查找1.2 二叉搜索树的插入1.3 二叉搜索树的删除7种情况1.4 二叉搜索树和TreeMap、TreeSet的关系2. Map和Set的区别与联系2.1 从接口框架的角度分析2.2 从存储的模型角度分析【2种模型】3. 关于Map3.1 Map的注意事项3.2 TreeMap 和 HashMap的对比3.3 Map.Entryk,v的用法 遍历4. 关于Set4.1 Set的注意事项4.2 TreeSet 和 HashSet的对比4.3 迭代器遍历Set5. 哈希表5.1 哈希函数5.2 冲突5.3 冲突的解决开放地址法和链地址法5.4 哈希表与Java集合类的关系6. HashMap源码分析6.1 成员变量6.2 构造方法6.3 put方法源码1. 二叉排序树(二叉搜索树)
二叉搜索树又称二叉排序树
若左子树不为空则左子树上所有节点的值都小于根节点的值若右子树不为空则右子树上所有节点的值都大于根节点的值左右子树也分别是二叉搜索树 【左小右大】
1.1 二叉搜索树的查找
【二叉搜索树的查找一般情况下一次可以干掉很多数据】 为了保证每次可以干掉很多数据 思路取遍历节点为cur每次要查找的值val和cur的val进行比较如果要查找的值比cur的val小则去cur的左边继续查找如果大则去cur的右边继续查找。 public boolean search(int val) {TreeNode cur root;while (cur ! null) {if (cur.val val) {return true;}else if (cur.val val) {cur cur.left;}else {cur cur.right;}}return false;}1.2 二叉搜索树的插入
思路整体思路与查找的思路类似但是二叉搜索树的每次插入的节点一定是叶子节点因此需要记录待插入节点的双亲。 当cur为空时parent记录了待插入结点的父亲位置再用val和parent的val比较进行插入。 public void insert (int val) {Node node new Node(val);if (root null) {root node;return;}Node cur root;Node parent root;while (cur ! null) {if (cur.val val) {return;}else if (cur.val val) {parent cur;cur cur.left;}else {parent cur;cur cur.right;}}if (parent.val val) {parent.left node;}else {parent.right node;}}1.3 二叉搜索树的删除7种情况
设待删除结点为cur待删除结点的双亲结点为parent 整体看分以下3种大情况 ①cur的左为空 ②cur的右为空 ③cur的左和右都不为空 继续细分cur是不是rootcur不是root的话是parent的左还是parent的右 故有3 3 1 7种情况。
cur.left null ①cur是root 则 root cur.right; ②cur不是rootcur是parent.left 则 parent.left cur.right; ③cur不是rootcur是parent.right 则 parent.right cur.right;cur.right null ①cur是root 则 root cur.left; ②cur不是rootcur是parent.left 则 parent.left cur.left; ③cur不是rootcur是parent.right 则 parent.right cur.left;cur.left ! null cur.right ! null 此时需要使用替换法进行删除即在它的右子树种寻找中序下的第一个结点关键码最小用它的值填补到被删除节点中再来处理该结点的删除问题。1.4 二叉搜索树和TreeMap、TreeSet的关系 TreeMap和TreeSet是Java种利用搜索树实现的Map和Set实际上用的是红黑树红黑树是一颗近似平衡的二叉搜索树即在二叉搜索树的基础之上颜色以及红黑树性质。
2. Map和Set的区别与联系
2.1 从接口框架的角度分析 Map是一个独立的接口而Set继承自Collection接口。 TreeMap 和 TreeSet 都继承了一个Sorted接口说明 Tree某某 都是经过排序的即 Tree某某 都是关于key有序的。
2.2 从存储的模型角度分析【2种模型】
Map中存储的是键值对key-valueSet中只存储了key
3. 关于Map
Map是一个接口类该类没有继承collection该类中存储的是k,v结构的键值对并且k一定是唯一的不能重复。
3.1 Map的注意事项
Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMap。 MapInteger, Integer map1 new HashMap();MapInteger, Integer map2 new TreeMap();Map中存放键值对的键key是唯一的key不可以重复但是value可以重复。在TreeMap中插入键值队的时候key不能为空否则会抛出NPE空指针异常但是value可以为空因为TreeMap中的key是要进行比较的反而HashMap的key和value都可以为空因为HashMap不涉及比较。Map中的key可以全部分离出来存储到Set中进行访问因为key不能重复set是天然的去重Map中的value可以全部分离出来存储到Collection的任何一个子集合中value可能有重复
3.2 TreeMap 和 HashMap的对比
Map底层结构TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间复杂度O(log2N)O(1)是否有序关于key有序无序线程安全不安全不安全插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址比较与覆写key必须能够比较否则会抛出类型转换异常自定义类型需要覆写equals和hashcode方法应用场景需要key有序的场景下key是否有序不关心需要更高的时间性能
3.3 Map.Entryk,v的用法 遍历
SetMap.Entry k,v entrySet() 返回所有的key-value映射关系 MapInteger, Integer map new TreeMap();map.put(1,2);map.put(2,3);map.put(3,6);//key一定是可以进行比较的for(Map.EntryInteger,Integer entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}分析 打印所有的键值对 entrySet()将Map中的键值对放在Set中返回了。
4. 关于Set
Set与Map主要的不同有2点 ①Set是继承自Collection的接口类 ②Set中只存储了Key Map不能使用迭代器遍历但是Set可以因为Set实现了Iterable接口
4.1 Set的注意事项 Set是继承自Collection的一个接口类 Set中只存储了key并且要求key一定要唯一 Set的底层使用Map来实现的其使用key与Object的一个默认对象作为键值对插入到Map中 Set最大的功能就是对集合中的元素进行去重 TreeSet中不能插入null的key但是HashSet可以
4.2 TreeSet 和 HashSet的对比
Set底层结构TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间复杂度O(log2N)O(1)是否有序关于key有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性进行插入和删除通过哈希函数计算哈希地址比较与覆写key必须能够比较否则会抛出类型转换异常自定义类型需要覆写equals和hashcode方法应用场景需要key有序的场景下key是否有序不关心需要更高的时间性能
4.3 迭代器遍历Set
Iterator E iterator() 返回迭代器可以利用其进行遍历 SetInteger set new TreeSet();set.add(1);set.add(3);set.add(2);set.add(8);set.add(4);IteratorInteger iterator set.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() );}运行结果
5. 哈希表
5.1 哈希函数
哈希表的效率非常高查找、删除、插入的时间复杂度都是O(1)。理想的搜索方法不经过任何比较一次直接从表中得到想要搜索的元素即一一映射关系。哈希方法中使用的转换函数称为哈希函数构造出来的结构称为哈希表(Hash Table)。哈希函数计算出来的地址能均匀分布在整个空间中。
5.2 冲突
冲突 不同关键字通过相同哈希函数计算出相同的哈希地址冲突的发生是必然的冲突是不可避免的只能降低冲突率。避免冲突负载因子调节其值 填入表中的元素个数/哈希表的长度因此可以增加哈希表的长度避免冲突。Java的系统库限制了荷载因子为0.75。
5.3 冲突的解决开放地址法和链地址法
开放地址法闭散列 ①线性探测 ②二次探测 闭散列最大的缺陷空间利用率比较低链地址法开散列 数组链表红黑树 思路首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于桶一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 注意数组长度64链表长度8就会变成红黑树。
5.4 哈希表与Java集合类的关系
HashMap和HashSet是用哈希表实现的Map和Set。Java会在冲突链表长度大于一定阈值后将链表转变成红黑树搜索树。Java中计算哈希值实际上调用的是类的hashcode方法进行key的相等性比较是调用key的equals方法。所有自定义类的HashMap的key或者HashSet的值必须重写hashcode和euqals方法而且必须做到euqals相等的对象hashcode一定也是一样的。扩容之后要注意每个元素都要重新计算hashcode哈希值。 面试问题 问如果2个对象hashcode一样equals一定一样吗 答不一定hashcode一样只能证明我们要找的位置一样位置一样的下面有很多值无法确定2个对象的euqals。问如果2个对象equals一样hashcode一定一样吗 答一定equals一样则hashcode一定一样。 6. HashMap源码分析
6.1 成员变量
默认容量16最大容量2的30次方 默认的负载因子0.75 树化的条件数组链表变成红黑树 链表长度超过8数组的容量大于等于64 解树的条件红黑树退化为链表数组 链表的阈值为6的时候 table数组的每一个元素是node类型的结点地址
6.2 构造方法
不带参数的构造方法 负载因子等于默认的负载因子0.75没有给table数组进行初始化意味着table数组没有分配内存数组的大小是0。 所以为什么等会put元素可以put进去---- 说明在第一次put的时候会把数组进行初始化为默认容量16 带2个参数的构造方法 一个是给定的容量参数一个是给定的负载因子参数 如果给定的参数容量大于2的30次方则容量为2的30次方 如果给定的参数容量小于0或者给定的负载因子小于0那么就抛异常。 最后负载因子满足条件直接赋值但是容量还需要经过tableSizeFor进一步筛选。 tableSizeFor里面返回最接近目标的一个二次幂整数。 例如 传入102的3次方82的4次方16因此返回16。 面试题调用构造方法给了1000请问最后哈希数组的长度是多少 答1024 HashMap的最大容量保证是2的n次方但是如果没有传入一个2的次方怎么办 答HashMap会将传入的参数做校验返回距离传参最近的一个2的n次方的值例如传入15会初始化为16。 那么为什么返回二次幂呢 分析put源码。
6.3 put方法源码 ①先把key给到hash函数中hash(key)调用hash方法将引用类型key转换成整数类型 ②hash这个方法中调用了hashcode方法如果key重写了hashcode方法则会调用自己的hashcode方法如果没有重写则会调用Object类的hashcode方法。 h是通过hashcode方法得到的32位的整数h 异或上 h右移16位 为什么要右移16位 答为了更好的均匀分布低16位和高16位异或可以让结果更均匀。 ③i (n - 1) hash 等价于 n % len位运算一定是最快的一定要保证n是2的次幂这样2个公式才等价。【所以初始化的长度为2的整数次幂】 文章转载自： http://www.morning.tsdjj.cn.gov.cn.tsdjj.cn http://www.morning.npmpn.cn.gov.cn.npmpn.cn http://www.morning.pflry.cn.gov.cn.pflry.cn http://www.morning.nwwzc.cn.gov.cn.nwwzc.cn http://www.morning.wypyl.cn.gov.cn.wypyl.cn http://www.morning.jbkcs.cn.gov.cn.jbkcs.cn http://www.morning.zqcdl.cn.gov.cn.zqcdl.cn http://www.morning.jspnx.cn.gov.cn.jspnx.cn http://www.morning.gmgnp.cn.gov.cn.gmgnp.cn http://www.morning.datadragon-auh.cn.gov.cn.datadragon-auh.cn http://www.morning.znmwb.cn.gov.cn.znmwb.cn http://www.morning.tcylt.cn.gov.cn.tcylt.cn http://www.morning.lnrhk.cn.gov.cn.lnrhk.cn http://www.morning.mcjyair.com.gov.cn.mcjyair.com http://www.morning.rjnky.cn.gov.cn.rjnky.cn http://www.morning.xqnzn.cn.gov.cn.xqnzn.cn http://www.morning.nxfwf.cn.gov.cn.nxfwf.cn http://www.morning.bfsqz.cn.gov.cn.bfsqz.cn http://www.morning.etsaf.com.gov.cn.etsaf.com http://www.morning.fksrg.cn.gov.cn.fksrg.cn http://www.morning.ttdxn.cn.gov.cn.ttdxn.cn http://www.morning.rlzxr.cn.gov.cn.rlzxr.cn http://www.morning.lhgqc.cn.gov.cn.lhgqc.cn http://www.morning.mmzfl.cn.gov.cn.mmzfl.cn http://www.morning.ngznq.cn.gov.cn.ngznq.cn http://www.morning.xfdkh.cn.gov.cn.xfdkh.cn http://www.morning.qqhersx.com.gov.cn.qqhersx.com http://www.morning.rjfr.cn.gov.cn.rjfr.cn http://www.morning.gbkkt.cn.gov.cn.gbkkt.cn http://www.morning.rxhsm.cn.gov.cn.rxhsm.cn http://www.morning.tzzkm.cn.gov.cn.tzzkm.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.nsppc.cn.gov.cn.nsppc.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.mrfgy.cn.gov.cn.mrfgy.cn http://www.morning.dyhlm.cn.gov.cn.dyhlm.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.rkdw.cn.gov.cn.rkdw.cn http://www.morning.clpkp.cn.gov.cn.clpkp.cn http://www.morning.ssxlt.cn.gov.cn.ssxlt.cn http://www.morning.nypgb.cn.gov.cn.nypgb.cn http://www.morning.xlwpz.cn.gov.cn.xlwpz.cn http://www.morning.ggmls.cn.gov.cn.ggmls.cn http://www.morning.jwpcj.cn.gov.cn.jwpcj.cn http://www.morning.ntffl.cn.gov.cn.ntffl.cn http://www.morning.lrzst.cn.gov.cn.lrzst.cn http://www.morning.mdwb.cn.gov.cn.mdwb.cn http://www.morning.ns3nt8.cn.gov.cn.ns3nt8.cn http://www.morning.dtcsp.cn.gov.cn.dtcsp.cn http://www.morning.rhfbl.cn.gov.cn.rhfbl.cn http://www.morning.hjlsll.com.gov.cn.hjlsll.com http://www.morning.jpnw.cn.gov.cn.jpnw.cn http://www.morning.ljbm.cn.gov.cn.ljbm.cn http://www.morning.bccls.cn.gov.cn.bccls.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.cnhgc.cn.gov.cn.cnhgc.cn http://www.morning.ckhpg.cn.gov.cn.ckhpg.cn http://www.morning.ampingdu.com.gov.cn.ampingdu.com http://www.morning.shxmr.cn.gov.cn.shxmr.cn http://www.morning.ckzjl.cn.gov.cn.ckzjl.cn http://www.morning.mhnd.cn.gov.cn.mhnd.cn http://www.morning.ymwcs.cn.gov.cn.ymwcs.cn http://www.morning.grxbw.cn.gov.cn.grxbw.cn http://www.morning.rnnq.cn.gov.cn.rnnq.cn http://www.morning.cyysq.cn.gov.cn.cyysq.cn http://www.morning.gppqf.cn.gov.cn.gppqf.cn http://www.morning.qcmhs.cn.gov.cn.qcmhs.cn http://www.morning.fydsr.cn.gov.cn.fydsr.cn http://www.morning.fmkbk.cn.gov.cn.fmkbk.cn http://www.morning.bmsqq.cn.gov.cn.bmsqq.cn http://www.morning.xgcwm.cn.gov.cn.xgcwm.cn http://www.morning.gppqf.cn.gov.cn.gppqf.cn http://www.morning.mwqbp.cn.gov.cn.mwqbp.cn http://www.morning.fcpjq.cn.gov.cn.fcpjq.cn http://www.morning.kmqjx.cn.gov.cn.kmqjx.cn http://www.morning.mfmbn.cn.gov.cn.mfmbn.cn http://www.morning.sgcdr.com.gov.cn.sgcdr.com http://www.morning.mhnrx.cn.gov.cn.mhnrx.cn http://www.morning.brld.cn.gov.cn.brld.cn http://www.morning.qnklx.cn.gov.cn.qnklx.cn
