wordpress 替换,百度seo是什么,网站后台编辑内容不显示,WordPress和phpwind怎么选1. 二叉树
1.1 二叉树概述
二叉树#xff0c;顾名思义#xff0c;每个节点最多有两个“叉”#xff0c;也就是两个子节点#xff0c;分别是左子节点和右子节点。不过#xff0c;二叉树并不要求每个节点都有两个子节点#xff0c;有的节点只有左子节点#xff0c;有的节…
1. 二叉树
1.1 二叉树概述
二叉树顾名思义每个节点最多有两个“叉”也就是两个子节点分别是左子节点和右子节点。不过二叉树并不要求每个节点都有两个子节点有的节点只有左子节点有的节点只有右子节点。
二叉树每个节点的左子树和右子树也分别满足二叉树的定义。 Java中有两个方式实现二叉树数组存储链式存储。
基于链式存储的树的节点可定义如下 1.2 二叉搜索树
在二叉树中比较常见的二叉树有 满二叉树 完全二叉树 二叉搜索树 红黑树
我们重点讲解二叉搜索树和红黑树。
1二叉搜索树概述
二叉搜索树Binary Search Tree,BST又名二叉查找树有序二叉树或者排序二叉树是二叉树中比较常用的一种类型。
二叉查找树要求在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值。 2二叉搜索树-时间复杂度分析
实际上由于二叉查找树的形态各异时间复杂度也不尽相同我画了几棵树我们来看一下插入查找删除的时间复杂度。 插入查找删除的时间复杂度**O(logn)**。
极端情况下二叉搜索的时间复杂度。 对于图中这种情况属于最坏的情况二叉查找树已经退化成了链表左右子树极度不平衡此时查找的时间复杂度肯定是O(n)。
1.3 红黑树
1概述
红黑树Red Black Tree也是一种自平衡的二叉搜索树BST之前叫做平衡二叉B树Symmetric Binary B-Tree。 2红黑树的特质
性质1节点要么是红色要么是黑色。
性质2根节点是黑色。
性质3叶子节点都是黑色的空节点。
性质4红黑树中红色节点的子节点都是黑色。
性质5从任一节点到叶子节点的所有路径都包含相同数目的黑色节点。
在添加或删除节点的时候如果不符合这些性质会发生旋转以达到所有的性质保证红黑树的平衡。
3红黑树的复杂度 查找 红黑树也是一棵BST二叉搜索树树查找操作的时间复杂度为O(log n)。 添加 添加先要从根节点开始找到元素添加的位置时间复杂度O(log n)。添加完成后涉及到复杂度为O(1)的旋转调整操作。故整体复杂度为O(log n)。 删除 首先从根节点开始找到被删除元素的位置时间复杂度O(log n)。删除完成后涉及到复杂度为O(1)的旋转调整操作。故整体复杂度为O(log n)。
2. 散列表
在HashMap中的最重要的一个数据结构就是散列表在散列表中又使用到了红黑树和链表。
2.1 散列表Hash Table概述
散列表Hash Table又名哈希表/Hash表是根据键Key直接访问在内存存储位置值Value的数据结构它是由数组演化而来的利用了数组支持按照下标进行随机访问数据的特性。
举个例子 假设有100个人参加马拉松编号是1-100如果要编程实现根据选手的编号迅速找到选手信息
可以把选手信息存入数组中选手编号就是数组的下标数组的元素就是选手的信息。
当我们查询选手信息的时候只需要根据选手的编号到数组中查询对应的元素就可以快速找到选手的信息如下图 现在需求升级了
假设有100个人参加马拉松不采用1-100的自然数对选手进行编号编号有一定的规则比如2023ZHBJ001其中2023代表年份ZH代表中国BJ代表北京001代表原来的编号那此时的编号2023ZHBJ001不能直接作为数组的下标此时应该如何实现呢 我们目前是把选手的信息存入到数组中不过选手的编号不能直接作为数组的下标不过可以把选手的选号进行转换转换为数值就可以继续作为数组的下标了
转换可以使用散列函数进行转换。
2.2 散列函数和散列冲突
将键key映射为数组下标的函数叫做散列函数。可以表示为hashValue hash(key)。
散列函数的基本要求 散列函数计算得到的散列值必须是大于等于0的正整数因为hashValue需要作为数组的下标。 如果key1key2那么经过hash后得到的哈希值也必相同即hash(key1) hash(key2。 如果key1 ! key2那么经过hash后得到的哈希值也必不相同即hash(key1) ! hash(key2)。
实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的即便像著名的MD5、SHA等哈希算法也无法避免这一情况这就是散列冲突或者哈希冲突哈希碰撞就是指多个key映射到同一个数组下标位置。 2.3 散列冲突-链表法拉链
在散列表中数组的每个下标位置我们可以称之为桶bucket或者槽slot每个桶槽会对应一条链表所有散列值相同的元素我们都放到相同槽位对应的链表中。 简单就是如果有多个key最终的hash值是一样的就会存入数组的同一个下标中下标中挂一个链表存入多个数据。
2.4 时间复杂度-散列表
1插入操作通过散列函数计算出对应的散列槽位将其插入到对应链表中即可插入的时间复杂度是O(1)。 通过计算就可以找到元素。 2当查找、删除一个元素时我们同样通过散列函数计算出对应的槽然后遍历链表查找或者删除。 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)。 散列表可能会退化为链表查询的时间复杂度就从O(1)退化为O(n)。 将链表法中的链表改造为其他高效的动态数据结构比如红黑树查询的时间复杂度是O(logn)。 将链表法中的链表改造红黑树还有一个非常重要的原因可以防止DDos攻击。 DDos攻击 分布式拒绝服务攻击英文意思是Distributed Denial of Service简称DDoS。 指处于不同位置的多个攻击者同时向一个或数个目标发动攻击或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的这类攻击称为分布式拒绝服务攻击其中的攻击者可以有多个。 3. HashMap的实现原理
HashMap的数据结构 底层使用hash表数据结构即数组和链表或红黑树。 当我们往HashMap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中的下标。 存储时如果出现hash值相同的key此时有两种情况。 如果key相同则覆盖原始值 如果key不同出现冲突则将当前的key-value放入链表或红黑树中 。 获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。 面试官追问HashMap的jdk1.7和jdk1.8有什么区别 JDK1.8之前采用的是拉链法。拉链法将链表和数组相结合。也就是说创建一个链表数组数组中每一格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。 jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8 时并且数组长度达到64时将链表转化为红黑树以减少搜索时间。扩容resize( )时红黑树拆分成的树的结点数小于等于临界值6个则退化成链表。
4. HashMap的put方法的具体流程
4.1 hashMap常见属性 4.2 源码分析 HashMap是懒惰加载在创建对象时并没有初始化数组。 在无参的构造函数中设置了默认的加载因子是0.75。
添加数据流程图 具体的源码
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//判断数组是否未初始化if ((tab table) null || (n tab.length) 0)//如果未初始化调用resize方法 进行初始化n (tab resize()).length;//通过 运算求出该数据key的数组下标并判断该下标位置是否有数据if ((p tab[i (n - 1) hash]) null)//如果没有直接将数据放在该下标位置tab[i] newNode(hash, key, value, null);//该数组下标有数据的情况else {NodeK,V e; K k;//判断该位置数据的key和新来的数据是否一样if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//如果一样证明为修改操作该节点的数据赋值给e,后边会用到e p;//判断是不是红黑树else if (p instanceof TreeNode)//如果是红黑树的话进行红黑树的操作e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);//新数据和当前数组既不相同也不是红黑树节点证明是链表else {//遍历链表for (int binCount 0; ; binCount) {//判断next节点如果为空的话证明遍历到链表尾部了if ((e p.next) null) {//把新值放入链表尾部p.next newNode(hash, key, value, null);//因为新插入了一条数据所以判断链表长度是不是大于等于8if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是进行转换红黑树操作treeifyBin(tab, hash);break;}//判断链表当中有数据相同的值如果一样证明为修改操作if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;//把下一个节点赋值为当前节点p e;}}//判断e是否为空e值为修改操作存放原数据的变量if (e ! null) { // existing mapping for key//不为空的话证明是修改操作取出老值V oldValue e.value;//一定会执行 onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue null)//将新值赋值当前节点e.value value;afterNodeAccess(e);//返回老值return oldValue;}}//计数器计算当前节点的修改次数modCount;//当前数组中的数据数量如果大于扩容阈值if (size threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值return null;
}判断键值对数组table是否为空或为null否则执行resize()进行扩容初始化。 根据键值key计算hash值得到数组索引。 判断table[i]null条件成立直接新建节点添加。 如果table[i]null 不成立。 4.1 判断table[i]的首个元素是否和key一样如果相同直接覆盖value。 4.2 判断table[i]是否为treeNode即table[i]是否是红黑树如果是红黑树则直接在树中插入键值对。 4.3 遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作遍历过程中若发现key已经存在直接覆盖value。 插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold数组长度*0.75如果超过进行扩容。
5. HashMap的扩容机制 扩容的流程 源码
//扩容、初始化数组
final NodeK,V[] resize() {NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap老数组容量设置为0int oldCap (oldTab null) ? 0 : oldTab.length;//老的扩容阈值int oldThr threshold;int newCap, newThr 0;//判断数组容量是否大于0大于0说明数组已经初始化if (oldCap 0) {//判断当前数组长度是否大于最大数组长度if (oldCap MAXIMUM_CAPACITY) {//如果是将扩容阈值直接设置为int类型的最大数值并直接返回threshold Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap*2//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold 等价于oldThr*2}//如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;//数组未初始化的情况将阈值和扩容因子都设置为默认值else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候扩容阈值是没有赋值的if (newThr 0) {//创建阈值float ft (float)newCap * loadFactor;//判断新容量和新阈值是否大于最大容量newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//计算出来的阈值赋值threshold newThr;SuppressWarnings({rawtypes,unchecked})//根据上边计算得出的容量 创建新的数组 NodeK,V[] newTab (NodeK,V[])new Node[newCap];//赋值table newTab;//扩容操作判断不为空证明不是初始化数组if (oldTab ! null) {//遍历数组for (int j 0; j oldCap; j) {NodeK,V e;//判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作if ((e oldTab[j]) ! null) {//将数组位置置空oldTab[j] null;//判断是否有下个节点if (e.next null)//如果没有就重新计算在新数组中的下标并放进去newTab[e.hash (newCap - 1)] e;//有下个节点的情况并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且没有树化链表形式else {//比如老数组容量是16那下标就为0-15//扩容操作*2容量就变为32下标为0-31//低位0-15高位16-31//定义了四个变量// 低位头 低位尾NodeK,V loHead null, loTail null;// 高位头 高位尾NodeK,V hiHead null, hiTail null;//下个节点NodeK,V next;//循环遍历do {//取出next节点next e.next;//通过 与操作 计算得出结果为0if ((e.hash oldCap) 0) {//如果低位尾为null证明当前数组位置为空没有任何数据if (loTail null)//将e值放入低位头loHead e;//低位尾不为null证明已经有数据了else//将数据放入next节点loTail.next e;//记录低位尾数据loTail e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null证明当前数组位置为空没有任何数据if (hiTail null)//将e值放入高位头hiHead e;//高位尾不为null证明已经有数据了else//将数据放入next节点hiTail.next e;//记录高位尾数据hiTail e;}} //如果e不为空证明没有到链表尾部继续执行循环while ((e next) ! null);//低位尾如果记录的有数据是链表if (loTail ! null) {//将下一个元素置空loTail.next null;//将低位头放入新数组的原下标位置newTab[j] loHead;}//高位尾如果记录的有数据是链表if (hiTail ! null) {//将下一个元素置空hiTail.next null;//将高位头放入新数组的(原下标原数组容量)位置newTab[j oldCap] hiHead;}}}}}//返回新的数组对象return newTab;}在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值数组长度 * 0.75。 每次扩容的时候都是扩容之前容量的2倍。 扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中。 没有hash冲突的节点则直接使用e.hash (newCap - 1)计算新数组的索引位置。如果是红黑树走红黑树的添加。如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上。
6. hashMap的寻址算法 在putVal方法中有一个hash(key)方法这个方法就是来去计算key的hash值的看下面的代码 首先获取key的hashCode值然后右移16位 异或运算 原来的hashCode值主要作用就是使原来的hash值更加均匀减少hash冲突。
有了hash值之后就很方便的去计算当前key的在数组中存储的下标看下面的代码 (n-1)hash : 得到数组中的索引代替取模性能更好数组长度必须是2的n次幂。
关于hash值的其他面试题为何HashMap的数组长度一定是2的次幂 计算索引时效率更高如果是 2 的n次幂可以使用位与运算代替取模。 扩容时重新计算索引效率更高hash oldCap 0的元素留在原来位置 否则新位置 旧位置 oldCap。
7. hashmap在1.7情况下的多线程死循环问题
jdk7的的数据结构是数组链表。
在数组进行扩容的时候因为链表是头插法在进行数据迁移的过程中有可能导致死循环。 变量e指向的是需要迁移的对象。 变量next指向的是下一个需要迁移的对象。 Jdk1.7中的链表采用的头插法。 在数据迁移的过程中并没有新的对象产生只是改变了对象的引用。
产生死循环的过程
线程1和线程2的变量e和next都引用了这个两个节点。 线程2扩容后由于头插法链表顺序颠倒但是线程1的临时变量e和next还引用了这两个节点。 第一次循环
由于线程2迁移的时候已经把B的next执行了A。 第二次循环 第三次循环 参考回答
在jdk1.7的hashmap中在数组进行扩容的时候因为链表是头插法在进行数据迁移的过程中有可能导致死循环。
比如说现在有两个线程
线程一读取到当前的hashmap数据数据中一个链表在准备扩容时线程二介入。
线程二也读取hashmap直接进行扩容。因为是头插法链表的顺序会进行颠倒过来。比如原来的顺序是AB扩容后的顺序是BA线程二执行结束。
线程一继续执行的时候就会出现死循环的问题。
线程一先将A移入新的链表再将B插入到链头由于另外一个线程的原因B的next指向了A
所以B-A-B形成循环。
当然JDK 8将扩容算法做了调整不再将元素加入链表头而是保持与扩容前一样的顺序尾插法就避免了jdk7中死循环的问题。
8. HashSet与HashMap的区别
(1) HashSet实现了Set接口仅存储对象HashMap实现了Map接口存储的是键值对。
(2) HashSet底层其实是用HashMap实现存储的HashSet封装了一系列HashMap的方法。依靠HashMap来存储元素值利用hashMap的key键进行存储而value值默认为Object对象。所以HashSet也不允许出现重复值判断标准和HashMap判断标准相同两个元素的hashCode相等并且通过equals()方法返回true。 9. HashTable与HashMap的区别
主要区别
区别HashTableHashMap数据结构数组链表数组链表红黑树是否可以为nullKey和value都不能为null可以为nullhash算法key的hashCode()二次hash扩容方式当前容量翻倍 1当前容量翻倍线程安全同步(synchronized)的线程安全非线程安全
在实际开中不建议使用HashTable在多线程环境下可以使用ConcurrentHashMap类。
10. 面试现场
10.1 说一下HashMap的实现原理
嗯。它主要分为了一下几个部分
1底层使用hash表数据结构即数组链表 | 红黑树。
2添加数据时计算key的值确定元素在数组中的下标 key相同则替换 不同则存入链表或红黑树中
3获取数据通过key的hash计算数组下标获取元素。
10.2 HashMap的jdk1.7和jdk1.8有什么区别 JDK1.8之前采用的拉链法数组链表。 JDK1.8之后采用数组链表红黑树链表长度大于8且数组长度大于64则会从链表转化为红黑树。
10.3 你能说下HashMap的put方法的具体流程吗 判断键值对数组table是否为空或为null否则执行resize()进行扩容初始化。 根据键值key计算hash值得到数组索引。 判断table[i]null条件成立直接新建节点添加。 如果table[i]null不成立。 判断table[i]的首个元素是否和key一样如果相同直接覆盖value。 判断table[i]是否为treeNode即table[i]是否是红黑树如果是红黑树则直接在树中插入键值对。 遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作遍历过程中若发现key已经存在直接覆盖value。 插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold数组长度*0.75如果超过进行扩容。
10.4 刚才你多次介绍了hsahmap的扩容能讲一讲HashMap的扩容机制吗 在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值数组长度 * 0.75 每次扩容的时候都是扩容之前容量的2倍 扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中 没有hash冲突的节点则直接使用e.hash (newCap - 1)计算新数组的索引位置 如果是红黑树走红黑树的添加 如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上。
10.5 刚才你说的通过hash计算后找到数组的下标是如何找到的呢你了解hashMap的寻址算法吗
这个哈希方法首先计算出key的hashCode值然后通过这个hash值右移16位后的二进制进行按位异或运算得到最后的hash值。
在putValue的方法中计算数组下标的时候使用hash值与数组长度取模得到存储数据下标的位置hashmap为了性能更好并没有直接采用取模的方式而是使用了数组长度-1 得到一个值用这个值按位与运算hash值最终得到数组的位置。
10.6 为何HashMap的数组长度一定是2的次幂
嗯好的。hashmap这么设计主要有两个原因
第一
计算索引时效率更高如果是 2 的n次幂可以使用位与运算代替取模。
第二
扩容时重新计算索引效率更高在进行扩容是会进行判断hash值按位与运算旧数组长租是否 0
如果等于0则把元素留在原来位置 否则新位置是等于旧位置的下标旧数组长度。
10.7 我看你对hashmap了解的挺深入的你知道hashmap在1.7情况下的多线程死循环问题吗
是这样
jdk7的的数据结构是数组链表。
在数组进行扩容的时候因为链表是头插法在进行数据迁移的过程中有可能导致死循环。
比如说现在有两个线程
线程一读取到当前的hashmap数据数据中一个链表在准备扩容时线程二介入
线程二也读取hashmap直接进行扩容。因为是头插法链表的顺序会进行颠倒过来。比如原来的顺序是AB扩容后的顺序是BA线程二执行结束。
当线程一再继续执行的时候就会出现死循环的问题。
线程一先将A移入新的链表再将B插入到链头由于另外一个线程的原因B的next指向了A所以B-A-B形成循环。
当然JDK 8将扩容算法做了调整不再将元素加入链表头而是保持与扩容前一样的顺序尾插法就避免了jdk7中死循环的问题。
10.8 hashmap是线程安全的吗
不是线程安全的。
10.9 那我们想要使用线程安全的map该怎么做呢
我们可以采用ConcurrentHashMap进行使用它是一个线程安全的HashMap。
10.10 那你能聊一下ConcurrentHashMap的原理吗
好的请参考《多线程相关面试题》中的ConcurrentHashMap部分的讲解。
10.11 HashSet与HashMap的区别
HashSet底层其实是用HashMap实现存储的HashSet封装了一系列HashMap的方法。依靠HashMap来存储元素值利用hashMap的key键进行存储而value值默认为Object对象。所以HashSet也不允许出现重复值判断标准和HashMap判断标准相同两个元素的hashCode相等并且通过equals()方法返回true。
10.12 HashTable与HashMap的区别
嗯他们的主要区别是有几个吧。
第一数据结构不一样hashtable是数组链表hashmap在1.8之后改为了数组链表红黑树
第二hashtable存储数据的时候都不能为null而hashmap是可以的
第三hash算法不同hashtable是用本地修饰的hashcode值而hashmap经常了二次hash
第四扩容方式不同hashtable是当前容量翻倍1hashmap是当前容量翻倍
第五hashtable是线程安全的操作数据的时候加了锁synchronizedhashmap不是线程安全的效率更高一些
在实际开中不建议使用HashTable在多线程环境下可以使用ConcurrentHashMap类。
