2023年3月

CSS概念

css的使用是让网页具有统一美观的页面,css层叠样式表,简称样式表,文件后缀名.css

css的规则由两部分构成:选择器以及一条或者多条声明

选择器:通常是需要改变的HTML元素

声明:由一个属性和一个值组成,每个属性有一个值,属性和值使用类似key:value的形式(如下方h1就是选择器,color就是属性,
rebeccapurple
就是值,属性和值成为一条声明)

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>h1{color:rebeccapurple;font-size:10px;
        }
    </style>
</head>
<body>
    <h1>Welcome CSS</h1>
</body>
</html>

CSS的引入

行内样式:在需要改变的标签内使用style属性,让style属性包含任何css的属性

注:缺点是缺乏整体统一性,不利于维护

 <h1style="background-color: blueviolet; font-size: 20px;">Welcome CSS</h1>

内部样式,在单个文档需要的特殊样式,如上方css概念中的例子,在文档头部使用style标签增加样式

注:可以让单个页面css代码具有统一性,但多个页面容易混乱

外部样式:当样式应用于多个页面,外部样式在每个需要使用的页面通过link标签链接到样式表。link标签在文档头部

建立一个
public.css
文件,写外部样式

p{
color: aquamarine;
font-size: 20px;
}
<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <linkrel="stylesheet"href="./public.css">
</head>
<body>
    <p>产品</p>
</body>
</html>

选择器

全局选择器:优先级最低,一般做初始化样式

*{
color: blue;
}

用通配符 *

元素选择器:选择页面所有相同类型标签,用于描述这些类型的共性,无论这个标签藏的多深都能被选择上

HTML文档中的p、div、img等等标签

p{
color: blue;
}

类选择器:用圆点.来定义,针对相同类的标签,类名不能用数字开头,同一个标签可以使用多个类选择器,用空格隔开

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>.classone{color:red;font-size:30px;
        }.classtwo{background-color:black;height:100px;
        }
    </style>
</head>
<body>
    <h1class="classone classtwo">标题</h1>
</body>
</html>

ID选择器:针对特定id标签来使用,只能使用一次,用#来定义,不能用数字开头

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>#mytext{color:red;
        }
    </style>
</head>
<body>
    <pid="mytext">文本</p>
</body>
</html>

合并选择器:多个标签提取共同样式,减少重复代码

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>#mytext,.mytitle{color:red;
        }.mytitle{background-color:black;
        }
    </style>
</head>
<body>
    <pid="mytext">文本</p>
    <h1class="mytitle">标题</h1>
</body>
</html>

选择器优先级:行内样式 > ID选择器 > 类选择器 > 元素选择器

字体属性

包括颜色、大小、加粗、文字样式

颜色

<pstyle="color: red;">字体颜色</p>
<pstyle="color: #fff000;">字体颜色</p>
<pstyle="color: rgb(0,0,0);">字体颜色</p>
<pstyle="color: rgba(0, 0, 0, 1);">字体颜色</p>

大小

<pstyle="color: red;font-size: 30px;">字体颜色</p>

粗细

数值范围100-900,400是默认值,700等同于
bold

<pstyle="font-weight: bold;">字体颜色</p>
<pstyle="font-weight: bolder;">字体颜色</p>
<pstyle="font-weight: lighter;">字体颜色</p>
<pstyle="font-weight: 900;">字体颜色</p>

文字样式

<pstyle="font-style: normal;">字体颜色</p>
<pstyle="font-style: italic;">字体颜色</p>
<pstyle="font-family: 'Trebuchet MS', 'Lucida Sans Unicode', 'Lucida Grande', 'Lucida Sans', Arial, sans-serif;">字体颜色</p>

背景属性

属性
background-color
背景颜色
background-image
背景图片
background-positio
图片位置
background-repeat
图片填充
background-size
图片大小
background-repeat
属性
repeat 默认值
repeat-x 水平方向平铺
repeat-y 垂直方向平铺
no-repeat 不平铺

background-size
:可以使用数值设置宽度和高度,也可以使用百分比,最常用的是两个值cover(保持图片横纵比将图片覆盖背景最小大小),contain(保持图片横纵比将图片覆盖背景最大大小)

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>.box1,.box2{width:600px;height:600px;
        }.box1{background-image:url(./u=1175012548\,1449685026&fm=253&fmt=auto&app=138&f=JPEG.webp);background-repeat:no-repeat;background-size:cover;
        }.box2{background-color:rebeccapurple;background-position:left top;
        }
    </style>

</head>
<body>
    <divclass="box1">背景1</div>
    <divclass="box2">背景2</div>
</body>
</html>

文本属性

文本对齐方式:居中、靠左、靠右

<h1style="text-align: center;">h1</h1>
<h2style="text-align: left;">h2</h2>
<h3style="text-align: right;">h3</h3>

文本添加下划线、上划线和删除线

<h1style="text-decoration: underline;">h1</h1>
<h2style="text-decoration: overline;">h2</h2>
<h3style="text-decoration: line-through;">h3</h3>

文本大小写

<h1style="text-transform: capitalize;">h1</h1>
<h2style="text-transform: uppercase;">h2</h2>
<h3style="text-transform: lowercase;">h3</h3>

首行文本缩进

<h1style="text-transform: capitalize; text-indent: 100px;">h1</h1>

表格边框、颜色、边框折叠

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>table,td{border:1px solid red;
        }table{border-collapse:collapse<!-- 折叠边框 -->;padding:20px;
        }
    </style>
</head>
<body>
    <table>
        <tr>
            <td>单元格</td>
            <td>单元格</td>
            <td>单元格</td>
        </tr>
        <tr>
            <td>单元格</td>
            <td>单元格</td>
            <td>单元格</td>
        </tr>
        <tr>
            <td>单元格</td>
            <td>单元格</td>
            <td>单元格</td>
        </tr>
    </table>
</body>
</html>

关系选择器

后代选择器:所有所有被A包含的B元素,用空格分开A B{ }

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>ul li{color:#fff000;
        }
    </style>
</head>
<body>
    <ul>
        <li>A</li>
        <li>B</li>
    </ul>
</body>
</html>

子代选择器:只对所有A标签的直接子标签B起作用,A>B{ }

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>div>span{color:#fff000;
        }
    </style>
</head>
<body>
    <div>
        <span>A</span>
        <h1><span>B</span></h1>
        <span>C</span>
    </div>
</body>
</html>

相邻兄弟选择器:选择紧跟A标签后的B元素,选择向下相邻的第一个兄弟元素, A+B{ }

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>span+p{color:#fff000;
        }
    </style>
</head>
<body>
    <div>
        <span>A</span>
        <p>B</p>
        <p>C</p>
    </div>
</body>
</html>

通用兄弟选择器:选择A之后的所有兄弟元素B作用多个,A~B{ }

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>span~p{color:#fff000;
        }
    </style>
</head>
<body>
    <div>
        <span>A</span>
        <p>B</p>
        <p>C</p>
    </div>
</body>
</html>

盒子模型

css的盒子包括外边距(margin),边框(border),内边距(padding),实际内容(content)

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>div{width:100px;height:100px;background-color:yellow;padding:50px 10px;border:5px solid red;margin:80px;
        }
    </style>
</head>
<body>
    <div>content</div>
</body>
</html>

弹性盒子模型

弹性盒子是由弹性容器和弹性子元素组成,弹性容器通过设置display属性值为flex来定义弹性容器,弹性盒子只对弹性子元素生效

通过flex-direction来设置子元素在容器中的位置(默认水平排列)row左对齐;row-reverse翻转右对齐;column纵向排列;column-reverse翻转纵向排列

子元素可以通过flex来分配空间

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>.container{width:500px;height:500px;background-color:black;display:flex;justify-content:center;align-items:center;
        }.box1,.box2,.box3{width:100px;height:100px;
        }.box1{background-color:red;flex:10%;
        }.box2{background-color:yellow;flex:30%;
        }.box3{background-color:blue;flex:60%;
        }
    </style>
</head>
<body>
    <divclass="container">
        <divclass="box1"></div>
        <divclass="box2"></div>
        <divclass="box3"></div>
    </div>
</body>
</html>

浮动

增加一个浮层来放置内容

float的值 值描述
left 向左浮动
right 向右浮动

浮动以后相当于在页面增加一个浮层来放置内容

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>.box1{width:100px;height:100px;background-color:red;float:left;
        }.box2{width:200px;height:200px;background-color:yellow;
        }
    </style>
</head>
<body>
    <divclass="box1"></div>
    <divclass="box2"></div>
</body>
</html>

清除浮动

浮动元素会造成父元素高度塌陷,如下方例子,不设置父元素的高度,浮动就无法把父元素撑起来

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>.box1{width:200px;background-color:red;
        }.box2{width:100px;height:100px;background-color:yellow;float:left;
        }
    </style>
</head>
<body>
    <divclass="box1">
        <divclass="box2"></div>
    </div>
</body>
</html>

解决方案可以设置父元素的高度,也可以通过清除浮动,通过在父标签加overflow:fidden

.box1{
width: 200px;
background-color: red;
overflow: hidden;
clear: both;
}

除了造成父元素塌陷,同样也会影响后续元素,例子如下,我们同样无法看到box3,因为被浮动的box2遮挡

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>.box1{width:200px;background-color:red;overflow:hidden;clear:both;
        }.box2{width:100px;height:100px;background-color:yellow;float:left;
        }.box3{width:100px;height:100px;background-color:black;
        }
    </style>
</head>
<body>
    <divclass="box1">
        <divclass="box2"></div>
        <divclass="box3"></div>
    </div>
</body>
</html>

解决方法就是,在需要处理的地方加上clear:both

.box3{
width: 100px;
height: 100px;
background-color: black;
clear: both;
}

定位

position的值 值描述
relative 相对定位
absolute 绝对定位
fixed 固定定位

设置后可以通过left、top、right、bottom来调整,每用一个position就会增加一个浮层:

固定定位是不会随着页面移动变动位置的,永远在固定位置

相对定位和绝对定位是根据具有定位的父元素进行定位的,如果父级没有定位就会根据页面来定位

相对定位是不脱离文档流的,绝对定位和固定定位都是脱离文档流的

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>div{width:100px;height:100px;background-color:red;position:relative;left:100px;top:100px;
        }.box1{width:100px;height:100px;background-color:black;position:absolute;left:100px;top:300px;
        }
    </style>
</head>
<body>
    <div></div>
    <divclass="box1"></div>
</body>
</html>

调整位置顺序通过z-index,如下方例子,原本是黑色遮盖红色,如果想调整为红色在上,只需要增加z-index

<!DOCTYPE html>
<htmllang="en">
<head>
    <metacharset="UTF-8">
    <metahttp-equiv="X-UA-Compatible"content="IE=edge">
    <metaname="viewport"content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>div{width:100px;height:100px;background-color:red;position:relative;left:100px;top:100px;

        }.box1{width:100px;height:100px;background-color:black;position:absolute;left:100px;top:100px;
        }
    </style>
</head>
<body>
    <div></div>
    <divclass="box1"></div>
</body>
</html>

z-index大的值在上方

div{
width: 100px;
height: 100px;
background-color: red;
position: relative;
left: 100px;
top: 100px;
z-index: 2;

}
.box1{
width: 100px;
height: 100px;
background-color: black;
position: absolute;
left: 100px;
top: 100px;
z-index: 1;
}

项目地址

https://gitee.com/Kindear/lucy-chat

介绍

lucy-chat
是接入
OpenAI-ChatGPT
大模型人工智能的
Java
解决方案,大模型人工智能的发展是不可阻挡的趋势,我们环境无法创造工具,但是也要更好的使用工具,该包简化了接入流程,可以非常方便的引入并使用
ChatGPT
相关功能。

接入方式

lucy-chat
提供了两种形式接入服务,完成集成或者独立部署后可以访问
[部署地址]/doc.html
调用相关接口。

1. Jar引入

准备

在引入任何
Lucy
系列依赖之前,需要完成
jitpack
镜像仓库的配置。

<repositories>
        <repository>
            <id>jitpack.io</id>
            <url>https://www.jitpack.io</url>
        </repository>
</repositories>

引入

根据版本号引入

当前默认
1.0.0-r4

		<dependency>
			<groupId>com.gitee.kindear</groupId>
			<artifactId>lucy-chat</artifactId>
			<version>${version}</version>
		</dependency>

启动类

启用
knife4j
文档,需要在启动类上配置
@EnableKnife4j

@EnableKnife4j
@SpringBootApplication
public class DemoApplication {

    public static void main(String[] args) {

        SpringApplication.run(LucyAdminApplication.class, args);
    }

}

配置文件

使用
lucy-chat
需要配置如下文件信息

spring.application.name=lucy-chat
# 运行端口
server.port=8080
# swagger 匹配
spring.mvc.pathmatch.matching-strategy=ant_path_matcher

# chat-gpt api-key
# 申请地址 https://platform.openai.com/account/api-keys
openai.chat.key=

# chat-gpt proxy host
# 配置代理地址 请参阅 https://www.v2ex.com/t/921689
openai.chat.host=

# 连接池最大连接数
forest.max-connections=1000
# 连接超时时间,单位为毫秒
forest.connect-timeout=30000
# 数据读取超时时间,单位为毫秒
forest.read-timeout=30000


2. 独立服务

  1. 从开源地址下载项目
git clone https://gitee.com/Kindear/lucy-chat
  1. 修改
    POM
    文件中打包方式,即恢复
    <build>
    相关注释掉的内容
<build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.8.1</version>
                <configuration>
                    <source>1.8</source>
                    <target>1.8</target>
                    <encoding>UTF-8</encoding>
                </configuration>

            </plugin>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <version>${spring-boot.version}</version>
                <executions>
                    <execution>
                        <goals>
                            <goal>repackage</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>
  1. 修改相关配置文件, 参考上文的配置文件相关内容,项目中提供的
    key
    为私人
    key
    ,随时会被替换。
  2. 打包项目并部署

效果

1. 对话

2. 图像绘制

3. 文本编辑

使用signalr实现APP扫码登录

1. 背景介绍

在移动化时代,web开发很多时候都会带着移动端开发,这个时候为了减少重复输入账号密码以及安全性,很多APP端都会提供一个扫码登录功能,web端生成二维码,APP扫码直接登录web端,无需再次输入账号密码。

2. 实现流程图

在这里插入图片描述

3. 代码运行环境

  • ASP.NET CORE 7.0

  • VS2022

    本案例为了操作方便,并没有操作db,直接硬编码了一个账号:admin 密码:123456 来模拟用户登录流程,正式环境可以用jwt来做认证,我这里自己简单实现了一个认证方式可供参考。

    项目启动后,使用浏览器打开http://localhost:5196/app.html和http://localhost:5196/web.html分别来模拟app和web的登录,先在APP端输入账号密码登录,然后到web端生成二维码,复制到APP端扫码就可以看到扫码登录效果啦~

4. 总结

市面上也有很多扫码登录是通过轮询的方式来实现,也就客户端定时发送请求来查询二维码标识符的扫描状态,感觉会有一定影响,SignalR的功能当然不是止步于此啦,这里只是一个简单案例,如果有帮助的话,可以来个star哦,谢谢
,如果有帮助的话,可以来个star哦,谢谢!
开源地址:
SignalR实现APP扫描登录

时间复杂度和空间复杂度


1、概述

​ 算法就是解决一个问题的方法,同一个问题使用不同的算法得到相同的结果,但是所消耗的资源是不等的,这就意味着我们需要从众多的算法中选出最优的那个算法。这个时候我们就不得不考虑这个算法的效率,而如何去评判或者判断一个算法的好坏,一个算法的效率如何,那就需要用到这两个指标:时间复杂性(消耗的时间)和空间复杂性(消耗的内存)。

2、时间复杂度


定义
:时间复杂度(Time complexity),个算法语句总的执行次数是关于问题规模N的某个函数,它定性描述该算法的运行时间。时间复杂度常用大O符号表示


统计方式:
我们知道了什么是时间复杂度,那么我们怎么去计算呢?当然也有两种方式:一种是事后统计,算法写好之后统计算法的运行时间,当然如果一个算法很劣质,那么我们可能就需要推倒重来;另外一种就是事前分析,即在算法编写之前我们先分析其执行的时间复杂度,从而判断算法优劣


复杂度的计算:
算法的运行时长我们可以理解为所有简单语句和每个简单语句运行的时长。赋值、比较、移动、判断、打印、一次数据库的操作等等我们都可以理解成是一个简单语句,从而:
时间复杂度 = 简单操作的次数 * 一个简单操作的时间
。一般一个简单语句的运行时长跟我们的计算机的硬件性能有关,但是硬件性能却与我们的算法质量无关,所以我们把每次简单语句的执行时间相同都是单位1,那么我们的时间复杂度就只与我们简单操作的次数相关。


例:
有这样一个需求,给出10个数字,6,8,3,2,16,7,9,13,4,17。得知其中两个数字之和得26,找出这两个数据分别是几?

public class Test {
		// 定义所有数字的数组
    Integer[] arr = {6,8,3,2,16,7,9,13,4,17};
    // 定义两数之和
    Integer sum = 26;
    
    @org.junit.jupiter.api.Test
    public void algoOne(){
    		// 第一个for循环得到第一个加数
        for (int i = 0; i < arr.length; i++) {
        		// 第二个for循环得到第二个加数,注意为了避免6+8 8+6这种重复,所以我们第二个加数直接把之前用过的数字去掉,节省一定循环次数
            for (int j = 0; j < arr.length; j++) {
            		// 拿着两个加数相加看得到的是否等于最终结果
                if ((arr[i] + arr[j]) == sum){
                    System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],arr[j],sum));
                    return;
                }
            }
        }
    }
}


分析:
我们最终要执行的就是里面的一个判断,在这个里面我们总共执行了多少次呢?外面循环是10次,里面一个循环每次也执行10次,如果按照最差结果,那么要执行10的2次方一百次。如果我们有100个数,那么就是100的2次方就是一万次,如果再往上增加恐怕这个数值的恐怖程度会超出我们的想想吧,如此来说这个算法的时间复杂度是与数组长度有关系的假设我们数组长度是N,那么我们的计算次数就是N的2次方,事件复杂度与执行次数成正比,那么时间复杂度记为:O(n^2)


降低时间复杂度:
我们感觉上面那种方式时间复杂度太高了,那么有什么办法降低呢,看下面这种方式

    @org.junit.jupiter.api.Test
    public void algoTwo(){
    		// 定义一个map存放能够得到目标数值的两个加数,key是当前值为了能得到最终值所需要的另一个加数,value就是我们当前值
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
        		// 判断这个当前数值是否是之前数所需要的数值
            if (map.containsKey(arr[i])){
                System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],sum - arr[i],sum));
                return;
            }
            Integer second = sum - arr[i];
            map.put(second,arr[i]);
        }
    }


分析:
经过这次改造,看我们还需要执行多少次呢?原来需要两个循环,现在我们需要一个循环,那么需要执行N次能得到最终的结果。那么我们的时间复杂度为:O(n)

​ 如果我们的一个算法,从头到位顺序执行不存在循环等条件,每行语句都执行一次或者固定次数,那么我们的时间复杂度就是O(1),那么我们总结一下,什么是时间复杂度,就是我们算法执行需要的时间,而怎么计算这个需要考虑我们算法中各个影响因素,以最重要因素为主去算我们的最终复杂度

3、空间复杂度


定义
:空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))

​ 一个算法运行时所占用的空间一般分两部分,一个是固定的,指代码部分,就是我们的代码的多少,定义常量的,简单变量的多少;另一部分就是在我们代码运行中所产生的临时变量所占用的空间,这部分空间是不确定的,而我们所说的空间复杂度说的就是这部分空间的的占用情况


例:
我们延用上面的两个案例来分析一下他们的空间复杂度


case1

public class Test {
		// 定义所有数字的数组
    Integer[] arr = {6,8,3,2,16,7,9,13,4,17};
    // 定义两数之和
    Integer sum = 26;
    
    @org.junit.jupiter.api.Test
    public void algoOne(){
    		// 第一个for循环得到第一个加数
        for (int i = 0; i < arr.length; i++) {
        		// 第二个for循环得到第二个加数,注意为了避免6+8 8+6这种重复,所以我们第二个加数直接把之前用过的数字去掉,节省一定循环次数
            for (int j = 0; j < arr.length; j++) {
            		// 拿着两个加数相加看得到的是否等于最终结果
                if ((arr[i] + arr[j]) == sum){
                    System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],arr[j],sum));
                    return;
                }
            }
        }
    }
}


分析:
在这个案例里面在运行时我们没有定义任何变量,所以无论我们的数组元素变成多少,我们所占用的内存空间是固定的,那么我们的空间复杂度就是O(1)


case2:

    @org.junit.jupiter.api.Test
    public void algoTwo(){
    		// 定义一个map存放能够得到目标数值的两个加数,key是当前值为了能得到最终值所需要的另一个加数,value就是我们当前值
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < arr.length; i++) {
        		// 判断这个当前数值是否是之前数所需要的数值
            if (map.containsKey(arr[i])){
                System.out.println(String.format("%s 和 %s 两数之和是:%s", arr[i],sum - arr[i],sum));
                return;
            }
            Integer second = sum - arr[i];
            map.put(second,arr[i]);
        }
    }


分析:
在case2中看到我们定义了一个map来存储数组元素,当我们开始运行时,map创建出来,随着我们数组元素的增多,我们map中所需要的空间也会不断增多,这个时候我们的空间复杂度就变成了:O(n),n就是我们数组的长度

4、空间与时间

​ 我们经常听到的一句话,利用空间换时间,利用时间换空间,其实在这里我们已经能深刻的体会出来了。这句话听着有点鱼与熊掌不可兼得的味道,但是目前来说大部分情况就是这个样子,有失有得,你总要付出一点代价方能得到一些。但是在我们目前的环境中这种选择似乎没有之前那么艰难,最开始的时候受资盘等的限制,一个程序的运行只有几K或者几百K,这个时候究竟是选择时间还是空间就会成为一个纠结的问题,随着计算机的发展,现在的磁盘内存等已经能够得到大部分需求的满足,所以在大部分情况下在选择空间与时间的问题上,选择时间的会偏多一点

不断努力,共同成长

关注公众号不迷路

源码基于jdk1.8
这一片主要讲述ConcurrentHashMap如何实现低粒度锁的插入,如何实现统计元素个数,如何实现并发扩容迁移

系列文章目录和关于我

一丶ConcurrentHashMap概述

  • 支持高并发读写的哈希表,
    ConcurrentHashMap
    中每一个方法都是线程安全的,并且读数据通常不需要加锁,并发的性能远优于
    Hashtable

    //每一个方法都是线程安全,但是复合操作并不一定安全,如下的contains然后put
    ConcurrentHashMap<Object, Object> concurrentHashMap = new ConcurrentHashMap<>();
    if (!concurrentHashMap.contains("1")){
     	concurrentHashMap.put("1","1");
    }
    
  • 虽然ConcurrentHashMap 具备很高的并发读写,但是对于并发的进行putAll 和get,只能反映
    瞬时态

    下面这段代码如果线程A先拿到Hashtable的全局锁,那么线程B一定可以get出值,但是如果把Hashtable换做ConcurrentHashMap即使在时间上putAll先于get,也无法保证一定能get到key1对应值

    Hashtable<Object, Object> hashtable = new Hashtable<>();
    //线程A 执行
    hashtable.putAll(hashMap);
    //线程B 执行
    Object v1 = hashtable.get("key1");
    
  • ConcurrentHastMap的迭代器不会抛出
    ConcurrentModificationException

    但是可以遍历到元素只有创建迭代器时的那部分。

  • ConcurrentHashMap支持自动并发扩容,注意这个扩容是并发的,意味着扩容的期间读写并不会被阻塞

二丶ConcurrentHashMap的结构

ConcurrentHashMap的结构基本上和HashMap类似,都是数组+链表+红黑的方式:

image-20230312140421513

  1. 数组

    是散列表查找效率可以达到o(1)的关键

    根据key的hash对数组大小取模得到下标index,然后根据下标快速定位到桶,利用了数组寻址快的优点

  2. 链表

    作用是解决hash冲突,
    发生hash冲突的节点就放在对应下标的链表 or 红黑树中

    hash冲突:
    hash然后对数组大小取模的操作可以看作一个函数
    这个函数的输入时无穷的,但是输出是介于0~数组大小的,那么必然存在多个key最后落在同一个下标的情况
    
  3. 红黑树

    解决链表遍历时间复杂度o(n)的问题,使用红黑树利用二分搜索的性质进行优化。

    红黑树本质是平衡二叉搜索树,平衡表示左子树右子树规模尽量接近,左子树小于父节点,父节点大于右子树的特征意味着可以使用log n的时间复杂度进行搜索,这个大小的比较优先使用Comparable类型key的compareTo方法,但是如果key不可比较那么将使用其hash值大小做比较。

在上图中锁的标志可以知道,ConcurrentHashMap锁的粒度,其锁只锁一个数组下标的元素,相比于Hashtable直接锁住整个哈希表,其锁的粒度更小,所以说ConcurrentHashMap具备更高的并发度。

三丶ConcurrentHashMap中的属性和常量

1.常量

这里只分析比较重要的常量,类似于为了兼容之前版本的常量不做列举
名称 含义
MAXIMUM_CAPACITY 1 << 30 数组最大大小
DEFAULT_CAPACITY 16 默认容量大小
LOAD_FACTOR 0.75 负载因子,1.8的负载因子为0.75,假如容量为8,那么当元素个数达到6的时候会发生扩容,扩容到原大小两倍
TREEIFY_THRESHOLD 8 树化阈值,指定桶位 链表长度达到8的话,有可能发生树化操作
UNTREEIFY_THRESHOLD 6 红黑树转化为链表的阈值
MIN_TREEIFY_CAPACITY 64 接合TREEIFY_THRESHOLD控制桶位是否树化, 只有当table数组长度达到64且 某个桶位 中的链表长度达到8,才会真正树化
MIN_TRANSFER_STRIDE 16 线程迁移数据最小步长,控制线程迁移任务最小区间一个值
NCPU 当前系统的cpu核数
RESIZE_STAMP_BITS 16 sizeCtl中用于生成扩容戳的位数(扩容时详细讲解)

2.属性

属性 作用
transient volatile Node<K,V>[] table 散列表,长度一定是2次方数
private transient volatile Node<K,V>[] nextTable 扩容过程中,会将扩容中的新table 赋值给nextTable 保持引用,扩容结束之后,这里会被设置为Null
private transient volatile long baseCount 实现ConcurrentHashMap计数的变量
private transient volatile int sizeCtl ConcurrentHashMap中最复杂的变量,不同语境下具备不同作用,后面使用时介绍
private transient volatile int transferIndex 扩容过程中,记录当前进度。所有线程都需要从transferIndex中分配区间任务,去执行自己的任务。
private transient volatile CounterCell[] counterCells ConcurrentHashMap实现计数的变量

四丶源码分析

1.构造方法

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();

    //如果初始容量大于 最大容量(1 << 30)的一半,那么直接使用最大容量,
    //如果使用 tableSizeFor((初始容量 + 初始容量/2)+1) =  大于(1.5初始容量+1)的2的倍数
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    /**
     * sizeCtl > 0
     * 当目前table未初始化时,sizeCtl表示初始化容量
     */
    this.sizeCtl = cap;
}

这里有趣的是,构造方法并不导致数组的初始化,这点类似HashMap,只有往ConcurrentHashMap中塞元素的才会初始化数组

1.1.tableSizeFor

使用位操作
返回大于等于c的最小的2的次方数

image-20230318113502994

假如c为1297 n就是1296

1296的二进制       0000 0101 0001 0000
右移1位            0000 0010 1000 1000
或操作             0000 0666666 1001 1000
右移2位            0000 0001 6666660 0110
或操作             0000 0666666 6666661 6666661
右移4位            0000 0000 0666666 6666661 
或操作             0000 0666666 6666661 6666661
。。。右移 16位就让32位树最高位及以后的都为1
最后进行+1 求出不小于它的最接近的2的整数幂m

n<0 说明当前数太大了 32位全是1 已经超过了int 最大,数组不可以开辟这么大

2.主线剧情——put方法

2.1带着问题学源码

put方法是看懂ConcurrenHashMap的重点,此方法会被多个线程并发调用,那么douglea 是如何并发问题的昵?

  1. 数组的初始化,如何保证只有一个线程初始化,并且不会重复初始化
  2. 如果插入key对应下标为空,多个线程如何保证不会发生覆盖
  3. 如何实现ConcurrentHashMap元素数量计数
  4. 如何实现并发扩容迁移

2.2 源码解析

线程安全且低粒度锁的插入 -> 热点数据分离的统计ConcurrentHashMap元素个数 -> 并发扩容迁移

image-20230318120929743

put方法直接调用了putVal,其中第三个参数表示只有在存在相同key的时候才插入,这里为false说明覆盖(之前存在key=1,value=2,这时候插入key=1,value=3.那么会覆盖为3)。下面我们大致看下putVal方法的流程

image-20230318122612983

2.2.1 spread让散列更均匀

image-20230318123350702

下面我们分析为什么需要使用高16位进行异或操作,为什么这种操作可以让key散列到数组中更均匀(这里和HASH_BITS进行且操作的目的是让hash值恒定为一个正数,因为再ConcurrentHashMap中负数hash值具备特殊意义,HashMap中则没有这个特殊处理)

  1. key是散列到指定数组下标的

    image-20230318143559036

    这里很巧妙的利用了数组长度是2的倍数的特点,2的倍数-1意味着低位连续x个1,对其进行且操作就是只保留原hash值的低x位等于取模

  2. 为什么需要使用高16位进行异或操作,为什么这种操作可以让key散列到数组中更均匀

    假设插入key的hash满足一个规律 hash = 6000整数倍+3,且数组的长度为8


    hash 对应二进制 且上(数组长度-1 = 7 =0666666)
    6003 0001066666606666660 011 011 = 3
    60003 6666660101001100 011 011 = 3
    600003 10010010066666611000 011 011 = 3
    6000003 010110666666000110110000 011 011 = 3

    可以看到最终这些key都将落在数组下标3中,这是为什么昵?

    因为上面的i * 60000对8取余肯定是0 剩下的结果只能是3对8取余 导致结果一直是3
    因为hash 高位的值没有参与计算
    

    如果使用高16位进行异或,得到数字的低位16位包含了原高16位的特征,从而让高位也参与计算,让散列更均匀


    hash 对应二进制 hash ^ (hash>>>16) 且上(数组长度-1 = 7 =0666666)
    6003 0001066666606666660 011 0001066666606666660 011 011 = 3
    60003 6666660101001100 011 6666660101001100 011 011 = 3
    600003 10010010066666611000 011 011000000000000000000010 010 = 2
    6000003 010110666666000110110000 011 010110666666000110666666011000 000 = 0

    可以看到
    600003,6000003
    被散列到2和0,避免了这一类数据都散列到下标3导致hash冲突剧烈的问题。

  3. 上述高16位异或的做法有什么缺点和优点


    • 缺点

      根据上面表格的例子可以看到
      6003,60003
      由于这些数字二进制高16位全为0,所以最终还是都散列到3,并没有被很好的离散开。

      可以学习redis 使用Crc16对key进行散列,可以让散列更均匀

    • 优点

      时间复杂度低,如果使用md5,或者Crc16等算法进行散列,其时间成本将更大。

2.2.2 如果数组没有初始化,如何保证只有一个线程初始化成功,并不发生覆盖

这种情况发生在ConcurrentHashMap第一次塞元素的情况,会调用initTable对数组进行初始化,和HashMap不同点在于,这个initTable存在多个线程并发调用的可能,下面我们看看doug lea如何保证这一步的线程安全,和线程可见性(线程A初始化了数组,线程B必须马上可见)

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //自选,只要数组没有初始化
    while ((tab = table) == null || tab.length == 0) {
		//sizeCtl<0 说明其他线程正在初始化数组
        if ((sc = sizeCtl) < 0)
            //当前线程只需要放弃cpu 静静等待
            Thread.yield(); // lost initialization race; just spin
        
        //cas设置sizeCtl 为-1 cas成功表示当前线程成功上锁,由当前线程进行初始化table
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                //再次检查,避免其他线程初始化了,当前线程还进行初始化导致前面线程put的元素丢失
                //因为下面finally 会释放锁,释放的一瞬间可能其他线程成功cas为-1,从而让前面初始化线程put的内容丢失
                if ((tab = table) == null || tab.length == 0) {
                    //sc 大于0 这是用户在构造方法中设置的大小,如果用户没有设置那么使用默认大小
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    //new 一个数组 并且赋值给table
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    
                    //n为当前数组的大小
                    //n - (1/4*n) = 3/4 n 也就是负载因子0.75 * n 
                    sc = n - (n >>> 2);
                }
            } finally {
                //释放锁
                sizeCtl = sc;
            }
            //结束自旋
            break;
        }
    }
    //返回初始化后的数组
    return tab;
}

总体上是利用sizeCtl做了一把锁,如果没有抢占到锁,那么让出cpu,这里没有使用
synchronized
的原因应该是:初始化一个数组是一个很快的过程,如果把其他线程挂起,初始化完后还需要进行唤醒,挂起和唤醒需要从用户态切换到内核态,为了一个短暂的初始化而进行挂起和唤醒是得不偿失的。

并且table属性是volatile修饰的属性,保证了可见性

代码中还有一点非常有趣

image-20230318151939551

2.2.3 如果插入位置不存在元素,如何保证并发情况下不会发生覆盖

image-20230318152911790

可以看到doug lea使用cas的方式保证了
多个线程插入元素到先前不具备元素的桶中,只有一个线程会成功,成功的线程将结束自旋,失败的线程将继续自旋

这里还有一个细节,那就是如何保证获取数组元素的线程可见性,table数组虽然被volatile修饰,但是table中元素怎么保证可见性:

image-20230318153232024

可以看到,获取table元素的方式是
Unsafe.getObjectVolatile(数组元素的地址)
的方式,这种方式会
在读指令前插入读屏障,可以让高速缓存中的数据失效,重新从主内存加载数据

2.2.4 如果发生hash冲突,如何保证线程安全的将当前插入数据追加到链表或者红黑树中
这里先暂时忽略helpTransfer 帮助扩容迁移的内容,后面讲到扩容我们再看看doug lea如何实现帮助扩容迁移的

image-20230318154433693

final V putVal(K key, V value, boolean onlyIfAbsent) {
    //不可存null key 和null value
    if (key == null || value == null) throw new NullPointerException();
    // 对key的hash进行扰动,是高16位参与计算,让散列更均匀
    int hash = spread(key.hashCode());
    //如果插入到链表中的那么记录链表中的下标,
    //如果插入到红黑树那么恒定为2,
    //如果没有发生hash冲突(没有插入到链表也没插入到树)那么为0
    int binCount = 0;   
    //自旋
    for (Node<K,V>[] tab = table;;) {
        //忽略无关代码。。。
        else {
            //进入这个位置的前提
            //1.数组初始化了
            //2.当前key hash对数组取模得到下标后,根据下标到数组中拿到对应的节点不是空(不是第一个插入在这个位置的元素)
            //3 数组在当前插入位置没有进行扩容迁移
            
            //旧值
            V oldVal = null;
            //加锁 锁的是头节点(可能是链表,也可能是树节点,等其他节点)
            synchronized (f) {
                // 重新获取以下,避免其他线程修改了头节点,从而锁错,如果其他线程修改了头,那么什么也不做,继续自选
                if (tabAt(tab, i) == f) {
                    
                    //当前key hash对数组取模得到下标后,根据下标到数组中拿到对应的节点的hash值 大于0,说明是链表节点,因为树节点的hash恒定-2
                    if (fh >= 0) {
                        //记录在链表中的位置
                        binCount = 1;
                        //遍历链表中每一个节点
                        for (Node<K,V> e = f;; ++binCount) {
						 // ek记录当前遍历节点的key
                            K ek;
                            //当前遍历节点kash = 企图插入key的hash
                            //且key是同一个对象 或者key equals为true 说明找到插入的位置
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                //记录旧值
                                oldVal = e.val;
							 //如果不是不存在才插入(put方法onlyIfAbsent=false,会进行值替换)
                                if (!onlyIfAbsent)
                                    //替换值
                                    e.val = value;
                                //插入成功那么结束自选
                                break;
                            }
                            
                            //遍历节点的前一个节点
                            Node<K,V> pred = e;
						 //e是当前遍历的节点,如果当前节点的下一个节点为null 
                            //此处还会让e = e.next 相当于让遍历节点向后移动
                            if ((e = e.next) == null) {
                                //到这儿说明 当前key和链表中每一个节点的key都不同(不能==,也不能equals)
                                //那么将当前插入的值包装成node 挂到链表末尾
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    
                    //当前key hash对数组取模得到下标后,根据下标到数组中拿到对应的节点 是一个树节点
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        //恒定binCount为2
                        binCount = 2;
                        //红黑树的插入 p为插入过程中key ==或者equals的节点,
                        //说明存在重复的节点 p是被覆盖的节点
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            //记录旧值
                            oldVal = p.val;
                           //如果不是不存在才插入(put方法onlyIfAbsent=false,会进行值替换)
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            
            //binCount 如果插入下标对应的第一个节点是空(当前是第一个插入到这个位置的)才为0
            //插入链表中 binCount记录插入到链表中的下标
            //如果插入到红黑中,binCount恒定为2
            if (binCount != 0) {
                //大于树化的阈值,那么进行树化(内部会要求数组长度大于64)
                if (binCount >= TREEIFY_THRESHOLD)
                    //树化
                    treeifyBin(tab, i);
                //如果之前相同key的元素存在,返回旧的key
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    
    //计数,会记录ConcurrentHashMap中的元素个数
    //如果超过扩容阈值 还会进行扩容迁移
    addCount(1L, binCount);
    return null;
}

这部分代码没有很复杂,使用
synchronized
锁住头节点保证线程安全,但是即使加了锁,doug lea居然还会使用
if (tabAt(tab, i) == f)
再次进行校验,这是为什么昵?

image-20230318160017354

2.2.5 如何统计ConcurrentHashMap中元素数量,和实现并发扩容迁移——addCount方法

统计数量和并发扩容都交给putVal最后的addCount方法,如果是覆盖了原有key value或者没有插入到ConcurrentHashMap那么将不进行
addCount(1L, binCount)
,因为没有新增元素。

  • 统计元素个数的难点

    如果addCount被并发调用且只使用一个属性记录元素个数,我们可以使用下列方案统计数量


    • 使用独占锁

      这种方案的缺点,多个线程并发插入最终都将受限于统计数量,这一步只能串行,这和ConcurrentHashMap主打一个并发是相悖的

    • 使用AtomicLong

      这种方案的缺点在于,假如当前有100个线程,线程1cas修改数目成功,将导致线程2~100失败继续自旋,线程2成功将导致其余线程失败自旋,导致线程进行多次无意义的自旋,把珍贵的cpu资源浪费在自旋上。这是
      热点数据更新
      导致的问题


    热点数据分离的方案


    • 使用LongAdder

      ConcurrentHashMap没有直接使用LongAdder,几乎是一样的代码再写了一次,可能doug lea觉得ConcurrentHashMap只需要加1这种操作,不需要所有LongAdder所有功能从而进行了独立实现

      JUC源码学习笔记4——原子类,CAS,Volatile内存屏障,缓存伪共享与UnSafe相关方法 - Cuzzz - 博客园 (cnblogs.com)
      这篇博客详细讲解了LongAdder的原理——热点数据分离

      其实和分表思想类似,将热点数据分散到多出,从而减少热点数据更新的问题。

      这种方案虽好但是有另外一个问题——统计热点数据之和不具备瞬时一致性,想象我们需要遍历完所有热点数据计算其和,可能遍历完A,再遍历B的时候,A被修改了。

      鱼和熊掌不可兼得

  • 并发扩容迁移的难点

    如何让多个线程协调合作,如何让迁移的过程不阻塞读,如何保证多线程迁移的线程安全问题

addCount方法很长,我们分两部分讲解
2.2.5.1 ConcurrentHashMap统计总数

增加CocurrentHashMap元素数量,并统计总数

这部分需要LongAdder的基础,推荐学习《
JUC源码学习笔记4——原子类,CAS,Volatile内存屏障,缓存伪共享与UnSafe相关方法 - Cuzzz - 博客园 (cnblogs.com)

//as 表示 LongAdder.cells
//b 表示LongAdder.base
//s 表示当前map.table中元素的数量
CounterCell[] as; long b, s;
//条件一:(as = counterCells) != null
		//true->表示cells已经初始化了,当前线程应该去使用hash寻址找到合适的cell 去累加数据
        // false->表示当前线程应该将数据累加到 base
//条件二:!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)
		//false->表示写base成功,数据累加到base中了,当前竞争不激烈,不需要创建cells
		//true->表示写base失败,与其他线程在base上发生了竞争,当前线程应该去尝试创建cells。
if ((as = counterCells) != null ||
    !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
    //有几种情况进入到if块中?
    //1.true->表示cells已经初始化了,当前线程应该去使用hash寻址找到合适的cell 去累加数据
    //2.true->表示写base失败,与其他线程在base上发生了竞争,当前线程应该去尝试创建cells。

    //a 表示当前线程hash寻址命中的cell
    CounterCell a;
    //v 表示当前线程写cell时的期望值
    long v;
    //m 表示当前cells数组的长度
    int m;
    //true -> 未竞争  false->发生竞争
    boolean uncontended = true;

    //条件一:as == null || (m = as.length - 1) < 0
    //true-> 表示当前线程是通过 写base竞争失败 然后进入的if块,就需要调用fullAddCount方法去扩容 或者 重试.. LongAdder.longAccumulate
    //条件二:a = as[ThreadLocalRandom.getProbe() & m]) == null   前置条件:cells已经初始化了
    //true->表示当前线程命中的cell表格是个空,需要当前线程进入fullAddCount方法去初始化 cell,放入当前位置.
    //条件三:!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)
    //      false->取反得到false,表示当前线程使用cas方式更新当前命中的cell成功
    //      true->取反得到true,表示当前线程使用cas方式更新当前命中的cell失败,需要进入fullAddCount进行重试 或者 扩容 cells。
    if (as == null || (m = as.length - 1) < 0 ||
        (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
        !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
    ) {
        //这里面涉及到Cell数组的扩容,自旋计数
        //和LongAdder代码一模一样
        fullAddCount(x, uncontended);
        return;
    }
     
        //只有put插入的时候,key对应table位置的元素为空,且cas成功 这时候check为0
        //或者删除的时候 check为-1
        //也就是说是这个桶中第一次插入,没有发生hash冲突,doug lea 认为这种情况说明桶中元素并不多
        //或者说是删除操作,删除自然不需要进行扩容
        //所以直接返回 不会进行扩容
        if (check <= 1)
            return;
        
        //记录当前ConcurrentHashMap中有多少个元素 这个过程会遍历Cell数组
       //因此不具备瞬时一致性
        s = sumCount();
}

....下面为并发扩容迁移
2.2.5.2 addCount调度线程发起扩容或者加入扩容

扩容过程中需要记录当前扩容批次,比如从数组长度16扩容到数组长度32会为扩容生成一个唯一标识

image-20230319142321045

并且还会记录有多少个线程在进行扩容,这两部分信息用sizeCtl一并记录

image-20230319143036244

高16位表示:扩容的标识戳(方法resizeStamp(当前数据大小)生成)
低16位表示:(1 + 参与扩容的线程数)
可以看到resizeStamp生成批次或上(扩容线程数+1)一定是负数==>sizeCtl如果是负数表示当前正在进行扩容
//s 是上面统计Cell数组得到的ConcurrentHashMap元素个数

//删除情况调用addCount的时候check是负数,这里标识是compute 或者put方法新增了元素
if (check >= 0) {
    //tab 表示map.table
    //nt 表示map.nextTable
    //n 表示map.table数组的长度
    //sc 表示sizeCtl的临时值
    Node<K,V>[] tab, nt; int n, sc;

    //自旋
    //条件一:s >= (long)(sc = sizeCtl)
    //       true-> 1.当前sizeCtl为一个负数 表示正在扩容中..
    //              2.当前sizeCtl是一个正数,表示扩容阈值
    //       false-> 表示当前table尚未达到扩容条件
    //条件二:(tab = table) != null
    //       恒成立 true
    //条件三:(n = tab.length) < MAXIMUM_CAPACITY
    //       true->当前table长度小于最大值限制,则可以进行扩容。
    while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
           (n = tab.length) < MAXIMUM_CAPACITY) {

        //扩容批次唯一标识戳,使用位操作生成,扩容唯一标识
        //16 -> 32 扩容 标识为:1000 0000 0001 1011
        int rs = resizeStamp(n);

        //条件成立:表示当前table正在扩容
        //         当前线程理论上应该协助table完成扩容
        if (sc < 0) {
            //条件一:(sc >>> RESIZE_STAMP_SHIFT) != rs
            //      true->说明当前线程获取到的扩容唯一标识戳 非 本批次扩容
            		//可能当前线程长时间没有获得时间片,以至于其他线程都扩容结束,进行下一轮扩容了
            		//当前线程才姗姗来迟
            //      false->说明当前线程获取到的扩容唯一标识戳 是 本批次扩容
            
            //条件二: JDK1.8 中有bug jira已经提出来了 其实想表达的是 =  sc == (rs << 16 ) + 1
            //        true-> 表示扩容完毕,当前线程不需要再参与进来了
            //        false->扩容还在进行中,当前线程可以参与
            //条件三:JDK1.8 中有bug jira已经提出来了 其实想表达的是 = sc == (rs<<16) + MAX_RESIZERS
            //        true-> 表示当前参与并发扩容的线程达到了最大值 65535 - 1
            //        false->表示当前线程可以参与进来
            //条件四:(nt = nextTable) == null
                     //nextTable在完成扩容后会赋值给table,然后nextTable置为null
            //        true->表示本次扩容结束
            //        false->扩容正在进行中
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                transferIndex <= 0)
                break;

            //前置条件:当前table正在执行扩容中.. 当前线程有机会参与进扩容。
            //条件成立:说明当前线程成功参与到扩容任务中,并且将sc低16位值加1,表示多了一个线程参与工作
            //条件失败:1.当前有很多线程都在此处尝试修改sizeCtl,有其它一个线程修改成功了,导致你的sc期望值与内存中的值不一致 修改失败
            //        2.transfer 任务内部的线程也修改了sizeCtl。
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                //协助扩容线程,持有nextTable参数
                transfer(tab, nt);
        }
        //1000 0000 0001 1011 0000 0000 0000 0000 +2 => 1000 0000 0001 1011 0000 0000 0000 0010
        //条件成立,说明当前线程是触发扩容的第一个线程,在transfer方法需要做一些扩容准备工作
        else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                     (rs << RESIZE_STAMP_SHIFT) + 2))
            //触发扩容条件的线程 不持有nextTable
            transfer(tab, null);
        s = sumCount();
    }
}

可以看到扩容操作在transfer函数中进行,addCount会负责维护sizeCtl,并且让当前线程发起扩容,或者参与扩容,我们关注下发起和参与是如何区分的

image-20230319144266666678

可以看到addCount在并发扩容这一步相当于是一个调度者,在自旋中让当前线程,要么发起(只有一个幸运儿可以发起)要么加入,要么扩容结束当前线程break

接下来我们看看transfer是如何让多个线程有条不紊进行扩容的
2.2.5.3 transfer方法实现并发扩容

假如你现在有100个手下,你需要安排他们一起做一件事情(扩容迁移),且这一百个手下能力一样(CPU分时调度,谁也别瞧不起谁)你要如何协调他们昵?

  • 分配任务


    • 任务尽量均匀
    • 任务不要太小,100个线程迁移64长度的格子,难道每一个线程0.64个格子么,ConcurrentHashMap是基于内存的,读写很快,所有任务太小反而会因为线程上下文的切换带来更多的开销
  • 迁移过程中如何告诉读线程,这个数组下标的元素已经被迁移走了,你去新表中读吧,尽量不要阻塞读

    如何告诉写线程,当前在扩容迁移,让写线程参与进来帮忙一起迁移?

    这里Doug lea使用
    ForwardingNode
    来实现新数组的路由,和让写线程根据特定节点hash值,来参与扩容

    image-20230319150511610

  • 如何同步多个线程迁移的进度

    这里使用全局属性transferIndex记录迁移的精度,使用volatile修饰,实现进度对多个线程可见

transfer这段代码很妙,很长,我们分段看
  1. 任务分配和多线程间的协调和一些前置操作

    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        //n 表示扩容之前table数组的长度
        //stride 表示分配给线程任务的步长
        int n = tab.length, stride;
        //MIN_TRANSFER_STRIDE = 16
        //如果我们具备多核CPU 且 数组长度/8/cpu核心数 > 16
        // 那么 每一个线程分配 【数组长度/8/cpu核心数】个连续数组单元进行扩容迁移
        //NCPU > 1) ? (n >>> 3) / NCPU : n
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
    
    
        //条件成立:表示当前线程为触发本次扩容的线程,需要做一些扩容准备工作
        //条件不成立:表示当前线程是协助扩容的线程..
        if (nextTab == null) {            // initiating
            try {
                //创建了一个比扩容之前大一倍的table
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            //赋值给对象属性 nextTable ,方便协助扩容线程 拿到新表
            nextTable = nextTab;
            //记录迁移数据整体位置的一个标记。
            // 从1开始计算的,不是从0开始,也就是说transferIndex = n 表示从n-1开始迁移直到0
            transferIndex = n;
        }
    
        //表示新数组的长度
        int nextn = nextTab.length;
        //fwd 节点,当某个桶位数据处理完毕后,将此桶位设置为fwd节点,
        //fwd节点持有nextTable的引用,且其hash恒定位MOVED = -1
        //如果线程企图写到这个单元格那么会加入扩容,如果尝试读那么将被转移到新数组中进行读
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        //推进标记
        boolean advance = true;
        //完成标记
        boolean finishing = false; // to ensure sweep before committing nextTab
    
        //i 表示分配给当前线程任务,执行到的桶位,从0开始计数,
        // 也就是说如果i=10 表示当前线程要迁移i-stride~i的数组单元格
        //bound 表示分配给当前线程任务的下界限制
        int i = 0, bound = 0;
        //自旋
        for (;;) {
            //f 桶位的头结点
            //fh 头结点的hash
            Node<K,V> f; int fh;
    
            //下面的代码要进行
            //1.给当前线程分配任务区间
            //2.维护当前线程任务进度(i 表示当前处理的桶位)
            //3.维护ConcurrentHashMap对象全局范围内的进度
            
            while (advance) {
                //分配任务的开始下标
                //分配任务的结束下标
                int nextIndex, nextBound;
    
                //CASE1:
                //条件一:--i >= bound
                //成立:表示当前线程的任务尚未完成,还有相应的区间的桶位要处理,--i 就让当前线程处理下一个 桶位.
                //不成立:表示当前线程任务已完成 或 者未分配
                if (--i >= bound || finishing)
                    advance = false;
                //CASE2:
                //前置条件:当前线程任务已完成 或 者未分配
                //条件成立:表示对象全局范围内的桶位都分配完毕了,没有区间可分配了,
                    // 设置当前线程的i变量为-1 跳出循环后,执行退出迁移任务相关的程序
                //条件不成立:表示对象全局范围内的桶位尚未分配完毕,还有区间可分配
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                //CASE3:
                //前置条件:1、当前线程需要分配任务区间  2.全局范围内还有桶位尚未迁移
                //条件成立:说明给当前线程分配任务成功
                //条件失败:说明分配给当前线程失败,应该是和其它线程发生了竞争吧
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
    
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
    
            //CASE1:
            //条件一:i < 0
            //成立:表示当前线程未分配到任务
            if (i < 0 || i >= n || i + n >= nextn) {
                //保存sizeCtl 的变量
                int sc;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
    
                //条件成立:说明设置sizeCtl 低16位  -1 成功,当前线程可以正常退出
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    //1000 0000 0001 1011 0000 0000 0000 0000
                    //条件成立:说明当前线程不是最后一个退出transfer任务的线程
                    //如果当前线程是最后一个那么 sizeCtl 前16位是扩容标识戳,
                    //后16位是 0000 0000 0010 = 2 所以这里减2 就是拿到 高16位为扩容戳,低16位全0的数
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        //正常退出
                        return;
    
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            //前置条件:【CASE2~CASE4】 当前线程任务尚未处理完,正在进行中
    
            //CASE2:
            //条件成立:说明当前桶位未存放数据,只需要将此处设置为fwd节点即可。
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            //CASE3:
            //条件成立:说明当前桶位已经迁移过了,当前线程不用再处理了,直接再次更新当前线程任务索引,再次处理下一个桶位 或者 其它操作
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            //CASE4:
            //前置条件:当前桶位有数据,而且node节点 不是 fwd节点,说明这些数据需要迁移。
            else {
                //下面是真正进行迁移
    

    • nextTable的初始化

      image-20230319151916872

      这可以看到扩容数组大小是原数组的两倍(n<<1)但是doug lea 不害怕这里nextTable重复初始化导致迁移工作白做的问题么?其实在调用transfer方法的地方都有如下这段代码做控制

      image-20230319152421990

      可以看到如果nextTable为null,那么其他线程会视当前扩容还没有启动,从而break出去!doug lea之所以这么做主要是为了实现nextTable初始化和其他线程写操作的异步,如果第一个线程没有初始化nextTable 那么其他线程break掉自旋,让写操作不要等待这个初始化nextTable的操作,狠狠的压榨CPU!!! 卧槽 doug lea您是真的牛逼!

    • 自旋+cas分配任务

      image-20230319154418872

  2. 真正进行迁移

    image-20230319155832762

    这一段代码最妙的点,在对于最后一个线程的判断,校验sc-2低16位是否全部为0的同时,还是保证了 当前线程是这一批次的扩容线程,并且对于最后一个线程,它将负责修改table 为新数组,修改nextTable = null

    其中如果迁移了null格子,或者迁移到已经被迁移的格子,advance会赋值位true,将继续分配格子进行迁移

    接下来就是使用synchronized,实现元素的迁移
    

     //synchronized 加锁当前桶位的头结点
            synchronized (f) {
                //这里和put 一样会
                if (tabAt(tab, i) == f) {
                    //ln 表示低位链表引用
                    //hn 表示高位链表引用
                    Node<K,V> ln, hn;
    
                    //条件成立:表示当前桶位是链表桶位
                    if (fh >= 0) {
                        //lastRun机制
                        //可以获取出 当前链表 末尾连续高位不变的 node
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
              			//从头开始,
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
    						//确保为连续的高位,或者为连续的低位
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
    
                        //条件成立:说明lastRun引用的链表为 低位链表,那么就让 ln 指向 低位链表
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        //否则,说明lastRun引用的链表为 高位链表,就让 hn 指向 高位链表
                        else {
                            hn = lastRun;
                            ln = null;
                        }
    
                        //注意这里是new了一个节点,并没有改变原本链表的结构
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        //加锁了下面没有使用
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    //条件成立:表示当前桶位是 红黑树 代理结点TreeBin
                    else if (f instanceof TreeBin) {
                        //转换头结点为 treeBin引用 t
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        //低位双向链表 lo 指向低位链表的头  loTail 指向低位链表的尾巴
                        TreeNode<K,V> lo = null, loTail = null;
                        //高位双向链表 lo 指向高位链表的头  loTail 指向高位链表的尾巴
                        TreeNode<K,V> hi = null, hiTail = null;
    
                        //lc 表示低位链表元素数量
                        //hc 表示高位链表元素数量
                        int lc = 0, hc = 0;
    
                        //迭代TreeBin中的双向链表,从头结点 至 尾节点(TreeNode其实有next和pre指针将树节点串联起来)
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            // h 表示循环处理当前元素的 hash
                            int h = e.hash;
                            //使用当前节点 构建出来的 新的 TreeNode
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
    
                            //条件成立:表示当前循环节点 属于低位链 节点
                            if ((h & n) == 0) {
                                //条件成立:说明当前低位链表 还没有数据
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                //说明 低位链表已经有数据了,此时当前元素 追加到 低位链表的末尾就行了
                                else
                                    loTail.next = p;
                                //将低位链表尾指针指向 p 节点
                                loTail = p;
                                ++lc;
                            }
                            //当前节点 属于 高位链 节点
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        //如果元素个数小于 红黑树转化为链表的阈值 6 那么进行链表化
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin<K,V>(lo) : t;
                        //同上
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
    

这里最妙最妙最妙的就是lastRun这个机制,为什么doug lea要从头找到尾部连续个高位或者低位的节点

  • 何为高位,低位

    image-20230319162537748

    注意红色箭头指的这一位,由于数组的长度是2的倍数,所以结尾是全0,存在一位为1,和其他key的hash值进行且操作 = 获取这个key在红色箭头这一位是0 还是 1,如果是1视作高位,反之视为低位。当前线程在迁移位于x位置的节点,那么高位节点们迁移后将位于新表的x+n位置,低位节点迁移后还是位于新表的x位置。下面解释这一点

    image-20230319164130118

    如果一个数原本在红色箭头位置是1,那么和扩容后的数进行且操作的时候,蓝色箭头位置这一位必然也是1,蓝色箭头之后的位置也是不变的,对于高位的key且操作之后,蓝色箭头位置是1,对于低位的key且 操作后蓝色位置是0。为1可以看作实在原本橙色基础上加上了一个64,为0可以看作是在原本橙色基础上加了0

    image-20230312170005373

  • lastRun存在的必要,为什么要这么做?

    减少new Node对象的操作

    image-20230319165340200

    这里原本就有一部分连续的高位节点,直接拿到绿色节点的作为高位的头即可。但是不能切断原本链表中任何的节点的连接指针,也就是说如果想把蓝色框框这部分节点进行迁移,需要new Node,为什么昵?

    因为并发迁移的过程中,可能存在其他线程正在读这个链表,如果我们断开了之前节点的连接将导致其他线程找不到原本链表中的节点,doug lea后面也确实是使用new的方式,这样相当于给读线程一个一致性视图(HashMap则没有这个策略,直接把原节点拆开两部分)

    img

2.2.6 回到put源码,看看帮助扩容helpTransfer

image-20230319170330946