首页  思维导图  详情

java基础

2021-01-12 14:29:08   0  举报





AI智能生成

java基础

作者其他创作

大纲/内容

hashMap

JDK 1.7

基于数组+链表

key

key的hash code

hash

异或运算，高位参与运算结果，影响低位的值,hash值更加散列

indexFor确定key的槽位

h&(length-1)

当length为2的次幂，length-1 即低位全是1

h&(length-1) 运算结果为，key的hash值h低位的，取值范围为0000 0000 - 0000 1111，
即是0到length-1，且运算速度比取模快

如果key的hash冲突，在槽位生成链表

头插法，每次冲突的key插入链表的头部

并发hash扩容循环引用

允许key为null

放在数组的第一个位置table[0]

初始化

默认初始化容量 threshold 16

默认加载因子 0.75

put

如果数组为空

inflateTable(int toSize) 初始化数组容量

找到大于等于toSize的2次幂整数

roundUpToPowerOf2

Integer.highestOneBit((num-1)<<1),左移一位翻倍，
然后找小于该数字的最大2的次幂

Integer.highestOneBit()

把最高位的1后面的位数变为1，i - (i >>> 1)，
将最高位1后面的位数都变成0

hash冲突，遍历链表，是否有相同key的元素

遍历，有相等，覆盖相同key的值，返回旧值

没有相同的值，遍历结束，插入到链表中

此时，因为遍历了所有节点，头插法和尾插法效率一致

扩容

size超过阈值（数组长度*加载因子），且table上的槽位不为空才会扩容

resize(2*老数组的容量)

new 一个新的2倍长度的数组

如果新数组长度大于Integer.max ，则长度为Integer.max

双重循环，遍历数组以及数组上面的链表

每个元素重新indexFor计算槽位

数组长度翻倍，h&(length-1)，变化的是length-1二进制高位的第一个1对应的位，可能是0，可能是1

1.槽位不变

2.新槽位 = 原槽位+old数组的大小

头插法

扩容后链表的顺序与扩容前相反

循环链表

a -> b -> c

线程1 同时执行完，顺序为c -> b -> a

线程 2 执行到 e = a; next =b;时 cpu切换

下一次循环e = b; next = a

此时 a -> b -> a

线程2 赋值table

当get时，循环链表的时候，死循环

目的：减少hash冲突，即减少链表的长度

modCount修改次数

put和remove会改变modCount的值

当在iterator循环时,赋值expectdModCount = modCount，interator.next() -> nextEntry()会比较expectdModCount 、 modCount，
如果不相等则抛出并发修改异常

在循环的时候hashMap的remove时，而不是interator.remove 会抛异常

JDK 1.8

红黑树

红黑树原则

1.每个结点要么是红的，要么是黑的。

2.根结点是黑的。

3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。

4.如果一个结点是红的，那么它的俩个儿子都是黑的。

5.对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

6.新节点是红色的

插入新节点的逻辑

1.父亲节点是黑色的

不用改变

2.父节点是红色的

a.叔叔节点是空的，旋转+变色

b.叔叔节点是红色，父节点+叔叔节点变黑色，祖父节点变红色

c.叔叔是黑色的，旋转+变色旋转后节点变更

二叉树的扩展

父节点大于等于左孩子节点小于右孩子节点

链表转红黑树

如果hashmap数组的长度小于64，则不转红黑树，先扩容

红黑树key的大小比较

hashcode()

compareto()

comparableClassFor

compareComparables

getClass().getName()

System.identityHashCode()

链表的插入

节点插入到链表1.8使用尾插法

HashMap的扩容机制为什么是2的幂次？

ConCurrentHashMap

JDK1.7

分段锁+unsafe中的cas操作

结构

Segment[]

默认16个Segment

Entry[]

最小容量为2

大小也是2的幂次方

Segment 也是2的幂次方大小

大于并发数的最小2的幂次方

Segment继承ReentrantLock

key不能为空

扩容

扩容Segment中的Entry，entry扩容之后更新Segment中的table

只和当前Segment的对象有关

resize属于Segment的方法

双倍扩容

线程安全，扩容时对当前Segment加锁

初始化

s0对象放到Segment的第一个槽位

Segment中Entry对象属性固定，其他槽位new Segment时参照原型s0初始化Entry的数组大小

put

hashcode & segment.length-1
hashcode & entry.length-1

槽位的Segment为空

while + cas 赋值Segment槽位的值

容量，加载因子等取s0的属性

加锁，tryLock,scanAndLockForPut

tryLock没有获取到锁的时候，重试几次遍历链表如果没找到new Entry操作或者key相等时赋值e，超过重试次数lock()阻塞

cpu核心超过1，重试64次，核心数为1，重试1次

偶数次数的时候检查链表有没有更新，如果更新重置重试次数，重新循环遍历

获取到锁，头插法，插入链表中

size()

先不加锁，如果循环的修改次数和上一次记录的循环次数相等，直接返回计算的长度，
如果中间一直有被修改，超过重试循环次数后会对每个Segment的加锁，然后计数，然后循环解锁

JDK1.8

Node[] 数组

put()

1.如果定位到的Node为空自旋CAS赋值操作

2.Node的hash值为-1，代表线程在扩容

帮助一起扩容

3.Node,不为空，代表hash冲突了，链表或者红黑树，并发时对单个Node加锁synchronized

hash>=0 链表

其他按类型 instance of TreeBin，即hashmap存放的TreeBin对象，并对该对象加锁

对象里面持有root节点

hashMap中红黑树插入旋转可能会导致root节点变化，对Node加锁，会导致hashmap数组槽位不安全

initTable

volilate sizeCtl控制，while+cas只允许一个线程更新成功初始化table

其他线程更新失败while再次读取sizeCtl时，释放cpu资源，Thread.yield()防止死循环cpu 100%飙高

类加载

双亲委派

JDBC为什么破坏双亲委派机制

JDBC的核心DriverManager在rt.jar中由启动类加载器加载，而其实现则在各厂商实现的的jar包中
根据类加载机制，若A类调用B类，则B类由A类的加载器加载，也就是说启动类加载器要加载jar包下的类，
我们都知道这是不可能的，启动类加载器负责加载$JAVA_HOME中jre/lib/rt.jar里所有的class，那么JDBC是如何加载这些Driver实现类的？

通过Thread.currentThread().getContextClassLoader()得到线程上下文加载器来加载Driver实现类

父ClassLoader可以使用当前线程Thread.current.currentThread().getContextClassLoader()所指定的classLoader加载的类。
这就改变了父ClassLoader不能使用子ClassLoader加载的类的情况，即改变了双亲委托模型

加载驱动的两种方式
在加载某一 Driver 类时，它应该创建自己的实例并向 DriverManager 注册该实例

Driver driver = new Driver();//com.mysql.jdbc.Driver
DriverManager.registerDriver(driver);

手动注册，内部也执行静态代码块，这相当于实例化了两个Driver对象

会产生对某一种数据库的依赖（会import驱动包），耦合性较高

Class.forName("com.mysql.jdbc.Driver");

当执行 Class.forName(driverClass) 获取其Class对象时， com.mysql.jdbc.Driver 就会被JVM加载，
连接，并进行初始化，初始化就会执行静态代码块java.sql.DriverManager.registerDriver(new Driver());

Mysql的spi加载机制，通过获取当前线程的类加载器加载了SPI配置的驱动，
com.mysql.jdbc.Driver被初始化，注册驱动

tomcat类加载器为什么要破坏双亲委派机制？

tomcat是web容器，需要解决的问题

1.一个web容器可能要部署两个或者多个应用程序，不同的应用程序，可能会依赖同一个第三方类库的不同版本，
因此要保证每一个应用程序的类库都是独立、相互隔离的。

2. 部署在同一个web容器中的相同类库的相同版本可以共享，否则，会有重复的类库被加载进JVM

3. web容器也有自己的类库，不能和应用程序的类库混淆，需要相互隔离

4. web容器支持jsp文件修改后不用重启，jsp文件也是要编译成.class文件的，支持HotSwap功能

如果使用双亲委派的问题？

1. 默认的类加载器无法加载两个相同类库的不同版本，它只在乎类的全限定类名，
并且只有一份，所以无法解决上面1和3，相互隔离的问题

2. 修改jsp文件后，因为类名一样，默认的类加载器不会重新加载，而是使用方法区中已经存在的类；
所以需要每个jsp对应一个唯一的类加载器，当修改jsp的时候，直接卸载唯一的类加载器，然后重新创建类加载器，并加载jsp文件

tomcat的类加载器

CommonClassLoader

tomcat最基本的类加载器，加载路径中的class可以被tomcat和各个webapp访问

CatalinaClassLoader

tomcat私有的类加载器，webapp不能访问其加载路径下的class，即对webapp不可见

SharedClassLoader

各个webapp共享的类加载器，对tomcat不可见

WebappClassLoader

webapp私有的类加载器，只对当前webapp可见

JspClassLoader

每个jsp一个类加载器

每一个web应用程序对应一个WebappClassLoader，每一个jsp文件对应一个JspClassLoader，所以这两个类加载器有多个实例

工作原理

a. CommonClassLoader能加载的类都可以被Catalina ClassLoader和SharedClassLoader使用，从而实现了公有类库的共用

b. CatalinaClassLoader和Shared ClassLoader自己能加载的类则与对方相互隔离

c. WebAppClassLoader可以使用SharedClassLoader加载到的类，
但各个WebAppClassLoader实例之间相互隔离，多个WebAppClassLoader是同级关系

d. 而JasperLoader的加载范围仅仅是这个JSP文件所编译出来的那一个.Class文件，它出现的目的就是为了被丢弃：
当Web容器检测到JSP文件被修改时，会替换掉目前的JasperLoader的实例，并通过再建立一个新的Jsp类加载器来实现JSP文件的HotSwap功能

tomcat目录结构

/common/*
/server/*
/shared/*
/WEB-INF/*

默认情况下，conf目录下的catalina.properties文件，没有指定server.loader以及shared.loader，所以tomcat没有建立CatalinaClassLoader和SharedClassLoader的实例，这两个都会使用CommonClassLoader来代替。Tomcat6之后，把common、shared、server目录合成了一个lib目录。所以在我们的服务器里看不到common、shared、server目录

每个webappClassLoader加载自己目录下的class文件
每个jasper类加载器加载一个jsp文件

加载过程

1.先在本地缓存中查找是否已经加载过该类(对于一些已经加载了的类，
会被缓存在resourceEntries这个数据结构中)，如果已经加载即返回，否则继续下一步。

2.让系统类加载器(AppClassLoader)尝试加载该类，主要是为了防止一些基础类会被web中的类覆盖，
如果加载到即返回，返回继续。

3.前两步均没加载到目标类，那么web应用的类加载器将自行加载，如果加载到则返回，否则继续下一步。

4.最后还是加载不到的话，则委托父类加载器(Common ClassLoader)去加载。

双亲委派模型过程

分类

启动（Bootstrap）类加载器

负责将 Java_Home/lib下面的类库加载到内存中（比如rt.jar）

标准扩展（Extension）类加载器

负责将Java_Home /lib/ext或者由系统变量 java.ext.dir指定位置中的类库加载到内存中