NanoPi R2S 软路由折腾记

😩 问题多多

最开始用的是YouTuber 洋葱提供的固件,但是存在一些问题:

  1. TF卡的空间没有挂载完(8G的卡,只用到了1G左右),自己用fdisk挂载逻辑分区报错;
  2. 修改docker默认存储位置后,镜像依赖的一些程序无法使用,如curl等;
  3. 直接opkg install安装固件总会出一些莫名其妙的依赖问题,opkg update也好,还是直接ipk安装,都会遇到很多奇奇怪怪的问题;

🧐 有机会?

接着,我就去openwrt官网找了镜像,但无论是用工具balenaEther刷入,还是使用dd命令写入。当在TF卡插回R2S时,SYS灯一直红色长亮,wan和lan的灯无任何响应。
由于R2S本身还有挑卡的毛病,不太确定是不是镜像本身存在问题;

😋 解决啦~

后面意外发现其实友善也有自己的官网,在其wiki上找到了镜像下载地址
下载刷入以后,正常启动。

我用的是balenaEther,但使用dd应该也是可行的

docker也可正常使用。当然还是遇到了一些小问题。

🐛 一些小问题

openclash订阅更新一直失败

安装好openclash插件以后,在更新订阅时,一直提示失败。

DNS无法解析

常见DNS无法解析,直接写到etc/hosts,使用ping或者nslookup命令验证解决

curl命令缺少依赖文件

openclash下载文件也是依赖于wget或者curl之类命令,我ssh连接到路由器以后,测试了一下这两个命令是否可正常下载文件,结果到curl时,发现缺少了部分so依赖文件,使用opkg install安装对应的包就解决了。
参考:libwolfssl5.2.0.99a5b54a_5.2.0-stable-2_x86_64.ipk OpenWrt 21.02 Download

🥶 继续折腾HASS

未完待续…

Docker容器一启动就挂,要怎么排查?

1. 分析镜像信息

通过

1
docker inspect 镜像ID

可以查看当前镜像的属性信息,那么我们重点需要关注的是Entrypoint这个属性的信息。
关于entrypoint是什么,你可以参考Dockerfile reference | Docker Documentation

我这里获取到的Entrypoint信息如下:

1
2
3
"Entrypoint": [
"/docker-entrypoint.sh"
],

这个Entrypoint可以说是非常的简单,但是又非常的复杂。
简单在于就一行,是直接去执行/docker-entrypoint.sh这个脚本,但是复杂在于我们并不能直接看到这个docker-entrypoint.sh的内容。

2. 分析Entrypoint

一般来说,我们有几种方法可以看到这个/docker-entrypoint.sh文件:

  1. 挂载:通过docker run -v将这个目录挂载到宿主机上,就算这个容器一启动就死,我们也不用担心拿不到文件;
  2. 交互命令(这个词是我自己想的,可能不是很准确):通过docker run -it 镜像ID sh -c "cat /docker-entrypoint.sh"去查看内容。这个方法其实还是需要容器启动的,如果是启动立刻挂的情况,这个方法应该是会失效的;
  3. 跳过entrypoint:通过`docker run –entrypoint sh 镜像ID -c “cat /docker-entrypoint.sh”,即可覆盖镜像中的entrypoint,覆盖以后,容器并没有去运行entrypoint脚本,所以也就不会挂了。

3. 覆盖entrypoint

既然都可以覆盖entrypoint了,那我们为啥要局限于通过交互命令去查看文件呢?

1
docker run -d --entrypoint sh 镜像ID -c "ping 127.0.0.1"

通过这个命令,给容器一个不可完成的任务,那么这个容器将一直存活。然后再通过

1
docker exec -it 容器ID sh

进入容器,岂不是美哉?

如果你的镜像比较简单,可能会没有ping命令,那么你可能需要tail或者其他命令来保证容器可长期存活

4. 手动执行entrypoint

容器不会被自动杀掉以后,我们就可以一步一步的去分析这个entrypoint到底是死在哪儿了?

这里就没有办法展开讲了,因为每个人的情况都是不同的,只要有点耐心,我相信一定是可以解决的。

Docker(K8S)环境下开启JMX远程监控

问题引入

JMX(即Java Management Extensions),如果你在网上搜索如何配置JMX,你就会看到这样的一堆配置

1
2
3
4
5
6
-Djava.rmi.server.hostname=
-Dcom.sun.management.jmxremote
-Dcom.sun.management.jmxremote.rmi.port=
-Dcom.sun.management.jmxremote.port=
-Dcom.sun.management.jmxremote.authenticate=false
-Dcom.sun.management.jmxremote.ssl=false

然后你就会发现在docker下,怎么弄都不对。

JMX分析

JMX其实需要注册三个端口,其作用为:

  • 端口1: 接收注册请求,JMX客户端(如jvisualvm)在连接时,需要填写的端口号

  • 端口2: 用于远程连接,可以与端口1使用同一个端口号

  • 端口3: 用于本地连接,随机(这个端口在实际业务场景中,不需要去指定,我暂时没研究如何指定这个端口)

排坑

坑点1 JMX端口仅暴露1个

由于JMX是在远程监控的情况下是需要两个端口的,所以在Docker环境下很可能就会出现因为端口没映射全而导致的失败

解决办法也很简单,就是把端口1和端口2设置为同一个端口即可,这样也可以减少端口映射过多而产生的端口冲突

1
2
-Dcom.sun.management.jmxremote.rmi.port=8888
-Dcom.sun.management.jmxremote.port=8888

注:8888这个端口是我随便写的,在合法范围内都可以

坑点2 java.rmi.server.hostname配置导致JMX连接失败

坑点1其实在网络上已经有大把大把现成的文章了,而对于坑点2,则在于java.rmi.server.hostname这个配置。我个人认为这个是因为JMX诞生比较早,所以JMX并没有适配容器化,这就导致了第二个坑点。

java.rmi.server.hostname配置失败的体现在于,你的JMX客户端,会在连接中卡顿很久,这其实就是JMX尝试连接,但连接不上导致的。

JMX客户端根据你填写的IP和PORT去查找JMX服务,这时候你的服务端会返回这个java.rmi.server.hostnamecom.sun.management.jmxremote.rmi.port,JMX客户端再根据这两个值去连接。

那么在docker环境下,你配置的java.rmi.server.hostname很可能就配置错了,你需要保证这个java.rmi.server.hostname是客户端直接可连的,并且这个com.sun.management.jmxremote.rmi.port也是可以直接访问的。

我使用的环境是我用我的笔记本去监控运行在服务器K8S集群中的服务,这种情况下,我需要把java.rmi.server.hostname配置为这个集群所使用的映射服务IP,

如果你的映射服务IP过多,这就会很麻烦,因为每次修改java.rmi.server.hostname需要重启,而重启等同于重新部署,这就导致有可能不匹配,这个问题可能需要想办法绑定,或者自己手动用kubectl做映射

并且你还需要保证com.sun.management.jmxremote.rmi.port是映射服务所使用的端口。

创建端口映射的时候,就保证你的容器端口和映射端口得是一致的,不然JMX服务返回给JMX客户端的端口,没办法通过端口映射连接了

![在这里插入图片描述](https://img-blog.csdnimg.cn/129b48695cbd44c5a6c6d0f346c23666.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAYmFvZmVpZHl6,size_20,color_FFFFFF,t_70,g_se,x_16 align=”left”)

参考

how-to-connect-with-jmx-from-host-to-docker-container-in-docker-machine

解决macOS Big Sur升级后部分java应用无法打开的问题JavaVM: Failed to load JVM: libserver.dylib

升级到macOS Big Sur以后,之前安装的dbeaver和mat都无法打开了,点击报错都是同一个问题。

实际上oracle jdk在安装完成以后是没有 libserver.dylib 这个文件的,但是dbeaver和mat还是在查找这个文件,应该是出兼容性bug了。

解决的方案很简单,就是要找到这个 libserver.dylib 对应应该是什么文件就可以了。几番折腾之下,我在这里找到了答案,实际的地址应该是

1
/Library/Java/JavaVirtualMachines/jdk1.8.0_271.jdk/Contents/Home/jre/lib/server/libjvm.dylib

使用ln -s创建一个链接就可以解决了。

1
sudo ln -s /Library/Java/JavaVirtualMachines/jdk1.8.0_271.jdk/Contents/Home/jre/lib/server/libjvm.dylib /Library/Java/JavaVirtualMachines/jdk1.8.0_271.jdk/Contents/Home/lib/libserver.dylib

如果你的jdk文件夹和我的命令不一样,请记得修改命令。

升级之前为啥没有这个问题,我就不知道了,很有可能我之前创建过链接被macOS给删掉?(可能性不大吧)

不要直接复用其他业务的线程池

前言

最近在复查团队小伙伴的代码时发现,错误复用了一个定时触发信息同步的线程池。但他开发的代码所对应的业务场景是响应前端页面的请求。而这次的线程池复用将可能会导致系统页面“卡死”。

信息同步的线程池,其主要配置信息为:

  • corePoolSize:4
  • maximumPoolSize:8
  • keepAliveTime:30L
  • unit:TimeUnit.SECONDS
  • workQueue:new ArrayBlockingQueue<>(1000)
  • threadFactory:new com.google.common.util.concurrent.ThreadFactoryBuilder().setNameFormat("xxx-pool-%d").build()
  • handler:new ThreadPoolExecutor.CallerRunsPolicy()

这个定时任务设定为每半个小时执行一次,当定时任务开始执行后,这个队列任务很快就会装满。

如果这个时候响应前端页面请求的线程进入,就会进行等待队列,此时可能会发生:

  1. 任务队列满,触发丢弃策略,前端页面请求被丢弃,用户拿不到的正确的数据;
  2. 任务较多,前端页面请求等待,可能会出现前端页面请求超时,系统“卡死”;

分析

存在任务优先级存在问题。页面请求的优先级应大于信息同步任务的优先级,但如果复用同一个线程池,那么在任务执行顺序上,就是先进先执行。

如果此前已经有多个信息同步任务正在等待,页面请求也必须要等到信息同步任务执行完成以后才可以去与其他线程抢占系统资源。

结论

对于一些优先级较高的任务,应当独立维护线程池。虽然在JVM中还存在线程调度问题,但至少不会一直阻塞去等待其他任务的执行。

对于一些优先级较低的定时任务,可以考虑适当复用,与此同时也需要考虑好核心线程数、最大线程数、等待队列、丢弃策略等。

很多技术解决方案都是一把双刃剑,用得好,事半功倍,用不好,系统宕机😂

git仓库从30G压缩到600M-git文档仓库过大的优化方案

项目上使用git管理相关文档,因维护多年,导致其文档仓库已经逼近30G的大小,对于我这台256G的MBP来说,无疑是占用了巨大的空间,介于此,我计划减少这个仓库的体积。

git-lfs

git-lfsatlassian维护的开源项目,意图解决因反复修改大文件而导致git仓库变大,以及影响初次下载的体验;

在我尝试使用git-lfs后,占用空间被压缩到了24G左右,但效果并不明显,这主要是因为这个git仓库中的大部分文档都不存在反复修改的情况,大部分文件都是上传后再也没有改过。

可以说git-lfs解决了我一部分的问题,但并没有全部解决。

GVFS

GVFS是微软的开源项目,意图解决git对于超大型仓库的维护问题,但很可惜,GVFS依赖于window操作系统,我手上主力机还是macOS,所以GVFS就不考虑了。

git sparse checkout

sparse checkout是git自己维护的功能,其提供的功能是告诉git相关的命令再拉取时仅拉取部分文件,或排除掉部分文件。

很现实,sparse checkout就是解决我这个问题的最佳方案

使用方法

  1. 新建仓库并设置远端仓库地址
1
2
git init
git remote add -f origin <url>
  1. 开启配置
1
git config core.sparsecheckout true
  1. 配置想要拉取的文件路径
1
xxx/xxx/**

或者是不想要拉取的文件路径

1
!yyy/**

然后正常使用git pull拉取即可

  1. 注意使用较新版本的git;

  2. 使用方法也可以参考[官网链接](git config core.sparsecheckout true)

结论

最终我使用的是git-lfs搭配git parse checkout搭配使用,一方面降低大文件重复修改所产生的占用,一方面只需要拉取我自己需要的文件到本地即可。

这样操作以后,原30G的git仓库,我现在只需要600M就可以了~

Java应用被k8s认定为oom杀掉

前不久现场反馈说服务运行一段时间就重启了,希望我介入排查一下。

先说结论

jvm堆大小与k8s pod设置的大小一致,均为4g。因jvm还存在其他的内存占用,pod服务总体的内存占用会超过4g,k8s认定为oom,将其杀掉。以及jvm较低版本没有支持容器namespace的资源隔离。

处理过程

  1. 检查日志

    看服务重启前后日志有无抛出一些较为严重的错误,是否存在因为个别异常导致的服务重启;

  2. 修改jvm堆的大小,增加oom时候自动dump等参数

    1. 怀疑是系统内部有一些“不良”业务导致的堆的大量占用,试想是否可以通过增加堆的大小,再对堆进行快照分析,确定具体占用较大堆内存的业务代码,对其进行定向优化。
    2. 增加-XX:+HeapDumpOnOutOfMemoryError以及-XX:HeapDumpPath=/myPath/heapdump.hprof参数,让jvm在下一次oom时自动导出堆的快照,便于分析。

    通过不停的分析堆的镜像快照,确实是没有任何业务代码过多的或者过量的导致了堆的增长,增加的-XX:+HeapDumpOnOutOfMemoryError也没有生效。

  3. 检查k8s pod信息

    在k8s
    pod信息查到,服务是以oom的原因导致被kill的。经过了解,k8s认定pod的内存占用达到了pod所配置的limit值时,就会判定为oom,然后杀掉,从侧面增加-XX:+HeapDumpOnOutOfMemoryError
    无效的原因。

    检查现场配置时发现,jvm堆的大小和pod的大小限制一致。已知java 8除了堆以外还有其他的内存占用,猜测是不是这部分导致了pod实际内存使用大小超过了pod限制导致。

    修改pod限制参数为6g后,问题得以解决。

后续思考

虽然修改为6g以后,服务不再被k8s以oom的原因kill了,但于此同时,还有一个问题一直萦绕着我。

为什么jvm没有回收内存?

在一番了解后,我了解到Java 1.8有一个更新,在Java 1.8
191这个版本中,Java更新了对于namespace的支持,地址是:https://www.oracle.com/java/technologies/javase/8u191-relnotes.html,对应具体的bug描述是https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8146115

容器是通过linux的namespace做资源隔离,通过pid下的cgroup做资源限制,但是在早先版本中,jvm并没有支持这一特性,从而导致了jvm内存不回收的问题。

jvm指定的堆大小到底

类的加载、链接和初始化(基于Java 1.8)

Java的数据类型(Data type)主要是有两种:

  1. 基本类型 primitive types
  2. 引用类型 reference types

其中引用类型又被细分为:

  1. 类 class types
  2. 数组 array types
  3. 接口 interface types

基本类型和数组类型是由Java虚拟机直接生成的,其他(类 class types、接口 interface types)则需要Java虚拟机对其进行链接和初始化。

1. Java虚拟机启动 Java Virtual Machine Startup

  • 通过引导类加载器创建一个初始类来启动,并执行这个public class中的void main(String[])方法。
  • 初始类可以作为命令行参数提供。或者,该实现可以提供一个初始类,该初始类设置一个类加载器,该类加载器进而加载。

2. 创建和加载 Creation and Loading

  • 指查找字节流,并据此创建类的过程。
  • 其中数组(array types)是没有字节流的,由Java虚拟机直接生成,对于其他的类来说,Java虚拟机需要借助于类加载器来完成查找字节流的工程。

2.1 类加载器 ClassLoader

在Java虚拟机规范中,类加载器被分为两种:

  1. Java虚拟机提供的引导类加载器(bootstrap class loader)
  2. 用户定义的类加载器(user-defind class loaders)

2.1.1 Java虚拟机提供的引导类加载器 bootstrap class loader

  • bootstrap class loader 由Java虚拟机提供的
  • 这个类加载器是使用C++实现的,没有对应的Java对象。

2.1.2 用户定义的类加载器 user-defind class loaders

  • user-defind class loaders 是Java虚拟机规范中对于类加载器的分类划分,是一个统称,实际上并没有这个类加载器
  • 用户定义的类加载器都是java.lang.ClassLoader类的子类
  • 在Java虚拟机规范中提到,用户定义的类加载器可以实现通过网络下载类,动态生成类或从加密文件中提取类
  • 用户定义的类加载器需要由bootstrap class loader去加载
  • 在Java1.8的核心类库中,提供了两个类加载器,分别是:
    1. 扩展类加载器 extention class loader
      sun.misc.Launcher.ExtClassLoader
    2. 应用类加载器 application class loader
      sun.misc.Launcher.AppClassLoader

2.1.2.1 扩展类加载器 extention class loader

  • 扩展类加载器的父是启动类加载器(bootstrap class loader)
  • 负责加载相对次要、但又通用的类,如JRE的lib/ext目录下jar包中的类(以及java.ext.dirs指定的类, 这个可以通过查看sun.misc.Launcher.ExtClassLoader.getExtDirs()方法确认)

2.1.2.2 应用类加载器 application class loader

  • 应用类加载器的父则是扩展类加载器
  • 负责加载应用程序路径下的类(应用程序指虚拟机参数-cp/-classpath、系统变量java.class.path或环境变量CLASSPATH所指定的路径。这个可以通过查看sun.misc.Launcher.AppClassLoader确认)
  • 默认情况下,应用程序中包含的类便是通过应用类加载器加载的。

2.1.3 双亲委派模型

  • 指的是一个类加载器接收到加载请求时,会先将请求转发给父类加载器,在父类加载器没有找到所请求的类的情况下,该类加载器才会去尝试加载。

  • 双亲委派模型可以避免类的重复加载,以及java的核心api被篡改的问题。

3 链接 Linking

  • 指将创建的类合并至Java虚拟机中,使之能够执行的过程。可分为验证(Verification)、准备(Preparation)以及解析(Resolution)三个阶段

3.1 验证 Verification

验证是为了确保被加载的类满足Java虚拟机的约束条件。

3.2 准备 Preparation

  • 准备是为被加载的类的静态字段分配内容。
  • 构造其他跟类层次相关的数据结构:如用来实现虚方法的动态绑定的方法表。

3.3 解析 Resolution

在开始解析之前,需要知道:
class文件被加载到Java虚拟机之前,这个类无法知道其他类及其方法、字段所对应的具体地址,甚至不知道自己方法、字段的地址。因此,每当需要引用这些成员时,Java编译器会生成一个符号引用。在运行阶段,这个符号引用一般都能无歧义地定位到具体目标上。

  • 解析的目标是将符号引用解析成为实际应用: 如果符号引用指向一个未被加载的类,或者未被加载类的字段或方法,那么解析就触发这个类的加载。(但未必会出发这个类的链接和初始化)

此外,在Java虚拟机规范中并没有要求在链接过程中完成解析。仅规定了:如果某些字节码使用了符号引用,那么在执行这些字节码之前,需要完成对这些符号引用的解析。

4. 初始化 Initialization

  • 为标记为常量值的字段赋值,以及执行<clinit>方法的过程
  • Java虚拟机会通过加锁来确保类的<clinit>方法仅被执行一次

常量值解释:
Java代码中,如果要初始化一个静态字段,可以在声明时直接赋值,或者在静态代码块中对其进行赋值
如果直接赋值的静态字段被final所修饰,并且它的类型是基本类型或字符串时,该字段便会被Java编译器标记为常量值(ConstantValue)

4.1 初始化的触发条件

在Java虚拟机规范中明确枚举了以下情况:

  • The execution of any one of the Java Virtual Machine instructions new, getstatic, putstatic, or invokestatic that references C (§new, §getstatic, §putstatic, §invokestatic). These instructions reference a class or interface directly or indirectly through either a field reference or a method reference.

  • Upon execution of a new instruction, the referenced class is initialized if it has not been initialized already.

  • Upon execution of a getstatic, putstatic, or invokestatic instruction, the class or interface that declared the resolved field or method is initialized if it has not been initialized already.

  • The first invocation of a java.lang.invoke.MethodHandle instance which was the result of method handle resolution (§5.4.3.5) for a method handle of kind 2 (REF_getStatic), 4 (REF_putStatic), 6 (REF_invokeStatic), or 8 (REF_newInvokeSpecial).

  • This implies that the class of a bootstrap method is initialized when the bootstrap method is invoked for an invokedynamic instruction (§invokedynamic), as part of the continuing resolution of the call site specifier.

  • Invocation of certain reflective methods in the class library (§2.12), for example, in class Class or in package java.lang.reflect.

  • If C is a class, the initialization of one of its subclasses.

  • If C is an interface that declares a non-abstract, non-static method, the initialization of a class that implements C directly or indirectly.

  • If C is a class, its designation as the initial class at Java Virtual Machine startup (§5.2).

Java虚拟机规范中有部分是依赖于Java虚拟机指令了,我对此了解并不多,以下摘抄于《极客时间-深入拆解Java虚拟机-郑雨迪》的分享,相较而言更通俗易懂些。

  1. 当虚拟机启动时,初始化用户指定的主类;
  2. 当遇到用以新建目标类实例的new指令时,初始化new指令的目标类;
  3. 当遇到调用静态方法的指令时,初始化该静态方法所在的类;
  4. 当遇到访问静态字段的指令时,初始化该静态字段所在的类;
  5. 子类的初始化会触发父类的初始化;
  6. 如果一个接口定义了default方法,那么直接实现或者间接实现该接口的类的初始化,会触发该接口的初始化;
  7. 使用反射API对某个类进行反射调用时,初始化这个类;
  8. 当初次调用MethodHandle实例时,初始化该MethodHandle指向的方法所在的类。

5. 绑定本机方法实现

指的是将Java编程语言以为的其他语言编写的功能和实现native方法的功能集成到Java虚拟机中以便可以执行的过程。

传统上来说,此过程可称为链接,但Java虚拟机规范中指出,使用绑定是为了避免于Java虚拟机对类和接口的链接产生混淆。

6. Java虚拟机退出

当调用Runtime.exit()Runtime.halt()System.exit,并且SecurityManager安全管理其允许exit或halt时候,Java虚拟机就会被关闭。

同时,JNI(Java Native Interface)规范描述了对于JNI调用相关的java虚拟机的终止信息。

参考文档

https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html
https://time.geekbang.org/column/article/11523

HashMap源码实现解析

1
2
3
java version "1.8.0_251"
Java(TM) SE Runtime Environment (build 1.8.0_251-b08)
Java HotSpot(TM) 64-Bit Server VM (build 25.251-b08, mixed mode)

基于数组+链表实现,通过&与运算,计算数组下标。在JDK8中,加入红黑树实现,使其时间复杂度保持在O(1)到O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

HashMap 静态内部类Node,实现链表,通过Node[]这个数组属性存放所有的节点。

put(K,V)

应该直接看final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)这个方法更为实际

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

如果当前想要存放的这个节点的hash值暂时没有存在的节点,则直接在数组中添加。

1
2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);

通过&与运算,

如果当前节点的hash值存在了,则在这个节点下增加链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}

从JDK8 开始,当链表中的子节点超过八个时,将转为红黑树。关于红黑树的数据结构特点,我现在也不是特别的理解,先给自己挖个坑,改天填。

红黑树

HashMap扩容

HashMap中有一个属性:threshold ,这个主要是根据阀值和当前HashMap的大小计算而来,可通过查看

1
2
3
4
5
6
7
8
9
10
11
12
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

在初始化HashMap的最后,会根据当前的阀值和实际的大小进行计算threshold的值,同时在每一次操作元素的时候,都会去比较当前HashMap的实际大小与threshold的值,如果当前实际大小已经大于了这个限定的阀值,此时将会对HashMap进行扩容。

resize()方法主要是两个步骤:

  1. 计算大小;
  2. 将原HashMap中的元素进行移动

挖坑,以后填

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

get(Object key)

get方法就更好理解了,首先还是通过hash值找到数组下标,然后通过数组下标获取的实际的元素。然后判断一下当前节点key的hash值是否与第一个节点相同,相同则直接返回结果。

如果不同,这个时候,就得看第一个节点后的下一个节点是采用的红黑树还是使用的链表。然后再根据key的hash去取值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

ArrayList源码解析

1
2
3
java version "1.8.0_251"
Java(TM) SE Runtime Environment (build 1.8.0_251-b08)
Java HotSpot(TM) 64-Bit Server VM (build 25.251-b08, mixed mode)

基于数组实现

1
transient Object[] elementData;

add(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

size是当前数组实际使用的大小,如果当前所需要的数组地址已经大于了当前数组的容量,则对数组进行扩容操作,即调用grow方法。

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

得到所需要扩容的大小以后,调用navite方法对集合进行扩容。
扩容结束以后,将size(代表着实际占用的变量)进行自增,同时将这个数组下标进行赋值。

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

remove方法实际上就是遍历数组所有的元素,然后找到数组下标,再根据数组下标进行删除

1
2
3
4
5
6
7
8
9
10
11
12
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}

定位到具体需要删除的数组下标以后,将下标后的数据往前移动,并将最后一个元素设为null,便于GC回收内存。

迭代器

私有内部类,通过“游标”去操作数组

为什么不能在循环里面增加或删除元素

foreach

foreach本质上就是迭代器的实现,但在删除的时候,使用的是集合的remove方法,而不是迭代器提供的remove方法,这就导致在迭代器遍历中,有一个校验是否并发修改的方法无法通过验证,抛出异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}

// modCount是ArrayList中的属性值,是集合添加元素、删除元素的次数,expectedModCount是迭代器中的属性值,是预期的修改次数。实际修改值与期望值不同
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

for循环

for循环本质上是使用数组下标遍历数组,通过前文中提到的remove(Object o)方法的实现,可以了解到,实际上是将需要删除的元素后的数组向前移动,并将最后一个元素设为null,便于GC回收。

那么当我们使用for循环操作数组,并对其进行删除操作的时候

1
2
3
4
5
for (int i = 0; i < list.size(); i++){
if(list[i] == 'xxx'){
list.remove(i);
}
}

假设数组中,第X个元素满足条件,并将其进行删除。 此时X后的数据元素全部向前移动,那么第X个元素,已经是移动前X+1,如果此时i++自增,那么你取到的是未移动前的X+2个元素。

所以我们只需要修正一下遍历的数组下标即可解决

1
2
3
4
5
6
for (int i = 0; i < list.size(); i++){
if(list[i] == 'xxx'){
list.remove(i);
i--;
}
}

部分参考: https://blog.csdn.net/wangjun5159/article/details/61415358

0%