2024年7月

用StabilityMatrix一键安装Stable Diffusion

作者: wenmo8
时间: 2024-07-06
分类: 其它
评论

Stable Diffusion是2022年发布的深度学习文字到图像生成模型，它既能免费使用，又能部署在本地端，又有非常多的模型可以直接套用，在使用体验上比Midjourney和DALL-E更加强大。

Stable Diffusion使用的模型有下列几大类，对照模型网站
https://civitai.com
以形成更直观的认识：

Base Model： Stable Diffusion的基底模型（Base models），由StableAI公司开源而来的最基础模型
- 常见的基底模型有SD 1.5、SD2.0、SDXL 1.0等
Checkpoint：当做图像生成的基础模型，通称为大模型
1. 由Base Model为基础微调而形成的模型，可生成质量更高的图像
2. 形成图像的基本风格，例如真实风格或卡通风格等，分别使用不同的两种Checkpoint
3. 合并多个Checkpoint而成的形成Checkpoint Merge
选项模型：附加在Checkpoint上的微调模型，可视为修补+滤镜功能的模型，增强或改变图像的风格
1. Textual Inversion（文本反转，embedding）：用新的关键词来产生新的特征
2. LoRA（Low-Rank Adaptation，低秩调整）： Checkpoint就像是AI画家的「基本画功」，而LoRA则是要求AI画家「照这个风格」产生图片
3. VAE（Value Auto Encoder）：用来调整亮度或饱和度的微调模型

不过Stable Diffusion的部署步骤有点繁复，必须安装Python相关环境、Git执行环境等等，但现在通过采用AvanloniaUI编写的跨平台桌面应用StabilityMatrix只要执行一个StabilityMatrix.exe就可以了，它会自动下载需要的文件与模型，并提供了图形界面让我们可以方便的控制多达 10几个Web UI（支持Automatic 1111、Comfy UI、SD.Next (Vladmandic)、VoltaML、InvokeAI、Fooocus 和Fooocus MRE），可以说StabilityMatrix大幅降低了Stable Diffusion的使用门槛。

本次介绍完整的StabilityMatrix安装步骤，Stablility 支持Linux、Mac和Windows，下面的安装是Windows 11下进行的。

1. 安装步骤

解压缩 StabilityMatrix-win-x64.zip 后执行StabilityMatrix.exe。在检查到NVIDIA显卡后，勾选同意授权协议再按【Continue】

勾选【Portable Mode】以建立便携环境，运行环境会建立在执行文件相同位置的Data文件夹里

选择Web UI，先使用最常见的Stable Diffusion WebUI，点击【Install】

开始安装并下载需要的文件...，它将在安装过程中显示推荐的型号（检查点）。它分为最流行的常规型号“SD1.5系列”和“SDXL系列”，具有高性能而不是较大的VRAM负载。每个都有几GB的大容量，因此下载时间会增加，但是如果有您想要的模型，请在此处查看并下载。

安装完成后会显示《Package》页面

点击三横线显示完整的侧边栏菜单
点击绿色的【Package】就能启动安装好的SwarmUI
【启动】按钮右侧的齿轮可设定启动参数

关于启动选项

更高级一点。 SDwebUI 可以通过填写写成“--◯◯”的“命令行参数”来启动，以启用各种可选功能。例如，有一个功能可以生成具有少量 VRAM 的 grabo，并加快生成速度。

在 StabilityMatrix 中，您可以在按下“启动”按钮之前按旁边的齿轮“⚙”按钮来调用启动选项屏幕，并且可以通过选中它通过“启动”来激活它。

请参阅官方网站了解每个启动选项的含义。您还可以通过自己填写参数来添加菜单中没有的内容。这里只是您应该记住的默认菜单中的选项。

-xformers：有望提高图像生成速度并显著减少 VRAM 使用。请注意，它只能与 NVIDIA Gravo 一起使用。几乎每个人都使用它

-autolaunch：webUI加载完毕后在浏览器中自动启动的功能，但在v1.6.0及以上版本中，可以在webui上设置，所以没有用。

-lowvram：用于低 VRAM 抓取。性能可能是灾难性的，因此能够生成图像。

–medvram — 以牺牲速度为代价减少VRAM的使用。

-medvram_sdxl：仅当使用 SDXL 模型时才激活 medvram。

5.点击【Packages】→【Add Package】可再新增其他的WebUI套件

6. 第一次启动（启动）时会自动复制需要的档案，其中默认的模型主档 v1-5-pruned-emaonly.safetensors 有3.97GB，需要花点时间下载。下载完成并启动后，会自动开启浏览器浏览网址
http://127.0.0.1:7801

2. 初次测试

State Diffusion checkpoint（大模型）选用预设的v1-5-pruned-emaonly.safetensors
，学习模型（检查点）通常主要以扩展名“.safetensors”和“.ckpt”分发，如果您将它们扔到指定的文件夹中，它们将起作用。除了 StabilityAI 的每个版本的 StableDiffusion 之外，网络上还分享了无数的衍生模型，有些带有插图，有些带有逼真的色调，有些介于两者之间，有些擅长柔和的表达，等等。
在txt2img分页的【Prompt】（正面提示词）输入
a cute kitten
【Negative Prompt】（负面提示词）输入
(worst quality:2),(low quality:2),(normal quality:2),lowres
- 负面提示词指示避免产生的属性，括号里可额外设定权重
点击【Generate】开始生成图片。产生时StabilityMatrix.exe窗口会显示执行记录

2.1. 生成结果

3.总结

目前 ComfyUI 对于新模型与新应用支持更好，已经有超越 Stable Diffusion web UI的趋势，SwarmUI 同时支持ComfyUI和SDWebUI，Fooocus由于简洁、占用资源低的原因，也越来越受欢迎，如果你是多个软件的用户，那么不妨考虑使用Stability Matrix 进行集中化管理。

4. 相关链接

解密Prompt系列33. LLM之图表理解任务-多模态篇

作者: wenmo8
时间: 2024-07-06
分类: 其它
评论

上一章我们介绍了纯文本模态的表格理解任务，这一章我们聚焦多模态图表数据。先讨论下单纯使用prompt的情况下，图片和文字模态哪种表格模型理解的效果更好更好，再说下和表格相关的图表理解任务的微调方案。

Prompt：表格模态哪家强

使用prompt对比SOTA的文本模型和多模态模型，哪个在表格理解任务上效果更好，可以借鉴以下两篇论文，前者使用了已有的TableQA Benchmark，后者新构建的TableVQA Benchmark。

Table as Text or Image

TableVQA-Bench: A Visual Question Answering Benchmark on Multiple Table Domains

这是一篇实验性论文，有如下几个实验变量

不同的开源（llama2）闭源（GPT3.5，GPT4，Gmini）模型
不同格式的文本表格数据：纯文字逗号分割（vanilla）类,行号标注类，括号数组类，行json，列json等5种
不同格式的图片表格数据：纯表格图片（Vanilla），每列一种颜色，每行一种颜色等3种
不同的prompt方案：vanilla，COT，和专家prompt（假设你是一个XX专家）

论文使用了以下6个数据集的混合，分别对TableQA，Table Fact-check，Table-to-text等任务进行评估。

直接来看实验结论吧

图片和文字的效果在不同数据集上存在差异
，Gmini和GPT4，当使用Vanilla的表格文本和表格图片时，在FinQA上图片显著更好，而在TabFact和WikiTQ上文本显著更好。论文猜测的点是FinQA的上文更长，导致文本表征模型容易混淆信息，而WikiTQ和TabFact是维基百科的数据，文本模型可能在预训练时见过才导致的效果更好。对比并不太充分，这么看感觉图片和文字的效果还是要在实际使用的场景上去做测试。

不论是图片和文字模态，COT都能带来显著的效果提升
，文字prompt上一章微软的另一篇论文中已经说过了，这里只看图片的实验结果，下图列（V，E，COT）分别是vanilla，ExPert和COT,行(VV,CC，RC)分别是图片无颜色，列高亮，和行高亮

更多文本模态的结论和前一章微软的论文有所重合这里了就不多说了，图片和文本的对比感觉不太充分，我们再看下下面的另一篇论文

TableVQA-Bench

TableVQA-Bench: A Visual Question Answering Benchmark on Multiple Table Domains

https://github.com/naver-ai/tablevqabench?tab=readme-ov-file

第二篇论文我们说下新出炉不久的TableVQA评估集，论文提出了新的多模态表格评估数据集。和以上论文的数据集存在重合，不过更细致地给出了数据集构建的细节，以及论文的结论也和前文存在差异。

评估集由以下三个数据集构成(点击链接可以看到数据）

VWTQ
：从维基百科表格问答的数据集WTQ，通过wiki网页链接获取原始表格的HTML截图得到图片，并通过Table Renderer对表格属性进行修改，降低维基百科在预训练中的数据泄露问题再通过截图获取图片数据（VWTQ-Syn）
VTabFact
: 表格事实检查的另类QA问题，这里未提供原始html，因此使用csv数据转换成伪html，再使用Table Renderer进行属性修改和截图
FinTabNetQA
: 本身是TSR任务，因此论文使用GPT4和HTML作为输入构建了QA对

上面提到的Table Renderer其实就是随机修改表格的HTML样式，例如加入cell color，调整文字对齐，修改边界样式，给表格加背景色等等。

基于以上评估集，论文对众多开源和商用MLLM进行了整体评估，结果如下

在3个数据集上：文本模态>图转文>图片模态
：这里的TabFact和WTQ数据集和上面一篇的论文重合，上面论文这两个数据集也是文本>图片，但并未测试前面论文中图片模态表现更好的FinQA数据集。
当图片模态效果不好时不妨试试先进行TSR模态转换
：论文还测试了用GPT-4V把图片模态转换成文本模态再用GPT-4进行回答的折中模式，效果比图片模态有提升

我们结合两篇论文来看，在当前的prompt水平上，整体上还是文本模态的表格要更好些，但确实可能存在不同上下文和表格类型上表现不同的差异性~

说完纯prompt的方案，我们再来看下图表理解相关的微调方案，这里的微调方案更多是针对图表数据中的图，例如饼图，时序图，直方图等等分别介绍ChartLlama和TinyChart两篇论文，还有一些相关的论文像ChartInstruct，ChartX，ChartAssistant会列在最后感兴趣的大家自己去看吧~

Chart SFT

ChartLlama

https://tingxueronghua.github.io/ChartLlama/

ChartLlama: A Multimodal LLM for Chart Understanding and Generation

ChartLlam的核心其实是给了一套构建多模态图表指令理解数据集的方案。然后基于构建的数据集在Llava-1.5上进行了微调训练。Llava-1.5是由VIT-L/14@336px作为图像编码器，两层MLP作为投影层，Llama作为LLM。这里ChartLlama只对Projection层和Llama层进行了微调。

既然以构建大规模，多样性的图表理解数据为主，那我们就重点说下数据构建的细节。分成以下三个步骤

step1： Chart Data生成
这里包含从头让GPT4直接构建和从已有数据中合成。以下prompt用于GPT直接生成数据，论文通过随机采样主题（预先生成了100+主题短语），数据趋势，表格的行数和列数，以及图片类型。这部分除了生成数据，还会生成数据的描述在最后的推理部分帮助模型理解数据。第一部分的核心其实是如何避免模型生成毫无意义的低质量数据

Step2: 基于ChartData绘制图片
基于以上获得的数据，论文使用GPT4的代码能力，生成matplotlib的绘图代码从而生成图片。为了代码生成的准确率，论文会随机采样可以成功执行的代码作为In-Context上文，并加入相关函数的documentation作为上文。这里除了生成代码同时还会生成图片描述，在最后的推理部分帮助模型理解图片。但整体上感觉只使用matplotlib比较容易导致这一步构建的图片本身的样式相对单一。

step3：QA对样本生成
获得图片后，就可以进行QA对的样本生成了。这里模型的输入会包括原始数据，前两部分生成的数据和图片的描述，以及问题类型。这里论文涵盖了TableQA，Summarization，数据抽取，图标描述，代码生成和图片编辑等丰富的问题类型。最终构建了总共160K的指令样本

微调和效果部分就不细说了在后面的TinyChart里面会有ChartLlama的效果数据。

TinyChart

TinyChart: Efficient Chart Understanding with Visual Token Merging and Program-of-Thoughts Learning

除了ChartLlama后面还有过很多篇论文但多数也是构建不同的数据，在不同的模型上去训练，这里我们再看一篇针对效率提升的论文。

TinyChart使用了更高效的像素合并和Program-of-Thoguhts让3B的MLLM一举超越了13B的ChartLLama。TinyChart的整体模型结构也是传统的MMLM，由Vision Transformer Encoder，Connector和LLM构成，下面我们主要说下提升效率的图像元素合并，以及提升效果的PoT

Visual Token Merging

图片编码器的输入会先把图片压缩到固定像素（N），然后裁剪成多个大小为（P）的区域作为视觉模型的token输入。因此视觉模型的token数=(N//p)^2。考虑到Chart图表理解往往需要用到图片中的文字等信息，因此必须使用高像素的图片。而像素N的提升会带来输入token平方级的增长。这里论文提出可以通过相似token合并来降低每一层的token量级。

这里其实用到了chart图表本身的图片特征，例如饼图和直方图等图片会在局部存在大量的同色色块，以及空白，因此在裁剪的区域上可以再做一层相似合并。

这里合并使用了token的self-attention的cosine similar来作为相似度度量，然后使用了二分图匹配算法，有点好奇为啥是用这个方案而不直接用矩阵。就是把所有token分两堆，然后男嘉宾（左边一堆）去找最喜欢（相似）的女嘉宾（右边一堆），保留最有眼缘（最相似）的r对嘉宾（token）进行合并。这里token合并并不一定是相邻token。

同时考虑到合并后参与attention计算的元素会减少，因此论文加入了被合并的元素数来调整scale。

\[Attention = softmax(\frac{QK^T}{\sqrt{d}} + logs)V
\]

直观来看下Token Merge的效果，这里论文展示了Transformer最后一层中最大的十组Merged Token，基本上都是白色背景，或者纯色的色块。

Program-of-Thought

为了提升模型在解决图表问题中数学计算等逻辑推理问题的效果，论文在训练时加入了让模型推理生成多步python代码的Program-of-Thought样本。而在推理时论文，会通过简单的关键词判断，如果涉及计算类问题，就选择让模型进行代码推理的prompt，否则使用文字推理的prompt。

这里论文分别通过模板和GPT进行了Chart-POT数据集的构建，总共构建了140,584条样本（question，POT Answer），每个answer包含完整带comment的python代码。包含chartQA，chart-to-text，chart-to-table，chart指令理解等几种任务，其中

Template-Base
这里论文从PlotQA中选了40个问题，然后手工编写了对应的Python代码模版，之后从每个data-table中随机采样字段和数值填入模版。总共构建了119,281个样本对
GPT-Base
尽管以上模版的样本对量级很大，但多样性非常有限，因此论文还使用以上template生成的q+code样本对作为In-Context上文，让GPT3.5基于文本化的表格数据进行回答构建。因为生成的python numpy代码，因此可以直接intrepreter运行检测输出是否正确。总共构建了21303个样本。

样本demo如下

之后基于以上的样本，TinyChart是基于TinyLlava，包含SIGCLIP作为图像Encoder，Phi-2作为作为LLM，然后分别在512*512，以及768*768的像素上进行全模型的微调。

效果如下，因为表格理解类任务的样本丰富度相对有限，所以在同领域的效果提升会比较明显，所以这个结果嘛看看就好~

论文还做了消融实验，对比了POT的加入，确实能有效提升模型在计算类问题上的效果，以及更高的分辨率配合TokenMerge可以推理效率持平的情况下提升模型效果。

其他相关论文

ChartAssisstant: A Universal Chart Multimodal Language Model via Chart-to-Table Pre-training and Multitask Instruction Tuning
ChartInstruct: Instruction Tuning for Chart Comprehension and Reasoning
ChartX & ChartVLM: A Versatile Benchmark and Foundation Model for Complicated Chart Reasoning
MMC: Advancing Multimodal Chart Understanding with Large-scale Instruction Tuning

想看更全的大模型相关论文梳理·微调及预训练数据和框架·AIGC应用，移步Github >>
DecryPrompt

如何用python计算不定积分

作者: wenmo8
时间: 2024-07-06
分类: 其它
评论

在Python中，计算不定积分（即原函数或反导数）可以通过SymPy库实现。SymPy是一个用于符号数学的Python库，支持许多类型的数学对象，包括整数、有理数、实数、复数、函数、极限、积分、微分、方程、几何等。

1. 示例一：使用SymPy库来计算不定积分

以下是一个使用SymPy库来计算不定积分的详细示例。我们将计算一个常见的函数 ∫(
x
2+3
x
+2)
d**x
的不定积分。

首先，确保我们已经安装了SymPy库。如果还没有安装，可以通过pip安装：

bash复制代码

pip install sympy

然后，我们可以使用以下Python代码来计算这个不定积分：

# 导入SymPy库中的符号变量和积分函数  
from sympy import symbols, integrate  
  
# 定义变量x  
x = symbols('x')  
  
# 定义函数f(x) = x^2 + 3x + 2  
f = x**2 + 3*x + 2  
  
# 计算不定积分  
# integrate(函数, 变量)  
indefinite_integral = integrate(f, x)  
  
# 打印结果  
print("不定积分结果:", indefinite_integral)

运行上述代码后，我们会得到输出：

复制代码

不定积分结果: x**3/3 + 3*x**2/2 + 2*x

这个结果表示函数
x
2+3
x
+2 的不定积分为 3
x
3+23
x
2+2
x
，其中常数项（积分常数）被省略了，因为不定积分通常不包括积分常数。

扩展应用

SymPy不仅可以用来计算简单的不定积分，还可以处理更复杂的符号表达式和方程。例如，我们可以用它来求解微分方程、进行符号化简、进行矩阵运算等。

注意事项

（1）在使用SymPy时，确保我们的表达式和变量都是符号类型。

（2）积分结果中的常数项（积分常数）在不定积分中通常被省略，因为不定积分表示的是一类函数，而不是一个具体的函数值。

（3）对于定积分（即给定积分上下限的积分），SymPy同样提供了
integrate
函数，但我们需要额外指定积分区间。

2. 示例二：计算基本的多项式函数的不定积分

# 导入SymPy库  
from sympy import symbols, integrate, Expr  
  
# 定义变量  
x = symbols('x')  
  
# 定义多项式函数  
f = x**2 + 3*x + 2  
  
# 计算不定积分  
indefinite_integral = integrate(f, x)  
  
# 打印结果  
print("不定积分结果:", indefinite_integral)

3. 示例三：计算包含指数函数和三角函数的不定积分

# 导入SymPy库  
from sympy import symbols, integrate, sin, exp  
  
# 定义变量  
x = symbols('x')  
  
# 定义包含指数函数和三角函数的函数  
f = exp(x) * sin(x)  
  
# 计算不定积分  
indefinite_integral = integrate(f, x)  
  
# 打印结果  
# 注意：这个积分的结果是一个特殊函数，SymPy会给出准确的表达式  
print("不定积分结果:", indefinite_integral)

4. 示例 4：使用换元积分法计算不定积分

有时候，直接积分可能很困难，但通过换元可以简化问题。然而，对于复杂的换元，SymPy可能不会自动进行。但我们可以手动进行换元，并展示如何处理这种情况。不过，对于简单情况，SymPy通常能自动识别并应用换元。这里我们展示一个直接可积的例子，但说明换元的思路。

假设我们要计算 ∫1−
x
2
d**x
，这可以通过令
x
=sin(
u
) 来换元求解。但在这个例子中，我们直接让SymPy计算它。

# 导入SymPy库  
from sympy import symbols, integrate, sqrt  
  
# 定义变量  
x = symbols('x')  
  
# 定义函数  
f = sqrt(1 - x**2)  
  
# 计算不定积分  
# 注意：这个积分实际上是半圆的面积函数的一部分，SymPy会给出准确的表达式  
indefinite_integral = integrate(f, x)  
  
# 打印结果  
print("不定积分结果:", indefinite_integral)

对于需要手动换元的复杂情况，我们通常需要定义新的变量，用表达式替换原函数中的部分，并相应地调整积分限（对于定积分）。但在不定积分的情况下，我们主要关注表达式本身，并且SymPy的
integrate
函数通常足够强大，能够处理许多需要换元的情况。

5. 示例五：计算有理函数的不定积分

有理函数是多项式函数之比。SymPy可以处理许多有理函数的积分。

# 导入SymPy库  
from sympy import symbols, integrate  
  
# 定义变量  
x = symbols('x')  
  
# 定义有理函数  
f = (x**2 + 1) / (x**3 + x)  
  
# 计算不定积分  
indefinite_integral = integrate(f, x)  
  
# 打印结果  
# 注意：结果可能包含对数函数或反三角函数  
print("不定积分结果:", indefinite_integral)

这些示例展示了如何使用SymPy库在Python中计算不同类型函数的不定积分。在实际应用中，我们可以根据需要调整函数和变量。

手把手教你解决spring boot导入swagger2版本冲突问题，刘老师教编程

作者: wenmo8
时间: 2024-07-05
分类: 其它
评论

手把手教你解决spring boot导入swagger2版本冲突问题

本文仅为个人理解，欢迎大家批评指错

首先Spring Boot 3 和 Swagger 2 不兼容。在 Spring Boot 3 中，应该使用 Springdoc 或其他与 Spring Boot 3 兼容的 API 文档工具来替代 Swagger 2。
Swagger 2 的依赖底层使用的是 javax 依赖包，而 Spring Boot 3 使用的是 Jakarta 依赖包。一般来说，可以将 Spring Boot 的版本降到 3.0.1 以下来解决这个问题，但如果想要使用 3.0.1 版本以上的 Spring Boot，启动时就会出现报错。

去pop.xml查看你springframework的版本，如果你已经是Spring boot3了，像我这里是当前的最新版3.3.1，那就改成2.7.2，改完之后点击右上角m形状的刷新按钮
改完之后使用了HttpServletRequest和HttpServletResponse的类应该都会报错，也是因为我之前提到的
Swagger 2 的依赖底层使用的是 javax 依赖包，而 Spring Boot 3 使用的是 Jakarta 依赖包。

此时不用导入这个依赖，加入了也没用spring boot2也不用这个.

<dependency>
    <groupId>jakarta.servlet</groupId>
    <artifactId>jakarta.servlet-api</artifactId>
    <version>6.0.0</version>
    <scope>provided</scope>
</dependency>

来个错误演示，加了之后的效果

这是因为Swagger 2 的依赖底层使用的是 javax 依赖包

正确做法加入这两个包替换原来的包就行了，很简单

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

在添加Swagger依赖之前先运行一下，如果你没报错但是运行失败，那就是java版本太高了，像我这里就是21
剩下就简单了，修改application.properties

因为Spring Boot 2.6.X后与Swagger有版本冲突问题，需要加入以下配置

spring.mvc.pathmatch.matching-strategy=ant_path_matcher

修改pop.xml

<!-- 添加swagger2相关功能-->
<dependency>
    <groupId>io.springfox</groupId>
    <artifactId>springfox-swagger2</artifactId>
    <version>2.9.2</version>
</dependency>
<!-- 添加swagger-ui相关功能-->
<dependency>
    <groupId>io.springfox</groupId>
    <artifactId>springfox-swagger-ui</artifactId>
    <version>2.9.2</version>
</dependency>

@Configuration  //告诉Spring容器这是一个配置类
@EnableSwagger2 //开启Swagger的功能
public class SwaggerConfig {
    
    @Bean
    public Docket createRestApi(){
        return new Docket(DocumentationType.SWAGGER_2)
                .apiInfo(apiInfo())
                .select()
                .apis(RequestHandlerSelectors.basePackage("com"))//com包下的所有AIP都交给Swagger2管理
                .paths(PathSelectors.any()).build();
    }

    /**
     * 这里为API文档显示的信息
     */
    private ApiInfo apiInfo(){
        return new ApiInfoBuilder()
                .title("演示项目API")
                .description("学习Swagger2的演示项目")
                .version("1.0")
                .build();
    }

}

成功运行

最后一步输入网址即可http://localhost:8080/swagger-ui.html

Java进阶：HashMap底层原理（通俗易懂篇）

作者: wenmo8
时间: 2024-07-05
分类: 其它
评论

1.底层结构

Java 7及之前版本

在Java 7及之前的版本中，HashMap的底层数据结构主要是
数组加链表
。具体实现如下：

数组
：HashMap的核心是一个Entry数组（
Entry<K,V>[] table
），这个数组的大小总是2的幂。每个数组元素是一个单一的Entry节点，或者是一个链表的头节点。

链表
：当两个或更多的键经过哈希运算后映射到数组的同一个索引上时，就会形成链表。Entry节点包含了键值对以及指向下一个Entry的引用，以此来解决哈希冲突。

Java 8及之后版本

从Java 8开始，HashMap的底层结构除了
数组加链表
之外，还引入了
红黑树
，以优化在链表过长时的查找性能。结构变为
数组加链表加红黑树
：

数组
：同样是一个Entry数组（Java 8中称为Node），大小仍然是2的幂，用于快速定位。
链表
：在哈希冲突时，键值对仍会以链表形式链接在一起。但与Java 7不同的是，Java 8对链表的处理增加了转换为红黑树的条件。
红黑树
：当一个桶中的链表长度超过8且HashMap的容量大于64时（不大于64会先对数组进行扩容
resize()
），链表会被转换成红黑树。这种转换提高了在大量哈希冲突情况下的查找效率，因为红黑树的查找时间复杂度为O(log n)，相较于链表的O(n)有显著提升。

2.数据插入

在JDK1.7的时候，采用的是头插法

在JDK1.8改成了尾插法，这是因为
头插法在多线程环境下扩容时可能会产生循环链表问题

线程不安全

无论是JDK1.7还是1.8都是线程不安全的
，下图是1.8中的put方法

tab是就是HashMap的数组table，第一个if判断时做了赋值。框起来的部分表示如果没有hash冲突就直接在数组上插入元素，但是如果两个线程hash一样且都进入到了这个if下，线程1先执行的插入数据，线程2会覆盖1插入的数据。

那么什么是循环链表问题呢？这就不得不介绍一下HashMap的扩容机制了。

3.扩容机制

首先讲几个HashMap的属性

table：数组，存放链表或红黑树的
头节点
Node：节点，属性有hash、key、value、next（下一个节点）
size：元素个数，即节点node个数，非数组长度
Capacity：当前数组长度
loadFactor：加载因子，默认为0.75f，简称loadFactor
threshold：扩容门槛，值为capacity*loadFactor，size达到这个门槛就扩容

当size大于threshold时，就会进行扩容
resize()
。

扩容分为两步

创建一个新的数组，长度为原数组的两倍
遍历所有Node节点，重新计算index值（Java8首先会重新计算hash值），放到新数组里，存在hash冲突的就放到链表或红黑树

为什么要重新计算index值，直接把张三这条链表复制到新的数组中不行吗？

答案是不行的，因为index规则是根据数组长度来的，如图

所以index 的计算公式是这样的：

index = HashCode(key) & (Length - 1)

4.循环链表问题

循环链表问题理解起来比较麻烦，如果理解不了就知道JDK1.7HashMap扩容的时候有这么回事就行。但是可能是我自己太笨了万一大家一看就懂了呢

我们来看一下Java1.7扩容的源码

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                //重新计算元素在数组中的索引
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

重点在于transfer方法，作用是重新计算index值然后将旧数组中的数据迁移到新数组

循环链表的产生：

原因：

假设我们有两个Thread都在执行resize方法，Thread1第一步刚执行完第23行
Entry<K,V> next = e.next;
就卡住了，这时Thread2执行完了resize方法。

过程：

Thread1第一次执行完Entry<K,V> next = e.next后，e=张三，next=李四，也就是说第二步执行李四的插入
Thread2执行完resize后，李四的next变成了张三
此时又回到Thread1，第二次执行Entry<K,V> next = e.next后，e=李四，next=张三，也就是说又要执行张三的插入，循环链表产生！

由此我们知道了循环链表产生的关键在于头部插入元素A时，元素A的next元素B的next是元素A本身，所以Java8采用了尾插法，避免了循环链表。

求赞！求关注！！以后会更新更多有用的内容！！！꒰⑅•ᴗ•⑅꒱

保佑大家代码永无bug ╰(
´︶`
)╯

2024年7月

用StabilityMatrix一键安装Stable Diffusion

1. 安装步骤

2. 初次测试

2.1. 生成结果

4. 相关链接

解密Prompt系列33. LLM之图表理解任务-多模态篇

Prompt：表格模态哪家强

Table as Text or Image

TableVQA-Bench

Chart SFT

ChartLlama

TinyChart

Visual Token Merging

Program-of-Thought

其他相关论文

如何用python计算不定积分

1. 示例一：使用SymPy库来计算不定积分

2. 示例二：计算基本的多项式函数的不定积分

3. 示例三：计算包含指数函数和三角函数的不定积分

4. 示例 4：使用换元积分法计算不定积分

5. 示例五：计算有理函数的不定积分

手把手教你解决spring boot导入swagger2版本冲突问题，刘老师教编程

手把手教你解决spring boot导入swagger2版本冲突问题

Java进阶：HashMap底层原理（通俗易懂篇）

1.底层结构

Java 7及之前版本

Java 8及之后版本

2.数据插入

线程不安全

3.扩容机制

4.循环链表问题

最新文章

最近回复

分类

归档

其它

2024年7月

用StabilityMatrix一键安装Stable Diffusion

1. 安装步骤

2. 初次测试

2.1. 生成结果

4. 相关链接

解密Prompt系列33. LLM之图表理解任务-多模态篇

Prompt：表格模态哪家强

Table as Text or Image

TableVQA-Bench

Chart SFT

ChartLlama

TinyChart

Visual Token Merging

Program-of-Thought

其他相关论文

如何用python计算不定积分

1. 示例一：使用SymPy库来计算不定积分

2. 示例 二：计算基本的多项式函数的不定积分

3. 示例 三：计算包含指数函数和三角函数的不定积分

4. 示例 4：使用换元积分法计算不定积分

5. 示例 五：计算有理函数的不定积分

手把手教你解决spring boot导入swagger2版本冲突问题，刘老师教编程

手把手教你解决spring boot导入swagger2版本冲突问题

Java进阶：HashMap底层原理（通俗易懂篇）

1.底层结构

Java 7及之前版本

Java 8及之后版本

2.数据插入

线程不安全

3.扩容机制

4.循环链表问题

最新文章

最近回复

分类

归档

其它

2. 示例二：计算基本的多项式函数的不定积分

3. 示例三：计算包含指数函数和三角函数的不定积分

5. 示例五：计算有理函数的不定积分