在初始化链表的根时使用node*而不是只使用node的原因是因为链表是一种动态数据结构,需要通过指针来链接各个节点。在C/C++等编程语言中,node*表示一个指向节点的指针,而node表示节点本身。
node*
node
使用指针的好处有以下几点:
综上所述,初始化链表的根时使用node*是为了方便进行内存分配、节点链接和链表操作。
你可以理解为链表,如果hash冲突了,就把这个Node放到该位置的链表末尾。Java8之前采用的头插法,而Java8换成了尾插法,至于为什么要换,后面会讲。...当该位置的链表中的元素超过了TREEIFY_THRESHOLD所设置的数量时,就会触发树化,将其转化为红黑树。Java8里给的默认值是8。 为啥要转化成红黑树 首先我们要知道为什么要树化。...而红黑树则在插入和修改操作较为密集的时候表现更好。 而总结我们日常的HashMap使用,大多数情况下插入和修改应该是比查找更频繁一些的。而在这种情况下,红黑树的综合表现会更好一些。...那为什么后面又变成了尾插法呢?放心,肯定不是设计者闲的蛋疼,没事来改个设计。这样做一定是有一定的道理的。在解释这个问题之前,我们先来看看,如果采取头插法在多线程下的情况下会出现什么问题。...实际情况是,当自动扩容形成了环形链表后,当你去Get了一个在entry链上不存在的元素时,就会出现死循环的情况。
LinkedList虽然在日常开发中使用频率并不是很多,但作为一种和数组有别的数据结构,了解它的底层实现还是很有必要的。...在这之前我们先来复习下ArrayList的优缺点,ArrayList基于数组的动态管理实现的,数组在内存中是一块连续的存储地址并且数组的查询和遍历是非常快的;缺点在于在添加和删除元素时,需要大幅度拷贝和移动数据...从上面可以看到LinkedList有两个构造函数,一个无参,一个有参,有参的构造函数的功能是通过一个集合参数并把它里面所有的元素给插入到LinkedList中,注意这里为什么说是插入,而不是说初始化添加...index节点的前置节点和后置节点,如果不是在第一次初始化插入的情况下,这段代码的工作原理,大家可以理解为一个木棒一刀两断之后,第一段的末尾处就是前置节点,而第二段木棒的开始处就是后置节点,我们插入的数据就类似于放在两个木棒之间...这里我们看到链表中也自定义了序列化和反序列化的方法,在序列化时只写入x.item而并不是整个Node,这样做避免java自带的序列化机制会把整个Node的数据给写入序列化,并且如果Node还是双端链表的数据结构
当计算出的hash值相同时,我们称之为hash冲突,HashMap的做法是用"链表和红黑树"存储相同hash值得value。当hash冲突的个数较少时,就使用链表,否则使用红黑树。...此函数通常通过将对象的内部地址转换为整数来生成哈希码,从而为所有不同的对象生成不同的哈希码。为什么链长度为8时,链表转成树;长度为6时,树转成链表?...则就发生扩容"transient Node[] table; "Hash数组table中存放指向链表的引用,table 它在resize()方法中初始化,并不是在构造方法里面初始化的" transient...具体原因如下:因为我们使用的是 2 次幂的扩展(指长度扩为原来 2 倍),所以,元素的位置要么是在原位置,要么是在原位置再移动 2 次幂的位置。...因为当 table 数组容量比较小时,键值对节点 hash 的碰撞率可能会比较高,进而导致链表长度较长。这个时候应该优先扩容,而不是立马树化。
HashMap为什么线程不安全,如何替换。 HashMap在JDK7跟JDK8中的区别。 HashMap中链表跟红黑树切换思路。10.HashMap中链表跟红黑树是怎么个维持方法。...当我们构造ArrayList时;若使用默认构造函数,则ArrayList的默认容量大小JDK7=10,JDK8=0。...java.util.HashMap.Node 就是我们HashMap中存储的基本的KV。 ?...这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。 动态参数 transient Node[] table HashMap的链表数组。...无论我们初始化时候是否传参,它在自扩容时总是2的次幂。
主要是围绕源码本身展开,以添加注释的方式进行记录和分析 image.png 初始化 在创建 HashMap 对象示例的时候不会初始化存储数组,会在首次调用 put 方法的时候初始化数组。...,最终构造出来的树可能是经历多个平衡操作,根节点目前到底是链表的那个节点是不确定的 // 因为我们需要基于树来做查找,所以就应该把 tab[N] 得到的对象一定是根节点对象,而且是链表的第一个节点对象...在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3. 所有叶子都是黑色。(叶子是NIL结点) 性质4....因为我们需要基于树来做查找,所以就应该把 tab[N] 得到的对象一定是根节点对象,而且是链表的第一个节点对象,所以要做对应的调整。...当放置的集合元素个数达千万级时会影响程序性能。 使用 entrySet 遍历 Map 类集合 KV,而不是 keySet 方式进行遍历。
----张风捷特烈 场景:模拟英语字典,有索引类和单词类,索引作为键,单词作为值放入HashMap中 由于HashMap挺大的,本篇只说一下HashMap的插入操作,包括:扩容、链表插入、链表树化...else if (oldThr > 0) //旧的扩容阀值大于零,说明并不是初始化 newCap = oldThr; else {//☆☆☆这里是添加第一个元素时扩容初始化的地方...HashMap初始化.png ---- 二、插入分析 在索引为5的地方插入了一个链表节点,索引位置由:[表容量-1 & 添加键的哈希值]决定 节点:hash=21----key:WordIndex{...hash 至于为什么如此: 1.添加时将[key的hash值]亦或[key的hash值无符号右移16位] static final int hash(Object key) { int h;...{ //根节点为空时,初始化根节点 x.parent = null; x.red
4、HashMap中hash函数怎么是是实现的? 5、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树? 6、说说你对红黑树的见解?...达摩:不是的,面试官一般都会用连环炮的方式提问的。 小鲁班:你说的连环炮是什么意思鸭? 达摩:那我举个例子 就比如问你HashMap是不是有序的? 你回答不是有序的。...当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。...=->得到下标 5、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?...为什么不一直使用红黑树? 之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。
HashMap作为我们熟悉的一种集合,可以说是面试必考题。简单的使用,再到原理、数据结构,还可以延伸到并发,可以说,就一个HashMap,能聊半个小时。 1.能说一下HashMap的数据结构吗?...简单来说,就是初始化时,传的不是2的倍数时,HashMap会向上寻找离得最近的2的倍数,所以传入17,但HashMap的实际容量是32。...我们到现在已经知道,HashMap使用链表的原因为了处理哈希冲突,这种方法就是所谓的: 链地址法:在冲突的位置拉一个链表,把冲突的元素放进去。...理想情况下,使用随机哈希码,链表里的节点符合泊松分布,出现节点个数的概率是递减的,节点个数为8的情况,发生概率仅为0.00000006。 至于红黑树转回链表的阈值为什么是6,而不是8?...HashMap不是线程安全的,可能会发生这些问题: 多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素,在多线程的环境下,扩容的时候有可能导致环形链表的出现,形成死循环。
也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。...那加载因子为什么是 0.75 而不是 0.5 或者 1.0 呢?...HashMap 是线程安全的吗,为什么不是线程安全的?...,const_map不能用,只希望确定某一个关键值是否存在而不希望插入元素时也不应该使用,mapped_type类型没有默认值也不应该使用。...Java 8在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为O(N))转换为红黑树(寻址时间复杂度为O(log(N))) synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash
当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。...以下是HashMap初始化 ,简单模拟数据结构 Node[] table=new Node[16] 散列桶初始化,tableclass Node { hash;//hash值 key;//键 value...=->得到下标 5、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?...为什么不一直使用红黑树? 之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。...而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少
做积极的人,而不是积极废人!...当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。...=->得到下标 5、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?...为什么不一直使用红黑树? 之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。...而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少
小鲁班:问这么多内容,那岂不是一个人都面试很久吗? 达摩:不是的,面试官一般都会用连环炮的方式提问的。 小鲁班:你说的连环炮是什么意思鸭?...当我们给 put() 方法传递键和值时,我们先对键调用 hashCode() 方法,计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。...那么当我们用 hash 算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。 所以,我们首先想到的就是把 hashcode 对数组长度取模运算。...为什么不一直使用红黑树? 之所以选择红黑树是为了解决二叉查找树的缺陷:二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成层次很深的问题),遍历查找会非常慢。...开放定址法 当冲突发生时,使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的地址。
“当然用过,HashMap是一种的存储结构,能够快速将key的数据put方式存储起来,然后很快的通过get取出来”,然后说“HashMap不是线程安全的, 答: HashTable...这个时候说明他已经很熟练使用HashMap的工具了。 问:“你知道HashMap 在put和get的时候是怎么工作的吗?”...e = p; //这里为什么要把p赋值给e,而不是直接覆盖原值呢?...我们在使用put方法时很少用他的返回值,甚至忘了它的存在,这里我们知道,他返回的是被覆盖的oldValue。...if (first instanceof TreeNode) //当这个table节点上存储的是红黑树结构时,在根节点first上调用getTreeNode方法
7.HashMap中put方法的过程? 8.数组扩容的过程? 9.拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树? 10.说说你对红黑树的见解?...,将table长度变为原来的两倍(注意是table长度,而不是threshold) ④、如果数据很大的情况下,扩展时将会带来性能的损失,在性能要求很高的地方,这种损失很可能很致命。...9.拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?...(桶的数量必须大于64,小于64的时候只会扩容) 发生hash碰撞时,java1.7会在链表的头部插入,而java1.8会在链表的尾部插入 在java1.8中,Entry被Node替代(换了一个马甲...(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动); 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时
生活中提到 “树”,我们肯定会想到去公园遛弯时看到的树木。一棵树只有一个主干,但是主干上面会分出无数的树枝,树枝又各自分叉产生新的树枝,这样层层分叉最终变成了我们看到那棵枝繁叶茂的大树。...本篇我们实现一棵二叉搜索树。 初始化类 在开始写二叉搜索树之前,需要先定义一个节点类,存储我们基本节点的数据。...其实只是含义上的区别。双向链表的两个属性指向的都是兄弟元素,而上述的节点类的 left 和 right 指向的是子元素。 在树当中,节点也被称为 键。...类,这个类和链表的结构也差不多,其中属性 root 表示根节点,传入一个自定义函数用来自定义节点如何比较。...本篇我们只介绍一个 insert 方法。
在 JDK8 以后,由于考虑到哈希冲突严重时,“桶”中的链表会影响查询效率,因此在一定条件下,链表元素多到一定程度,Node 就会转为 TreeNode,也就是把链表转为红黑树。...在 HashMap 中数组的每一个位置都是一个“桶”,而“桶”中存放的就是带有数据的节点对象 Node。当哈希冲突时,多个 Node 会在同一个“桶”中形成链表。...Node节点转为TreeNode节点; 构建树,添加每一个子节点的时候判断是否需要再平衡; 构建完后,若原本链表的头结点不是树的根节点,则再平衡确保头节点变为根节点 链表转为红黑树的条件 这里我们也理清楚了链表树化的条件...我们暂且只关注链化的判断条件,也就是在 removeTreeNode()中的这一段代码: // 根节点为null,根节点的左或右子节点为null,根节点左子节点的左子节点为null if (root =...也就是说,和网上所说的小于6就链化不同,在删除中,链化触发值是一个范围,在 [3,10] 之间。 3.红黑树在扩容过程的链化 我们知道,扩容经过重哈希有可能会拆分链表,树也一样。
前言 本文的分析的源码是JDK8的版本,上一节我们介绍了HashMap,提到了多线程避免扩容时出现死循环,时要使用ConcurrentHashMap,下面我来讲解一下ConcurrentHashMap这个东西简单的基本原理是什么...,我们为什么用。...这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。...TreeBin 他是一个对象,包装的很多TreeNode节点,它代替了TreeNode的根节点,也就是说在实际的ConcurrentHashMap“数组”中,存放的是TreeBin对象,而不是TreeNode...而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。
,Concurrent的table中如果是红黑树的形式,存储的是TreeBin并不是TreeNode,但TreeBin并不是红黑树的存储节点,TreeBin通过root属性来维护红黑树的根节点。...JDK 1.8 ConcurrentHashMap初始化 ConcurrentHashMap初始化过程并不是在构造的时候,而是在第一次进行put操作的时候通过initTable()方法来进行初始化。...: key的hash值 & (hash桶的size-1) 为什么需要通过spread来重新计算key的hash值,而不是直接使用key.hashCode作为hash值?...Unsafe.getObjectVolatile方法 在我们获取table中的元素时我们并没有使用table[i]直接去获取,而是通过getObjectVolatile方法去内存中获取指定的数据?...红黑树退化为链表 11.1 remove元素时发生退化 红黑树退化为链表发生在我们对ConcurrentHashMap的元素进行移除时,也就是调用其remove方法时,会有下面一段逻辑: else if
不幸的是,很大部分人都拜倒在HashMap的石榴裙底下。 HashMap为什么如此受面试官青睐? 我觉得其中有4个原因: HashMap在我们工作中使用频率相当高。...14:说说resize扩容的过程 15:说说hashMap中get是如何实现的? 16:拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?...() 方法,将 table 长度变为原来的两倍(注意是 table 长度,而不是 threshold); ④、如果数据很大的情况下,扩展时将会带来性能的损失,在性能要求很高的地方,这种损失很可能很致命。...16、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?...(桶的数量必须大于64,小于64的时候只会扩容) 2.发生hash碰撞时,java 1.7 会在链表的头部插入,而java 1.8会在链表的尾部插入 3.在java 1.8中,Entry被Node替代(
HashMap的存储与一般的数组不同,HashMap的每一个元素存储的并不是一个值,而是一个引用类型的Node结点,这也就意味着这个Node结点有被扩充的可能,因为这个Node结点可以是一个链表的Head...为什么选择0.75作为默认的负载因子呢?这并不是随意的选择,而是经过深思熟虑后的优化值。负载因子实际上是一个权衡空间和时间的参数。...通过将负载因子设置为0.75,可以在空间和时间效率之间取得平衡。这意味着,当数组接近其容量时,HashMap会进行扩容,以避免因哈希冲突而导致的性能下降。.../** * 在我们的列表转为红黑树的时候,如果我们的数组长度(也就是容量)达不到64,那我们就扩充数组 * 而不是进行红黑树的转化 **/ static...写了注释的直接看看就好,关于树的我不说了,只说链表。
领取专属 10元无门槛券
手把手带您无忧上云