Mone Zhao的博客

Happens-before 关系

happens-before 关系保证：如果线程 A 与线程 B 满足 happens-before 关系，则线程 A 执行动作的结果对于线程 B 是可见的。如果两个操作未按 happens-before 排序，JVM 将可以对他们任意重排序。

下面介绍几个与理解 ConcurrentHashMap 有关的 happens-before 关系法则：

1. 程序次序法则：如果在程序中，所有动作 A 出现在动作 B 之前，则线程中的每动作 A 都 happens-before 于该线程中的每一个动作 B。
2. 监视器锁法则：对一个监视器的解锁 happens-before 于每个后续对同一监视器的加锁。
3. Volatile 变量法则：对 Volatile 域的写入操作 happens-before 于每个后续对同一 Volatile 的读操作。
4. 传递性：如果 A happens-before 于 B，且 B happens-before C，则 A happens-before C。

Java 7基于分段锁的ConcurrentHashMap

数据结构

Java 7中的ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

1. 最大的分段（segment）数为2的16次方，每一个segment的HashEntry[]的最大容量为2的30次方。
2. 默认的分段数和每个segment的HashEntry[]的初始容量均为16。segment的默认加载因子为0.75。
3. 定位segment段需要用的两个参数：segmentMask，segmentShift。

整体数据结构如下图所示：

什么是线程

一个线程是进程的一个顺序执行流。同类的多个线程共享一块内存空间和一组系统资源，线程本身有一个供程序执行时的堆栈。线程在切换时负荷小，因此，线程也被称为轻负荷进程。一个进程中可以包含多个线程。

进程与线程的区别

一个进程至少有一个线程。线程的划分尺度小于进程，使得多线程程序的并发性高。另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

线程在执行过程中与进程的区别在于每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用来实现进程的调度和管理以及资源分配。

并发原理

多个线程或进程”同时”运行只是我们感官上的一种表现。事实上进程和线程是并发运行的，OS的线程调度机制将时间划分为很多时间片段（时间片），尽可能均匀分配给正在运行的程序，获取CPU时间片的线程或进程得以被执行，其他则等待。而CPU则在这些进程或线程上来回切换运行。微观上所有进程和线程是走走停停的，宏观上都在运行，这种都运行的现象叫并发，但是不是绝对意义上的“同时发生。

摘要

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别，深入探讨HashMap的结构实现和功能原理。

简介

Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

下面针对各个实现类的特点做一些说明：

1. HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

2. Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

3. LinkedHashMap：LinkedHashMap是HashMap和双向链表合二为一的HashMap一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

4. TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

apt.sh更新清理软件

1
2
3
4
5
6
7
8
9
10
11
12
13
14

sudo aptitude update
sudo aptitude upgrade -y
sudo aptitude autoclean -y
sudo aptitude clean

echo "\033[31m aptitude end \033[0m"

sudo apt-get update
sudo apt-get upgrade -y
sudo apt-get autoremove -y
sudo apt-get autoclean
sudo apt-get clean

echo "\033[31m apt-get end \033[0m"

ls.sh查看deb包缓存

1
2
3
4

cd /var/cache/apt/archives
pwd
echo "==================="
ls | grep deb

非pom导入的额外Jar包, 在 maven clean install 的时候是会报错的, 程序包 *.*.* 不存在, 需要配置 pom.xml。

我们将额外Jar包放在一个统一的目录 ${dirs} 下面。

dependency 加上 <scope>system</scope> 以及 Jar包位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<dependency>
  <groupId>${groupId}</groupId>
  <artifactId>${artifactId}</artifactId>
  <version>${version}</version>
  <scope>system</scope>
  <systemPath>${project.basedir}/${dirs}/target1.jar</systemPath>
</dependency>

<dependency>
  <groupId>${groupId}</groupId>
  <artifactId>${artifactId}</artifactId>
  <version>${version}</version>
  <scope>system</scope>
  <systemPath>${project.basedir}/${dirs}/target2.jar</systemPath>
</dependency>

npm使用淘宝源

1

npm config set registry https://registry.npmmirror.com/

.npmrc

1
2
3

registry=https://registry.npmmirror.com/
sass_binary_site=https://npm.taobao.org/mirrors/node-sass/
electron_mirror=https://npm.taobao.org/mirrors/electron/

使用cnpm

1

npm install -g cnpm@6.2.0 --registry=https://registry.npmmirror.com

.yarnrc

1
2
3
4
5
6
7
8

# THIS IS AN AUTOGENERATED FILE. DO NOT EDIT THIS FILE DIRECTLY.
# yarn lockfile v1


registry "https://registry.npmmirror.com/"
electron_mirror "https://npm.taobao.org/mirrors/electron/"
lastUpdateCheck 1692882092809
sass_binary_site "https://npm.taobao.org/mirrors/node-sass/"

使用nvm管理node版本

1
2
3
4
5

# 列出node版本
nvm ls

#切换node版本
nvm use 16.20.1

Fixing npm permissions

1

sudo chown -R $(whoami) $(npm config get prefix)/{lib/node_modules,bin,share}

This changes the permissions of the sub-folders used by npm and some other tools (lib/node_modules, bin, and share).

什么是 CAS

CAS, Compare and Swap 即比较并替换, CAS 有三个操作数：内存值 V、旧的预期值 A、要修改的值 B, 当且仅当预期值 A 和内存值 V 相同时, 将内存值修改为 B 并返回 true, 否则什么都不做并返回 false。

java.util.concurrent.atomic 包下的原子操作类都是基于 CAS 实现的, 接下去我们通过 AtomicInteger 来看看是如何通过 CAS 实现原子操作的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class AtomicInteger extends Number implements java.io.Serializable {
    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    public final int get() {return value;}
}

1. Unsafe 是 CAS 的核心类, Java 无法直接访问底层操作系统, 而是通过本地（native）方法来访问。不过尽管如此, JVM 还是开了一个后门, JDK 中有一个类 Unsafe, 它提供了硬件级别的原子操作。

2. valueOffset 表示的是变量值在内存中的偏移地址, 因为 Unsafe 就是根据内存偏移地址获取数据的原值的。

3. value 是用 volatile 修饰的, 保证了多线程之间看到的 value 值是同一份。

说明

sychronized 一般用来修饰一个方法或者一个代码块。利用 sychronized 实现同步的基础：java 中每一个对象都可以作为锁。具体表现为以下 3 中形式。

1. 修饰一个代码块, 被修饰的代码块称为同步语句块, 其作用的范围是大括号{}括起来的代码, 作用的对象是调用这个代码块的对象；

2. 修饰一个方法, 被修饰的方法称为同步方法, 其作用的范围是整个方法, 作用的对象是调用这个方法的对象；

3. 修改一个静态的方法, 其作用的范围是整个静态方法, 作用的对象是这个类的所有对象；

4. 修改一个类, 其作用的范围是synchronized后面括号括起来的部分, 作用主的对象是这个类的所有对象。

一个线程访问一个对象的synchronized代码块时, 别的线程可以访问该对象的非synchronized代码块而不受阻塞。

总结

1. 无论synchronized关键字加在方法上还是对象上, 如果它作用的对象是非静态的, 则它取得的锁是对象；如果synchronized作用的对象是一个静态方法或一个类, 则它取得的锁是对类, 该类所有的对象同一把锁。

2. 每个对象只有一个锁（lock）与之相关联, 谁拿到这个锁谁就可以运行它所控制的那段代码。

3. 实现同步是要很大的系统开销作为代价的, 甚至可能造成死锁, 所以尽量避免无谓的同步控制。

锁的可重入性

先举例来说明锁的可重入性：

1
2
3
4
5
6
7
8
9
10
11
12
13

public class UnReentrant{
    Lock lock = new Lock();
    public void outer(){
        lock.lock();
        inner();
        lock.unlock();
    }
    public void inner(){
        lock.lock();
        //do something
        lock.unlock();
    }
}

outer 中调用了 inner, outer 先锁住了 lock, 这样 inner 就不能再获取 lock。其实调用 outer 的线程已经获取了 lock 锁, 但是不能在 inner 中重复利用已经获取的锁资源, 这种锁即称之为 不可重入 。通常也称为 自旋锁 。相对来说, 可重入就意味着：线程可以进入任何一个它已经拥有的锁所同步着的代码块。

ReentrantLock 相比 synchronized 有如下几个优势

1. 可以反复进入, 同一个线程获得几个锁, 在释放的时候也需要同等释放, 要不然会死锁的（其实 synchronized 也是可重入的）；

2. 支持锁中断 lockInterruptiblity(), 防死锁, 优先响应中断；

3. 支持限时获取锁, lock.tryLock(int,TimeUnit); 在给定的时间范围捏尝试获取锁；

4. 支持尝试获取锁, tryLock 不带参数, 如果获取不到则立刻返回 false, 而不等待锁；

5. 公平锁 ReentrantLock(boolean fair), 排队获取锁, 性能相对低下；

6. 配合 Condition, 可以让线程在合适的时间等待, 得到通知后继续执行。

类的加载

其中类加载的过程包括了加载、验证、准备、解析、初始化、使用、卸载七个阶段。验证、准备、解析三个阶段统称为连接。

在这七个阶段中, 加载、验证、准备和初始化和卸载这五个阶段发生的顺序是确定的, 而解析阶段则不一定, 它在某些情况下可以在初始化阶段之后开始, 这是为了支持 Java 语言的运行时绑定（也成为动态绑定或晚期绑定）。另外注意这里的几个阶段是按顺序开始, 而不是按顺序进行或完成, 因为这些阶段通常都是互相交叉地混合进行的, 通常在一个阶段执行的过程中调用或激活另一个阶段。

加载

加载时类加载过程的第一个阶段, 在加载阶段, 虚拟机需要完成以下三件事情：

1. 通过一个类的全限定名来获取其定义的二进制字节流。
2. 将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构。
3. 在 Java 堆中生成一个代表这个类的 java.lang.Class 对象, 作为对方法区中这些数据的访问入口。

在类加载器中将详细描述使用类加载器加载类的过程