【好看登录html源码】【神木资源源码】【stl源码剖析详解】arraylist源码1.7

时间:2024-12-29 01:33:33 来源:淘秀源码 分类:时尚

1.JDK成长记7:3张搞懂HashMap底层原理!
2.Java编程中since 1.7是什么意思
3.List LinkedList HashSet HashMap底层原理剖析

arraylist源码1.7

JDK成长记7:3张搞懂HashMap底层原理!

       一句话讲, HashMap底层数据结构,JDK1.7数组+单向链表、JDK1.8数组+单向链表+红黑树。好看登录html源码

       在看过了ArrayList、LinkedList的底层源码后,相信你对阅读JDK源码已经轻车熟路了。除了List很多时候你使用最多的还有Map和Set。接下来我将用三张图和你一起来探索下HashMap的底层核心原理到底有哪些?

       首先你应该知道HashMap的核心方法之一就是put。我们带着如下几个问题来看下图:

       如上图所示,put方法调用了putVal方法,之后主要脉络是:

       如何计算hash值?

       计算hash值的算法就在第一步,对key值进行hashCode()后,对hashCode的值进行无符号右移位和hashCode值进行了异或操作。为什么这么做呢?其实涉及了很多数学知识,简单的说就是尽可能让高和低位参与运算,可以减少hash值的冲突。

       默认容量和扩容阈值是多少?

       如上图所示,很明显第二步回调用resize方法,获取到默认容量为,这个在源码里是1<<4得到的,1左移4位得到的。之后由于默认扩容因子是神木资源源码0.,所以两者相乘就是扩容大小阈值*0.=。之后就分配了一个大小为的Node[]数组,作为Key-Value对存放的数据结构。

       最后一问题是,如何进行hash寻址的?

       hash寻址其实就在数组中找一个位置的意思。用的算法其实也很简单,就是用数组大小和hash值进行n-1&hash运算,这个操作和对hash取模很类似,只不过这样效率更高而已。hash寻址后,就得到了一个位置,可以把key-value的Node元素放入到之前创建好的Node[]数组中了。

       当你了解了上面的三个原理后,你还需要掌握如下几个问题:

       还是老规矩,看如下图:

       当hash值计算一致,比如当hash值都是时,Key-Value对的Node节点还有一个next指针,会以单链表的形式,将冲突的节点挂在数组同样位置。这就是数据结构中所提到解决hash 的冲突方法之一:单链法。当然还有探测法+rehash法有兴趣的人可以回顾《数据结构和算法》相关书籍。

       但是当hash冲突严重的时候,单链法会造成原理链接过长,导致HashMap性能下降,stl源码剖析详解因为链表需要逐个遍历性能很差。所以JDK1.8对hash冲突的算法进行了优化。当链表节点数达到8个的时候,会自动转换为红黑树,自平衡的一种二叉树,有很多特点,比如区分红和黑节点等,具体大家可以看小灰算法图解。红黑树的遍历效率是O(logn)肯定比单链表的O(n)要好很多。

       总结一句话就是,hash冲突使用单链表法+红黑树来解决的。

       上面的图,核心脉络是四步,源码具体的就不粘出来了。当put一个之后,map的size达到扩容阈值,就会触发rehash。你可以看到如下具体思路:

       情况1:如果数组位置只有一个值:使用新的容量进行rehash,即e.hash & (newCap - 1)

       情况2:如果数组位置有链表,根据 e.hash & oldCap == 0进行判断,结果为0的使用原位置,否则使用index + oldCap位置,放入元素形成新链表,这里不会和情况1新的容量进行rehash与运算了,index + oldCap这样更省性能。葫芦影视tv源码

       情况3:如果数组位置有红黑树,根据split方法,同样根据 e.hash & oldCap == 0进行树节点个数统计,如果个数小于6,将树的结果恢复为普通Node,否则使用index + oldCap,调整红黑树位置,这里不会和新的容量进行rehash与运算了,index + oldCap这样更省性能。

       你有兴趣的话,可以分别画一下这三种情况的图。这里给大家一个图,假设都出发了以上三种情况结果如下所示:

       上面源码核心脉络,3个if主要是校验了一堆,没做什么事情,之后赋值了扩容因子,不传递使用默认值0.,扩容阈值threshold通过tableSizeFor(initialCapacity);进行计算。注意这里只是计算了扩容阈值,没有初始化数组。代码如下:

       竟然不是大小*扩容因子?

       n |= n >>> 1这句话,是在干什么?n |= n >>> 1等价于n = n | n >>>1; 而|表示位运算中的或,n>>>1表示无符号右移1位。遇到这种情况,安卓扫描源码之前你应该学到了,如果碰见复杂逻辑和算法方法就是画图或者举例子。这里你就可以举个例子:假设现在指定的容量大小是,n=cap-1=,那么计算过程应该如下:

       n是int类型,java中一般是4个字节,位。所以的二进制: 。

       最后n+1=,方法返回,赋值给threshold=。再次注意这里只是计算了扩容阈值,没有初始化数组。

       为什么这么做呢?一句话,为了提高hash寻址和扩容计算的的效率。

       因为无论扩容计算还是寻址计算,都是二进制的位运算,效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。

       你可以再回顾下resize代码,看看指定了map容量,第一次put会发生什么。会将扩容阈值threshold,这样在第一次put的时候就会调用newCap = oldThr;使得创建一个容量为threshold的数组,之后从而会计算新的扩容阈值newThr为newCap*0.=*0.=。也就是说map到了个元素就会进行扩容。

       除了今天知识,技能的成长,给大家带来一个金句甜点,结束我今天的分享:坚持的三个秘诀之一目标化。

       坚持的秘诀除了上一节提到的视觉化,第二个秘诀就是目标化。顾名思义,就是需要给自己定立一个目标。这里要提到的是你的目标不要定的太高了。就比如你想要增加肌肉,给自己定了一个目标,每天5组,每次个俯卧撑,你看到自己胖的身形或者海报,很有刺激,结果开始前两天非常厉害,干劲十足,特别奥利给。但是第三天,你想到要个俯卧撑,你就不想起床,就算起来,可能也会把自己撅死过去......其实你的目标不要一下子定的太大,要从微习惯开始,比如我媳妇从来没有做过俯卧撑,就让她每天从1个开始,不能多,我就怕她收不住,做多了。一开始其实从习惯开始,先变成习惯,再开始慢慢加量。量太大养不成习惯,量小才能养成习惯。很容易做到才能养成,你想想是不是这个道理?

       所以,坚持的第二个秘诀就是定一个目标,可以通过小量目标,养成微习惯。比如每天你可以读五分钟书或者5分钟成长记,不要多,我想超过你也会睡着了的.....

       最后,大家可以在阅读完源码后,在茶余饭后的时候问问同事或同学,你也可以分享下,讲给他听听。

Java编程中since 1.7是什么意思

       java编程中since 1.7意思是从jdk1.7开始引进的新的api。

       Jdk1.7的新特性:

       1,switch中可以使用字串

       Java代码:

       String s = "test";

       switch (s) {

        case "test" :

        System.out.println("test");

        case "test1" :

        System.out.println("test1");

        break ;

        default :

        System.out.println("break");

        break ;

        }

       2."<>"这个玩意儿的运用List<String> tempList = new ArrayList<>(); 即泛型实例化类型自动推断。

       3.语法上支持集合,而不一定是数组

       Java代码:

       final List<Integer> piDigits = [ 1,2,3,4,5,8 ];

       4. 新增一些取环境信息的工具方法

       Java代码:

       File System.getJavaIoTempDir() // IO临时文件夹

       File System.getJavaHomeDir() // JRE的安装目录

       File System.getUserHomeDir() // 当前用户目录

       File System.getUserDir() // 启动java进程时所在的目录

       5. Boolean类型反转,空指针安全,参与位运算

       Java代码:

       Boolean Booleans.negate(Boolean booleanObj)

       True => False , False => True, Null => Null

       boolean Booleans.and(boolean[] array)

       boolean Booleans.or(boolean[] array)

       boolean Booleans.xor(boolean[] array)

       boolean Booleans.and(Boolean[] array)

       boolean Booleans.or(Boolean[] array)

       boolean Booleans.xor(Boolean[] array)

       6. 两个char间的equals

       Java代码:

       boolean Character.equalsIgnoreCase(char ch1, char ch2)

       7,安全的加减乘除

       Java代码:

       int Math.safeToInt(long value)

       int Math.safeNegate(int value)

       long Math.safeSubtract(long value1, int value2)

       long Math.safeSubtract(long value1, long value2)

       int Math.safeMultiply(int value1, int value2)

       long Math.safeMultiply(long value1, int value2)

       long Math.safeMultiply(long value1, long value2)

       long Math.safeNegate(long value)

       int Math.safeAdd(int value1, int value2)

       long Math.safeAdd(long value1, int value2)

       long Math.safeAdd(long value1, long value2)

       int Math.safeSubtract(int value1, int value2)

List LinkedList HashSet HashMap底层原理剖析

       ArrayList底层数据结构采用数组。数组在Java中连续存储,因此查询速度快,时间复杂度为O(1),插入数据时可能会慢,特别是需要移动位置时,时间复杂度为O(N),但末尾插入时时间复杂度为O(1)。数组需要固定长度,ArrayList默认长度为,最大长度为Integer.MAX_VALUE。在添加元素时,如果数组长度不足,则会进行扩容。JDK采用复制扩容法,通过增加数组容量来提升性能。若数组较大且知道所需存储数据量,可设置数组长度,或者指定最小长度。例如,设置最小长度时,扩容长度变为原有容量的1.5倍,从增加到。

       LinkedList底层采用双向列表结构。链表存储为物理独立存储,因此插入操作的时间复杂度为O(1),且无需扩容,也不涉及位置挪移。然而,查询操作的时间复杂度为O(N)。LinkedList的add和remove方法中,add默认添加到列表末尾,无需移动元素,相对更高效。而remove方法默认移除第一个元素,移除指定元素时则需要遍历查找,但与ArrayList相比,无需执行位置挪移。

       HashSet底层基于HashMap。HashMap在Java 1.7版本之前采用数组和链表结构,自1.8版本起,则采用数组、链表与红黑树的组合结构。在Java 1.7之前,链表使用头插法,但在高并发环境下可能会导致链表死循环。从Java 1.8开始,链表采用尾插法。在创建HashSet时,通常会设置一个默认的负载因子(默认值为0.),当数组的使用率达到总长度的%时,会进行数组扩容。HashMap的put方法和get方法的源码流程及详细逻辑可能较为复杂,涉及哈希算法、负载因子、扩容机制等核心概念。