对于给定的键，可以有多个红黑树吗？ - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

Java集合面试题&知识点总结（下篇）

HashMap 用的哪种？问题 50. 何 HashMap 用红黑树而不使用 AVL 树？问题 51. HashMap 和 HashTable 有什么区别？问题 52....链表和红黑树：当哈希冲突发生时（即不同的键映射到同一索引位置），HashMap 会在对应的链表中进行查找或插入。当链表长度超过一定阈值（默认为 8）时，链表会转换为红黑树，以提高搜索效率。...红黑树是一种自平衡的二叉查找树，它可以保证任何一个节点到叶子节点的最长路径的长度不超过其他路径的两倍长度。...这是因为红黑树的查找效率比链表更高，当元素数量较多时，使用红黑树可以提高性能。当红黑树的节点数量减少到一定程度（默认为 6）时，红黑树会被转换回链表。...红黑树：TreeMap 的底层数据结构是红黑树，红黑树是一种自平衡的二叉查找树。在红黑树中，每个节点都包含了一个键值对，节点之间的排序关系由键决定。

2182 0

HashMap的31连环炮，我倒在第5个上

17：说说你对红黑树的了解 18：JDK8中对HashMap做了哪些改变？ 19：HashMap 中的 key 我们可以使用任何类作为 key 吗？...因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，所以，当链表长度 >= 8时，有必要将链表转换成红黑树。...16、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...17、说说你对红黑树的了解红黑树是一种自平衡的二叉查找树，是一种高效的查找树。红黑树通过如下的性质定义实现自平衡：节点是红色或黑色。根是黑色。所有叶子都是黑色（叶子是NIL节点）。...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用CAS + synchronized + Node + 红黑树。

5112 0

您找到你想要的搜索结果了吗？

是的

没有找到

深入理解HashMap，让你面试对答如流...

因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，所以，当链表长度 >= 8时，有必要将链表转换成红黑树。...拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...说说你对红黑树的了解红黑树是一种自平衡的二叉查找树，是一种高效的查找树。红黑树通过如下的性质定义实现自平衡：节点是红色或黑色。根是黑色。所有叶子都是黑色（叶子是NIL节点）。...HashMap 中的 key 我们可以使用任何类作为 key 吗？...底层变更为数组 + 链表 + 红黑树。 27. 熟悉ConcurrentHashMap 的并发度吗？程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。

8184 0

Java TreeMap 源码解析

大或相等的元素 higherEntry，返回所有比给定Map.Entry大的元素设计理念（design concept）红黑树（Red–black tree） TreeMap是用红黑树作为基础实现的...我这里想到一个比较严肃的问题，如果说二叉搜索树将问题规模减少了一半，那么三叉搜索树不就将问题规模减少了三分之二，这不是更好嘛，以此类推，我们还可以有四叉搜索树，五叉搜索树……对于更一般的情况： n个元素...这样也就大概能理解为什么二叉树这么流行了，就是因为进行一次比较操作，我们最多可以将问题规模减少一半。好了这里扯的有点远了，我们再回到红黑树上来。红黑树性质先看看红黑树的样子： ?...红黑树旋转示例（没有画出NIL节点）关于红黑树的插入、删除、左旋、右旋这些操作，我觉得最好可以做到可视化，文字表达比较繁琐，我这里就不在献丑了，网上能找到的也比较多，像v_July_v的《教你透彻了解红黑树...，7分钟左右，大家可以参考。这里还有个交互式红黑树的可视化网页，大家可以上去自己操作操作，插入几个节点，删除几个节点玩玩，看看左旋右旋是怎么玩的。

4881 0

Java TreeMap 源码解析

大或相等的元素 higherEntry，返回所有比给定Map.Entry大的元素设计理念（design concept）红黑树（Red–black tree） TreeMap是用红黑树作为基础实现的...我这里想到一个比较严肃的问题，如果说二叉搜索树将问题规模减少了一半，那么三叉搜索树不就将问题规模减少了三分之二，这不是更好嘛，以此类推，我们还可以有四叉搜索树，五叉搜索树……对于更一般的情况： n个元素...这样也就大概能理解为什么二叉树这么流行了，就是因为进行一次比较操作，我们最多可以将问题规模减少一半。好了这里扯的有点远了，我们再回到红黑树上来。红黑树性质先看看红黑树的样子： ?...红黑树旋转示例（没有画出NIL节点）关于红黑树的插入、删除、左旋、右旋这些操作，我觉得最好可以做到可视化，文字表达比较繁琐，我这里就不在献丑了，网上能找到的也比较多，像v_July_v的《教你透彻了解红黑树...，7分钟左右，大家可以参考。这里还有个交互式红黑树的可视化网页，大家可以上去自己操作操作，插入几个节点，删除几个节点玩玩，看看左旋右旋是怎么玩的。

3981 0

Java中 Treemap和 Treeset的使用

前言首先要注意的是,本文章不涉及到红黑树的具体实现,也就是说不会逐行分析TreeMap和TreeSet的源码实现,因为红黑树看了也会忘的… 所以本文只是记录红黑树的一些基础介绍,以及TreeMap和...TreeSet两个类的公共API. ---- 红黑树红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。...如果一个结点是红的，那么它的两个儿子都是黑的。对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。...通过这5个性质,可以保证红黑树的高度永远是logn,所以红黑树的查找、插入、删除的时间复杂度最坏为O(log n). 红黑树有什么作用呢?那就是快,查找,插入,删除的时间复杂度最坏为O(logn)....红黑树的具体实现可以google一下,有很多开源的实现.中心思想就是各种旋转~. TreeMap TreeMap是一个有序的key-value集合,基于红黑树（Red-Black tree）实现。

1.3K1 0

JAVA面试备战(二）--集合

List(对付顺序的好帮手)：List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象 Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。...另外，HashTable 基本被淘汰，不要在代码中使用它；对Null key 和Null value的支持：HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为...map底层为什么用红黑树实现？ 1、红黑树：红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。...通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下...红黑树的插入、删除、遍历时间复杂度都为O(lgN)，所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出，红黑树因为是排序插入的，可以按照键的值的大小有序输出。

4901 0

你都能回答出来吗？

9.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？ 10.说说你对红黑树的见解？ 11.jdk8中对HashMap做了哪些改变？...9.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。...接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器） 13.HashMap & TreeMap & LinkedHashMap 使用场景？...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。

7000 0

顺丰科技面试

先看问题自我介绍说一个你认为有挑战的项目怎么学习Java的说一下抽象类和接口说一下HashMap和Hashtable HashMap添加一个元素的流程什么是红黑树，特点是什么？...抽象类可以有构造方法，接口中不能有构造方法。抽象类中可以有普通成员变量，接口中没有普通成员变量，它的变量只能是公共的静态的常量一个类可以实现多个接口，但是只能继承一个父类，这个父类可以是抽象类。...，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出NullPointerException 。...，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。...红黑树的特点有5个：结点是红色或黑色。根结点是黑色。所有叶子都是黑色（叶子是NIL结点）每个红色结点的两个子结点都是黑色。

3332 0

顺丰面试，第二个问题把我劝退了！

先看问题自我介绍说一个你认为有挑战的项目怎么学习Java的说一下抽象类和接口说一下HashMap和Hashtable HashMap添加一个元素的流程什么是红黑树，特点是什么？...，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出NullPointerException 。...，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。...8.放入后判断当前链表是否超过最大允许链表长度8，如果超过则转为红黑树进行插入 9.如果map的索引表为空或者当前索引表长度还小于64（最大转红黑树的索引数组表长度），那么进行resize操作就行了；...红黑树的特点有5个：节点是红色或黑色。根节点是黑色。所有叶子都是黑色（叶子是NIL结点）每个红色节点的两个子节点都是黑色。

5492 0

Java集合：ConcurrentHashMap

一、ConcurrentHashMap 概述 ConcurrentHashMap 是 HashMap 的线程安全版本，其内部和 HashMap 一样，也是采用了数组 + 链表 + 红黑树的方式来实现。...2、JDK1.8 中结构 JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，...3、ConcurrentHashMap 在 Jdk1.7 和 Jdk1.8 中的区别数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。...链表转化为红黑树：定位结点的 hash 算法简化会带来弊端，Hash 冲突加剧,因此在链表节点数量大于 8 时，会将链表转化为红黑树进行存储。...红黑树的引入，对链表的优化使得 hash 冲突时的 put 和 get 效率更高获得JVM的支持，ReentrantLock 毕竟是 API 这个级别的，后续的性能优化空间很小。

6382 0

图解JDK 8 HashMap

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个 JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap...）时，将链表转化为红黑树，以减少搜索时间。...null : e.value; } 在定位到的桶中查找与给定键相匹配的节点。如果找到了匹配的节点，则返回该节点的值。...红黑树由于在链表中获取对应Value值的过程是通过for循环实现的，其时间复杂度为O(n)，当链表过长时，查询时间变长，JDK使用红黑树解决了该问题，当链表长度大于8时，链表进行树化。...红黑树结构如果存储桶中的元素是一个红黑树，则通过红黑树的查找算法，在红黑树中查找具有相同哈希码并且键相等的节点。后续内容文章持续更新中…

881 0

这21个刁钻的HashMap面试题，我把阿里面试官吊打了

9.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据块，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少...，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。...在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）关注微信公众号：Java大后端，在后台回复：资料，可以获取架构师资源干货。...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。

2.4K2 1

HashMap 和 Hashtable 的区别

另外，HashTable 基本被淘汰，不要在代码中使用它；对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个...，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。...② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码...底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容...，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

9473 0

21个刁钻的HashMap 面试

9.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少...，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。...在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）关注微信公众号：Java大后端，在后台回复：资料，可以获取架构师资源干货。...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。

3191 0

彻底服了：HashMap 夺命二十一问，顶不住了！

9.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少...，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。...接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器） 13.HashMap & TreeMap & LinkedHashMap 使用场景？...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。

4462 0

面试必问之HashMap

链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。...问题1.4 能说一下什么是红黑树吗？红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树....红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低，其平均统计性能要强于 AVL 。...红黑树通过3种操作来维持自身的平衡（插入或删除节点后） —变色，左旋，右旋问题1.5 还有其他集合的数据结构是红黑树吗？ treemap、hashset 问题1.6 红黑树能替换为二叉查找树吗？...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。

5551 1

Java集合之Map接口

，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。...而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。...）时，将链表转化为红黑树，以减少搜索时间。...TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。...数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。

5304 0

阿里 HashMap 面试夺命连环 21 问

4、你知道 hash 的实现吗？为什么要这样实现？...9、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？...而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少...，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。...锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。

6541 0

一文带你网罗HashMap面试考点！

2、HashMap的工作原理是什么？ 3、有什么方法可以减少碰撞？ 4、HashMap中hash函数怎么是是实现的? 5、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？...=->得到下标 5、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？...为什么不一直使用红黑树？之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。...而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少...，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

1K3 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭