Kafka安全认证

发表于 2019-05-20 | 更新于 2019-06-09

Kafka安全认证整理

Jaas文件说明

// sasl  
KafkaClient {  // 客户端需要的jaas   
  org.apache.kafka.common.security.plain.PlainLoginModule required
  username="yourname"  // 客户端登录的用户名和密码，该用户名和密码要在服务配置过
  password="yourpw";
};

KafkaServer { // 服务端需要的jaas
  org.apache.kafka.common.security.plain.PlainLoginModule required
  username="admin"  // 服务端也需要一个账户进行登录
  password="admin"
  user_admin="admin"  // 配置admin账户
  user_myuser="mypw"; // 格式 user_<username>="<password>"
};

// kerberos
KafkaClient {   // 还有配置Client连接zk
  com.sun.security.auth.module.Krb5LoginModule required       
  useKeyTab=true
  keyTab="src/main/resources/user.keytab"        // 设置keytab所在的相对路径 
  principal="CORPLK50OPENAPI@HADOOP.COM"
  useTicketCache=false                           // 若为true时，可先用kinit命令获取凭证
  storeKey=true
  debug=true;
};

最后一行和倒数第二行要以分号结尾

运行配置

以程序方式运行

程序运行时要将krb5和jaas文件的路径设置在系统的环境变量里

1 2	System.setProperty("java.security.auth.login.config", "src/main/resources/jaas.conf"); System.setProperty("java.security.krb5.conf", "src/main/resources/krb5.conf");

或者

1	props.put("sasl.jaas.config", PlainLoginModule.class.getName() + " required username=\"" + username + "\" password=\"" + password + "\";");

以脚本方式运行

1	-Djava.security.krb5.conf=./krb5.conf -Djava.security.auth.login.config=./jaas.conf

sasl认证时不用配krb5
kinit -kt ./user.keytab MYPRINCIPAL@HADOOP.COM

SASL + ACL

properties文件中配置

1 2	security.protocol=SASL_PLAINTEXT sasl.mechanism=PLAIN

使用kafka-acls.sh脚本对用户权限进行授权

Kerberos

properties文件中配置

1
2
3

security.protocol=SASL_PLAINTEXT
sasl.mechanism=GSSAPI
sasl.kerberos.service.name=kafka

Java并发编程——理论基础

发表于 2019-05-15 | 更新于 2019-06-09

Java并发编程学习笔记——理论基础

并发的三个核心问题

分工
同步
互斥

微观层面

CPU增加缓存，以均衡与内存的速度差异。
缓存带来可见性问题
可见性：一个线程对共享变量的修改，另外一个线程能够立即看到
操作系统增加进程线程，分时复用CPU，均衡与IO设备的速度差异。
线程切换带来原子性问题
原子性：一个或多个操作在CPU执行过程中不被中断的特性

例如：count += 1； 32位机器对long型变量都不是原子性操作
编译器优化指令执行次序，使缓存更加合理地利用。
编译优化带来有序性问题

例如：双重检查创建单例对象

宏观层面

安全性 => 互斥、锁
数据竞争：多个线程访问未加锁的共享资源
竟态条件：程序的执行结果依赖线程的执行顺序
活跃性 => 资源公平分配，公平锁，等待队列
死锁，活锁，饥饿
性能问题
使用无锁的数据结构和算法，减少持有锁的时间

指标
吞吐量：指单位时间内能处理的请求数量
延时：指发出请求到收到响应的时间
并发量：指同时能处理的请求数量

Java内存模型对可见性和有序性的处理

Happens-Before规则

程序次序规则
在一个线程中，按照程序的顺序，前面的操作happens-before于后续的操作
volatile变量规则
对volatile变量的写操作happens-before于后续对该变量的读操作 (一个线程写volatile变量后，其他线程总是可见的)
管程锁定规则
对一个锁的解锁操作happens-before于后续对这个锁的加锁操作 (一个线程在锁中的操作，解锁后其他线程都是可见的)
线程启动规则
线程A调用线程B的start方法时，线程B能够看到线程A在启动线程B前的操作
线程终止规则
线程A得到线程B完成(调用线程B的join方法)，当线程B完成返回后，线程A能够看到线程B的操作(对于共享变量而言)

Happens-Before是有传递性的

实现方式：内存屏障(Memory Barrier)；对编译器而言，内存屏障会限制指令重排序；对处理器而言，内存屏障会使缓存刷新

锁对原子性问题的处理

加锁的本质是在锁对象的对象头中写入当前线程id

原子性的本质：多个资源间有一致性要求，操作的中间状态对外不可见

class SafeCals {
    long value = 0L;
    long get() {  // 但get方法的可见性没保证到
        return value;
    }
    synchronized void addOne() { //多线程执行addOne方法能保证可见性
        value += 1;
    }
}

解决方法：get方法加锁synchronized，或value变量加volatile关键字

// 加的是SafeCals.class的锁，加不同的锁也无法保证可见性
synchronized static long get() { 
    return value;
}

// JVM逃逸分析后，sync代码会被优化掉
void addOne() {
    synchronized(new Object()) {
        value += 1;
    }
}

锁和受保护资源的关系

受保护资源和锁的关系应该是N：1 (不能多把锁保护一个资源)

class Account {
    private int balance;
    
    // 有并发问题，this对象只能保护自己的balance字段
    // 保护不了target对象的balance字段
    synchronzied void transfer(Account target, int amt) {
        ...
    }
}

解决方法：创建Acount是传入同一个Object对象作为锁, 或者使用Account.class作为锁(但有性能问题，所有账户的转账transfer操作都会变成串行的)

不能用this.balance这类可变对象作为锁，例如Integer，String，Boolean

死锁的处理方式

void transfer(Account target, int amt) {
    synchronzied(this) {
        synchronzied(targer) {   
            // 锁的粒度细，但先后加锁不同的对象，有可能产生死锁
            ...
        }
    }
}

当以下四个条件同时满足时，才会发生死锁

互斥：共享资源X和Y只能被一个线程占有 (目的)
占有且等待：线程占有X在等待Y时，不会释放X
不可抢占：其他线程不能抢占线程占有的资源
循环等待：两个线程相互等待对方占有的资源

破坏占有且等待条件

一次申请所有资源

// 创建一个单例的类，负责一次申请所有资源
class Allocator {
    private List<Object> als = new ArrayList<>(); // 存放表示已申请到的资源
    synchronzied boolean apply(Object from, Object to) {
        // list中有对象，表明锁已经被其他线程申请了
        if (als.contain(from) || als.contain(to)) 
            return false;
        else {
            als.add(from);
            als.add(to);
        }
        return true;
    }
}

破坏不可抢占条件

要求获取资源的线程能主动解锁 (synchronzied原语做不到主动释放资源)

破坏循环等待条件

对资源进行排序，申请资源时按顺序申请 (相对来说成本小)

等待-通知机制

while(!allocator.apply(from, to));   // 不停的请求锁
---
    // 改进后
    synchronzied void apply(Object from, Object to) {
        while (als.contain(from) || als.contain(to)) 
            try {
                wait();
            } catch(Exception e) {
            }
        als.add(from);
        als.add(to);
    }

    // 释放资源
    synchronzied void free() {
        als.remove(from);
        als.remove(to);
        notifyAll();
    }

管程

管程：管理共享变量以及对共享变量的操作过程，让其支持并发

管程对互斥的处理方式

将共享变量及其操作封装起来(类似Java)，同一时间只允许一个线程进入管程执行

管程对同步的处理方式

同步意味着有条件控制
MESA管程模型
Hasen/Hoare/MESA三种管程模型的核心区别: 当条件满足后，通知线程的方式不同 (假如当线程T2使线程T1等待的条件满足，线程T1和T2如何执行)

Hasen: 要求notify方法放在最后。T2通知完T1后，T2结束，T1执行
Hoare：T2通知完T1后，T2阻塞，T1立马执行，T1执行完再唤醒T2
- 多了阻塞操作，本质是中断当前线程
MESA：T2通知完T1后，T2接着执行，T1从条件变量等待队列进入到入口等待队列
- 好处是notify不用放在最后，也无阻塞操作
- 副作用是当T1执行时，条件有可能变化，因此需要轮询执行条件
  1
  2
  3
  4
  // MESA管程模型的编程范式
  while(条件不满足) {
  wait();
  }

Java内置的管程synchronized对MESA模型进行了精简，只有一个条件变量。

wati()方法只有MESA模型有超时时间的参数。因为notify后，是将等待的线程放入入口等待队列，不一定有机会执行，所以要设超时时间。Hasen/Hoare模型都是notify后，等待的线程肯定能执行到。

Thread th = Thread.currentThread();
while(true) {
    if (th.isInterrupted()) {
        break;
    }
    ...
    try {
        Thread.sleep(100);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}
// 当线程被中断后，不能退出while循环
// 因为抛出异常后会清理中断标志，因此执行不到break语句 (线程大部分时间在执行sleep)

修改方式：

在catch中重置中断标志， Thread.currentThread().interrupt();
try包在while循环外
在catch中break;

逸出

静态方式若操作了静态变量就会有线程安全问题
尽管方法内部考虑了线程安全，但方法的参数是引用类型时，也会产生线程安全问题

Hbase性能压测工具

发表于 2018-11-10 | 更新于 2019-06-09

PerformanceEvaluation源码阅读

近日在工作需要对集群的hbase做些简单的测试，所以接触了PerformanceEvaluation这个类，作为HBase自带的性能测试工具，其主要就是模拟多用户同时访问集群进行压测。

用法 & 主要参数

1	bin/hbase pe <options> <command> <nclients>

倒数第二个参数command为hbase提供的几种测试用例，最后一个参数为线程数

测试用例常用的有：

sequentialRead ———— 顺序读测试
sequentialWrite ———— 顺序写测试
randomRead ———— 随机读测试
randomWrite ———— 随机写测试
scan ———— 扫描 (读每一行)
scanRange10/100/1000 ———— 指定范围内随机扫描，返回10/100/1000个数据

主要参数有：

nomapred —— 使用MapReduce的方式启动多线程测试还是启动本地多线程的方式，通常使用本地多线程方式。如果没有安装MapReduce加上此参数表示不是mr
rows —— 指定每个线程处理的数据行数，总共测试行数等于线程数*rows
size —— 总测试的数据大小，单位为GB。这个参数与rows互斥，不要两个参数一起设。在使用RandomRead和RandomSeekScan测试时，这个size可以用来指定读取的数据范围。这个值在Read时非常重要，如果设的不好，会产生很多返回值为空的读，影响测试结果
valueSize —— 写入HBase的value的size，单位是Byte，默认1024字节
oneCon —— 多线程运行测试时，所有线程使用一个连接还是每个线程一个连接。默认值为false，每个thread都会启一个Connection，建议把这个参数设为True (涉及底层netty的线程模型，hbase2.0后可指定连接数)
presplit —— 表的预分裂region个数
inmemory —— 会将数据尽量放在内存中，默认是false，为了保证测试准确性，建议保持为false
table —— 测试表的名字，默认为TestTable
compress —— 指定压缩方式，默认是NONE
filterAll —— 加上此参数，则server端scan出来的结果不再返回给client端，用于单纯测试server端的性能
autoFlush —— 默认为false，即PE在写测试时用的是BufferedMutator，BufferedMutator会把数据攒在内存里，达到一定的大小再向服务器发送，如果想明确测单行Put的写入性能，建议设置为true。autoFlush为false会影响统计的准确性，因为在没有攒够足够的数据时，put操作会立马返回，根本没产生RPC，但是相应的时间和次数也会被统计在最终结果里 (源码中好像没有看到这个参数的作用？？)

源码解读

继承了Configured类，表示已被配置了Configuration文件，在PE的构造函数中调用了super(conf)，将配置文件保存了起来
在run方法中，对参数进行处理。这种处理参数的方法以后可以借鉴。将所有参数以空格分割，转成linkedList，再在一个方法中解析该list，每次poll一个参数进行判断赋值给TestOptions类保存参数。
并且通过这种方法控制命令行格式，若判断到一个参数为测试用例的其中一种，则下一个参数必须为线程数，最后在判断list是否为空。

从parseOpts方法中能看到，size参数和rows参数必须设置一个且只能设其一。如果指定size，这算出要测试的总行数再除以线程数，得到每个线程要操作的rowkey范围；若指定每个线程处理的行数，则同理求出size大小

TestOptions保存这全部的参数信息，并且提供了一个方法可以从一个TestOptions对象复制出另一个该对象的方法，供多线程测试时，每个线程维持一份不同的参数

通过反射构造出测试用例的类类型Class，所有测试用例类都通过TableTest继承Test，所以是Test的子类
runTest方法中，搜先是调用了checkTable方法来判断测试表是否需要重建，主要判断逻辑：
- 在只读测试中，必须指定一张存在的表
- 如果测试表存在，但与指定的region数不同，则要重建
- 如果是写测试，测试表的分区策略或副本数与指定参数不同，则也要重建
  目的就是为了提供一个与指定参数完全符合的测试环境，主要就是region数，分区策略和副本数要一致，这样测试结果才准确。最后根据nomapred决定是本地多线程测试还是启动mapreduce测试。
doLocalClients的主要逻辑是创建和线程数相同的Future对象用于取回测试结果，再创建一个线程池向提交n个线程。为每个线程复制一个TestOptions对象，以维持每个线程不同的参数，例如startRow。再调用runOneClient方法
runOneClient是每个线程单独处理的方法，通过传入的参数反射构造出Test测试用例类，再调用Test的test方法(这里使用了模板方法的设计模式)。最后返回RunResult对象，保存着这个线程的一些性能指标，返回出去可用于统计平均值和方法等总体性能指标。

注意的问题

在进行读测试之前要准备数据，建议使用SequentialWrite测试用例。

在SequentialWrite中，PE会给每个线程设置偏移量，保证0 ~ 9999这10000个行（会把所有数字扩展成26位等长的byte数组）一行不差地写入HBase。如果是RandomWriteTest，在每个线程中会随机生成一个0 ~ 9999之前的数字写入（–row=1000代表每个线程会写1000次）。由于是随机，会造成中间有些行没有写入，那么在读取测试时，读到的就是空行，影响测试结果。
建议使用–size参数而不是–rows

size参数指定后，具体执行多少行PE内部会自己去算。假设我这里填的是–row=1000，线程数是10，那么写入的数据范围是0~9999。当我在做RandomReadTest时，如果需要修改线程数，比如我想测20个线程并行读，那么数据读取的范围将是0 ~ (1000*(20-1))，很大一部分读是空读！你当然可以根据线程数来调整读测试时row变量的值，使读的整体范围不超过写入的数据范围，但是row的大小影响了整体测试的时间，而统一用size你就啥都不用管了。
在读测试时不要加关于表的任何参数，如presplit，如果加了PE会将表重建。valueSize和size的值要与准备数据时写测试用例的参数保持一致，PE靠这两个值来算数据的范围和行数。

内部类解读

Test是抽象类，提供了很多hook，类似模板方法供子类实现
比如：TableTest实现了Test的onStartup和onTakedown方法，控制每个测试用例Table对象的创建(Table对象的创建比较消耗hbase资源)；所有测试用例类都实现了testRow类方法，实现各自测试方法对每行数据的处理。所以从Test类基本能看到整个测试的流程

整个test方法调用链有三条：

test ——> testSetup:负责线程和连接的关系 ——> onStartup: 通过线程各自的连接得到table对象，由TableTest或BufferedMutatorTest实现
testTimed: 得到起止的rowkey ——> testRow：由每个测试用例类实现各自逻辑
testTakedonw ——> 打印性能指标，onTakedown：关闭table对象

其中RandomWriteTest和SequentialWriteTest这两个写测试用例继承BufferedMutatorTest,内部是一个BufferedMutator，用于异步批量写数据，实现大致和TableTest一样，只是把Tabel接口换成了BufferedMutator接口

Imcrement、Append和CheckAnd开头的测试类，有类似CAS操作，则继承了CASTest这个基类

##参考资料

单例模式整理

发表于 2018-07-12 | 更新于 2019-06-09

单例模式

单例模式

保证一个类在内存中只有一个实例，并提供一个全局访问点

饿汉式

class Singleton{
   /**
     在类内创建对象  
     静态，保证内存中只有一个
     私有，进行封装通过方法调用
    */
   private static Singleton s = new Singleton();  
                                            
   private Singleton(){}                       //私有化构造函数，对外不能创建对象

   public static Singleton getInstance(){      //公共静态方法，用类名调用
        return s;                              //Singleton s1 = Singleton.getInstance();
   }
}

懒汉式

class Singleton{

    private static Singleton s;   //懒汉模式，声明时未实例化

    private Singleton(){}

    public static Singleton getInstance(){
        if(s == null)           //存在线程安全问题
            s = new Singleton();
        return s;
    }
}

未实例化时，可能存在多个线程都通过判空s==null的情况，因此存在线程安全问题。

双重检查加锁
改进懒汉式线程安全问题，在创建对象前加同步锁Synchronized

class Singleton{

    private volatile static Single s = null; 
    
    private Singleton(){}
    
    public static Single getInstance(){
        if(s==null){                  
            synchronized (Single.class) {
                if(s==null){      
                     s = new Single();
                }
            }
        }
        return s;
    }
}

第一次判空防止实例化后，每次调用getInstance方法都会同步，提高性能
第二次判空防止未实例化时，多个线程通过第一次判断，进入等待。其中一个线程创建了对象后，另一个线程也能再一次创建对象，无法保证单例
volatile关键字防止因为JVM的指令重排而产生线程安全问题，保证指令执行的顺序

如：instance = new Singleton，会被编译器编译成如下JVM指令：

memory = allocate(); //1：分配对象的内存空间
ctorInstance(memory); //2：初始化对象
instance = memory; //3：设置instance指向刚分配的内存地址

但是这些指令顺序并非一成不变，有可能会经过JVM和CPU的优化，指令重排成下面的顺序：
memory = allocate(); //1：分配对象的内存空间
instance = memory; //3：设置instance指向刚分配的内存地址
ctorInstance(memory); //2：初始化对象

当线程A执行完1,3时，instance对象还未完成初始化，但已经不再指向null。此时如果线程B抢占到CPU资源，执
行if（instance == null）的结果会是false，从而返回一个没有初始化完成的instance对象。

加入volatile关键字时，生成的汇编代码会多出一个lock前缀指令，lock前缀指令实际上相当于一个内存屏障(也叫内存栅栏)，内存屏障会提供3个功能:
1.它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面，即在执行到内存屏障这句指令时，在它前面的操作已经全部完成；
2.它会强制将对缓存的修改操作立即写入主存；
3.如果是写操作，它会导致其他CPU中对应的缓存行无效
volatile不保证原子性，保证可见性和部分有序性

静态内部类

public class Singleton {
    private Singleton() {}

    public static Singleton getInstance(){
        return SingletonHolder.instance;
    }

    private static class SingletonHolder{
        private static Singleton instance = new Singleton();
    }  
}

instance对象是通过在调用getInstance方法时才实例化对象，通过ClassLoader的加载机制实现懒加载(加载外部类时，并不加载内部类)
线程安全，但能利用反射破坏单例

//获得构造器
Constructor con = Singleton.class.getDeclaredConstructor();
//设置为可访问
con.setAccessible(true);
//构造两个不同的对象
Singleton singleton1 = (Singleton)con.newInstance();
Singleton singleton2 = (Singleton)con.newInstance();
//验证是否是不同对象
System.out.println(singleton1.equals(singleton2));

单元素枚举

public enum ResourceEnum {
    INSTANCE;
    
    private Resource instance;
    
    ResourceEnum() {
        instance = new Resource();
    }
    public Resource getInstance() {
        return instance;
    }
}

// 需要单例的资源
class Resource{
}

调用方法：ResourceEnum.INSTANCE.getInstance()

枚举类的构造方法限制为私有，在访问枚举实例时会执行构造方法
每个枚举实例都是static final类型，只能被实例化一次
单例对象在枚举类加载时进行初始化，并非懒加载
能防止反射破坏单例
保证反序列化结果为同一对象

JVM在序列化时，只是将枚举对象的name属性输出到结果中，反序列化时通过java.lang.Enum的valueOf()方法根据名字查找枚举对象。因此反序列化后的对象和序列化前的对象实例相同。
其他单例模型要做到这点，必须实现readResolve()方法

谈谈一致性哈希算法

发表于 2018-03-16 | 更新于 2019-06-09

问题引入

传统数据库集群设计时的主要策略是，将数据的id通过哈希函数转换成一个哈希值key，然后对机器数量N取模，得到数据的存放位置。由此带来的问题是，当增加、删除机器或机器宕机时需要对所有数据id重新进行一遍哈希，然后进行大量的数据迁移。

为了解决分布式集群容量变化时带来的大量数据迁移问题，引入一致性哈希算法。

算法思想

把全量的缓存空间当作一个环形存储结构，环形空间总共分成2^32个区域。每个数据的id都可以通过hash函数转换成一个0~(2^32)-1的数字，并对应到环形空间的一个区域。每台机器也遵循相同hash算法，根据机器IP或域名映射到环形空间。
离每一个数据的哈希值key的顺时针方向最近的节点，负责存储该key的数据。实现将数据和节点对应起来。
(本文章多次引用了程序员小灰中的图片，侵删)
节点变化
当集群节点变化时，只会引起一小部分的数据迁移。
新增节点时的变化情况：

移除节点时的变化情况：

虚拟节点

当机器较少时，机器的哈希值很大可能不能均匀分布在哈希环上，就会出现负载不均衡的情况。

一致性哈希算法引入虚拟节点机制来解决这种数据倾斜的问题。即对每一台机器通过多个哈希函数映射到多个位置，这些位置上的节点称为虚拟节点。（也可以通过在IP或域名后增加编号后缀再通过同一哈希函数映射到不同位置）

在增加节点时，会打破原来负载均衡的情况，新增节点会从原有节点分流数据的情况。把新增一个物理节点拆分成多个虚拟节点并均匀分布在哈希环上可以有效解决这个问题。
在移除节点时，也会造成负载不均衡的情况。但当移除的物理节点已经被拆分成多个虚拟节点时，数据倾斜的情况也会减小很多。

注意：这是指的“数据迁移”实际是指key的路由情况。在数据库集群场景下，可以是根据key值决定数据存储位置，集群变化时根据key指定决定是否将该数据进行迁移；在服务应用集群场景下，可以是根据请求url进行分流。

代码实现

实现一致性哈希算法主要是考虑哈希环的数据结构，哈希环上存储的是机器的哈希值。当有数据需要路由时，查找哈希环上大于待路由数据哈希值且最小的值，即为该数据路由的目标机器。

考虑机器集群是动态变化的，因此数据结构不适合选择数组。适合的数据结构有List和树，下面分析两种实现方案：

List列表
将机器节点的hash值放入List，然后进行排序。待路由数据只需在List中找到第一个hash值大于它的机器节点即可。这样问题就变成了类似有序表查找。
- 查找的算法可以用：顺序查找O(N)、二分查找O(logN)、跳表O(logN)

因此，排序+查找时间复杂度总共为O(N*logN)

树
节点的hash值有自然顺序，并且要求查找时间复杂度低。因此可以使用二叉查找树作为保存节点hash值的数据结构。JDK的TreeSet和TreeMap提供了红黑树的实现。

谈谈Bloom Filter

发表于 2018-03-13 | 更新于 2019-06-09

布隆过滤器是一种多哈希函数映射的快速查找算法，实际由一个二进制向量和一系列hash函数组成。主要用于检索一个元素是否属于集合，但并不严格要求100%正确的场合。

优点：空间和时间效率上远超一般算法，适合大数据场景
缺点：存在一定误识别率(即假正例，False positives)，集合的元素删除困难

典型的应用场景有：

爬虫的url判重
垃圾邮件过滤
网页黑名单系统

算法思想

创建一个m位的BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对元素e哈希的结果记为h(i,e)，且h(i,e)的范围是0到m-1。

加入元素的过程
先对元素e分别计算k个哈希函数h(1,e)，h(2,e)，…，h(k,e)的值，然后将BitSet的h(1,e)，h(2,e)，…，h(k,e)为置为1。最后再加入到集合中。

(图片来源于网络，侵删)
检索元素是否存在
同样先对元素e分别计算k个哈希函数h(1,e)，h(2,e)，…，h(k,e)的值，然后检查BitSet的第h(1,e)，h(2,e)，…，h(k,e)是否为1。若其中任何一位不为1则判定该元素没有被记录过，若全部都为1则可认为元素存在。

注意：若元素对应的bit全为1，实际上不能100%肯定该元素被布隆过滤器记录，因为有可能该元素对于的所有bit刚好被其他元素覆盖。

删除过程
布隆过滤器是不支持删除操作的，因为删除会影响到其他元素的检索。但有一种Bloom Filter的变体Counting Bloomfilter支持删除操作，CBF实际是将Bloom Filter的每一位Bit改为一个计数器，添加时将对于位加1，删除时减1。

注意：删除时必须保证元素是在集合中的，这点单凭布隆过滤器无法判断，需要到集合中检索。

参数选择

如何根据预测输入元素n的级别和期望失误率p确定布隆过滤器bitSet的大小m和哈希函数的个数k。它们之间存在最优解的情况，直接给出公式
$$ m=-\frac{(n \times \ln p)} {(\ln2)^2} $$
$$ k=\ln 2 \times \frac {m} {n} $$
布隆过滤器的真实失误率为：
$$ p=(1-e^{-\frac {nk} {m}}) $$

源码实现

这是一个用Java简单实现的布隆过滤器Github。该实现能根据期望失误率和预测输入元素级别，计算最优参数构造布隆过滤器。

参考文章

程序员代码面试指南

LinkedList源码阅读笔记

发表于 2018-03-11 | 更新于 2019-06-08

源码版本JDK1.8.0_121

LinkedList内部是基于双向链表实现的，元素在内存中的存储并不是连续的，通过节点的引用来关联所有元素。优点和ArrayList相反，添加和删除元素比较快，查询和遍历效率低。

LinkedList类定义

1
2
3

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

从LinkedList类的定义可以看出：

支持泛型
继承AbstractSequentialList并实现了List接口，所以是一个有序列表
实现了Deque接口，可以作为双端队列操作 (能用作双端队列说明也可作为队列和栈)
实现了Cloneable接口，可以被克隆
实现了Serializable接口，并重写了序列化和反序列化方法

Node节点数据结构

private static class Node<E> {
    E item;  //当前节点的数据
    Node<E> next;  //后一个节点
    Node<E> prev;  //前一个节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

构造函数和成员变量

// 链表存储元素个数
transient int size = 0;
// 首节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList有两个构造函数，默认无参构造函数创建一个空链表。带参的构造函数传入一个集合，调用addAll方法将元素插入到链表。

注意： LinkedList的带参构造函数调用this()方法后，有可能有其他线程想链表插入数据，所以集合中的元素并不一定从链表首节点开始。

成员方法

addAll方法
构造函数中的addAll方法的调用链涉及三个主要函数

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在index位置插入集合元素
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); //越界检查

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // 创建第index个节点(即为要插入的第一个节点)的
    // 临时的前置和后置节点 
    Node<E> pred, succ;
    // 在链表尾部插入时，前置节点为last节点，后置节点为null
    if (index == size) {
        succ = null;
        pred = last;
    } else { // 在非尾部插入时，前置节点为第index个节点，后置节点为原来第index个节点的后置
        succ = node(index); //node()方法返回第index个节点
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o; //强转成指定泛型
        // 当前插入节点初始化
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果插入的节点的pred为null，则是首节点
        if (pred == null)
            first = newNode;
        else        
            pred.next = newNode;  // 尾插法，与前置节点相连
        // 一次插入完成后，将当前节点赋值给pred，作为下次插入的前置
        pred = newNode;
    }

    // 集合插入完成后，如果succ为null，则说上面遍历插入的最后一个节点为尾节点
    if (succ == null) {
        last = pred;
    } else {        //否则将遍历的最后一个节点和原链表的index位置相连
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

// 返回index位置上的节点
Node<E> node(int index) {
    // 折半查询，如果index小于size的一半，从前遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

再看其他add方法
add(E e)功能是在尾部添加元素，调用linkLast方法
add(int index, E element)功能是在index插入，同样调用的主要方法有linkLast和linkBefore

// 在末尾插入，实现和上面addAll中的代码相似
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// add内部调用 linkBefore(element, node(index));
// 功能是将e节点插入到succ节点之前
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

移除方法
移除方法常用有两个，一个是根据index移除，一个是根据object移除

public E remove(int index) {
    // 注意，这里检查的是有效下标  index < size   index从0开始记
    checkElementIndex(index);
    return unlink(node(index));
}

public boolean remove(Object o) {
    // 分移除数据是否为null处理
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 主要的方法，功能是移除一个节点
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    
    // 维护前置节点
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    // 维护后置节点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

此外还有没有任何参数的remove，removeFirst，removeLast方法，其都为Deque接口的实现，后面总结。

从上面分析的增删方法可以看出，基于首尾节点的增删操作都是O(1)复杂度；而非首尾操作要调用node()方法遍历链表，所以平均复杂度是O(n)。

查询get方法有get(index)，getFirst()，getLast()，
其中get(index)调用node()方法，经过折半优化；getFirst和getLast为Deque接口实现。
序列化
LinkedList自己重写序列化方法的原因和ArrayList一样，为了节省空间。如果将整个LinkedList会把Node节点给写入序列化，由于Node是双端链表的数据节点，会导致多浪费2倍的空间。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {

    s.defaultWriteObject();

    s.writeInt(size);

    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {

    s.defaultReadObject();

    int size = s.readInt();

    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());  //尾插
}

克隆
LinkedList的克隆也是浅克隆，即只克隆LinkedList并不克隆每个节点。

public Object clone() {
    // 克隆LinkedList本身
    LinkedList<E> clone = superClone();

    // clone的first和last会指向原本链表的first和last
    // 为了下面循环遍历添加元素，先置未null
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

public interface Deque<E> extends Queue<E> {
    
    // ***双端队列的方法***
    void addFirst(E e);
    void addLast(E e);
    E removeFirst();
    E removeLast();
    
    // 插入队列首尾，调用的是addFirst和addLast
    boolean offerFirst(E e);  //调用addFirst
    boolean offerLast(E e);   //调用addLast
   
    // 查看并移除，与remove*区别在于不会报异常
    E pollFirst();
    E pollLast();
    
    // 查看但不移除，不同处在于get*方法得到null会报NoSuchElementException异常，peek*不会
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***
    boolean add(E e);
    E remove();         //调用removeFirst。移除队首元素，与poll不同处在于移除null会报异常
    
    boolean offer(E e); //添加元素到队尾
    E poll();           //移除队首元素
    E element();        //查看队首元素，null会报异常
    E peek();           //查看队首元素

    // *** Stack methods ***
    void push(E e);  // 压栈
    E pop();         // 出栈
}

Deque接口小结：
队列提供的主要操作有offer、poll和peek，双端操作在方法名后加上后缀First和Last。
双端队列的移除方法有remove*和poll*，区别在于遇到null是否报异常；队列的方法同理
双端队列的查询方法有get*和peek*，区别在于遇到null是否报异常；队列的方法element和peek同理
队列和栈的增删操作调用的是addFirst/addLast/removeFirst/removeLast方法，它们又调用LinkedList的核心方法link/linkFirst/linkLast/unlink/unlinkFirst/unlinkLast。

迭代器

private class ListItr implements ListIterator<E> {
        // 前一个遍历过的节点
        private Node<E> lastReturned;
        // 下次遍历的节点
        private Node<E> next;
        // 下次遍历的节点下标
        private int nextIndex;
        private int expectedModCount = modCount;

        // 构造函数，指定从index开始遍历， 下标：0<=index<size
        ListItr(int index) {
            // index等于size时，next节点为null；下标index比size小1，所以nextIndex等于size
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
    }

ListItr不仅提供从任意节点开始向后变量的功能，也可以向前遍历，移除/修改前次遍历过的元素，在下次遍历指向的next节点前插入元素的功能。

参考文章
JDK8中LinkedList的工作原理剖析

ArrayList源码阅读笔记

发表于 2018-03-08 | 更新于 2019-06-08

源码版本JDK1.8.0_131

ArrayList内部是基于数组的动态管理来实现的，容量能自动增长，数组占据内存一块连续的存储空间，对于下标随机访问和遍历非常高效。

ArrayList类定义

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

从ArrayList类的定义可以看出：

支持泛型
继承AbstractList并实现了List接口，因此具有基本的增删查改功能
实现了RandomAccess接口，具有随机读写的功能。该接口是个标识接口
实现了Cloneable接口，可以被克隆
实现了Serializable接口，并重写了序列化和反序列化方法

成员变量

// 数组的默认容量
private static final int DEFAULT_CAPACITY = 10;

// 空数组，用于带指定容量参数的构造函数
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空数组，用于无参构造函数
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 数据存放的数组对象， elementData.length即为数组容量
// 在序列化过程中不参与序列化，由重写的序列化方法实现具体序列化过程
transient Object[] elementData; // non-private to simplify nested class access

// 数组中存放元素的个数， 应小于数组容量
private int size;

// 数组最大可存放元素个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

ArrayList有三种构造函数

//1.指定容量就分配指定容量大小的数组
//若指定大小为0用EMPTY_ELEMENTDATA赋值
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//2.默认构造函数，用DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//3.传入一个集合作为数组的数据
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

主要成员方法

添加

add方法有两种重载，一个是在数组末尾添加，一个是在指定位置添加元素

add(E e)的调用链涉及5个方法, 依次如下：

public boolean add(E e) {
    // 确定数组容量能否再添加一个元素
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;  // 将元素赋值给扩容后的size位置上，并size加1
    return true;
}

// 确定数组的容量
private void ensureCapacityInternal(int minCapacity) {
    // 如果数组为空，容量不能小于默认容量10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 表明对数组进行了结构性修改，遍历时涉及
    
    // 数组容量不足最小需求容量时，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容长度是增加原来数组的一半大小，1.5倍扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 判断扩容后是否符合最小容量，还不足则直接扩容至最小需求
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 判断扩容后大小是否超过上限
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
   
    // 复制原数组，并扩容数组大小至newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);  //判断下标是否在0到size之间

    ensureCapacityInternal(size + 1); 
    // 将elementData数组从index开始的size-index个元素往后移1位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //在指定位置插入新元素
    elementData[index] = element;
    size++;
}

modCount变量是父类AbstrcatList中的属性，表示list结构化修改的次数。于遍历器的fail-fast机制相关。
由于要对数组元素整体移动，因此在指定位置插入的操作比较耗性能。

addAll方法也有两种重载，与add方法相似。将集合追加到末尾和将集合插入到指定位置。
(实现方法基本相同，我不想这篇文章太过累赘，相似的代码就不帖出来了)

ArrayList每次在增加元素时，都会ensureCapacityInternal方法来确保容量足够。在容量不够时会调用Arrays.copyOf方法将原数组拷贝到新数组中，这是一个非常耗性能的操作。因此建议在确定元素数量时才使用ArraysList，否则建议使用LindedList。

移除

remove方法也有2种重载，一个是移除指定下标的元素，一个是指定元素移除其第一次出现

public E remove(int index) {
    rangeCheck(index);  // 越界检查

    modCount++;        // 移除操作也是对数组的结构性改动，不允许发生在遍历过程中
    E oldValue = elementData(index);

    int numMoved = size - index - 1; // 需要移动的元素个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // size减1，并让旧数组的末尾元素GC

    return oldValue;
}

public boolean remove(Object o) {
    // 分是否为null两种情况，过程大致一致
    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;
}

// 不进行越界检查，不返回被移除的元素
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; 
}

批量删除

// 删除与指定集合c中相同的元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

// 保留与指定集合c中相同的元素
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 遍历elementData数组
        for (; r < size; r++)
            // 通过compement来决定是否保留元素
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

此外，还有removeRange方法将指定范围内的元素移除。

修剪

作用是将数组对象的capacity减小到size长度，减少ArrayList对象占用的内存。

/**
 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 * list's current size.  An application can use this operation to minimize
 * the storage of an <tt>ArrayList</tt> instance.
 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

包含

// 利用indexOf方法判断是否包含某个元素
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

// 返回元素所在的下标，不存在则返回-1
// 与remove(Object o)方法相似
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

与indexOf方法相似的lastIndexOf方法，作用是从最后一个元素开始向前遍历。

克隆方法

Arraylist的克隆是浅克隆，即只产生ArrayList对象的副本，并不赋值元素本身

public Object clone() {
    try {
        // 调用父类的clone方法，产生ArrayList对象副本
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 对elementData数组进行拷贝(浅拷贝)
        // 将elementData的地址赋值给副本的elementData
        v.elementData = Arrays.copyOf(elementData, size);
        // 基本类型的值会拷贝，所以副本的modCount要置零
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

数组拷贝方法

Arrays.copyOf方法参数含义：（原数组，拷贝个数），返回拷贝的数组。
System.arraycopy方法，该方法是一个本地方法，通过调用系统的C/C++方法实现，实现数组之间的移动和复制。

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

序列化机制

ArrayList实现了Serializable接口，本身具备序列化的功能。那为什么ArrayList中存储数据的elementData数组要用transient修饰，并且重写writeObject和readObject方法？

分析源码，ArrayList重写的序列化方法其实就是把size和elementData数组中不为null的元素逐个写到流中，反序列化时在逐个读取。这么做的原因是因为数组每个扩容时，极端情况下会产生原来数组长度一半的为null的元素。在序列化时把这部分null排除出去，有助于提高性能

// wirteObject方法，for循环中遍历size大小而不是elementData.length
for (int i=0; i<size; i++) {
    s.writeObject(elementData[i]);
}

迭代机制

在进行ArrayList遍历时，可以调用iterator()方法返回一个迭代器，使用迭代器可以进行遍历操作。

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E>

iterator方法返回的Itr实例是ArrayList的内部类，实现了Iterator接口。

成员变量

1
2
3

int cursor;       // 指向迭代器下一个值的位置
int lastRet = -1; // 指向迭代器最后取出元素的位置，没进行遍历时为-1
int expectedModCount = modCount; //记录初始化迭代器时modCount的值

ArrayList的迭代器使用fail-fast机制，在调用add和remove方法时会使modCount++，modCount记录的是ArrayList发生结构性修改的次数。在调用迭代器的next方法时会检查modCount与expectedModCount是否相等，不等则抛出ConcurrentModificationException异常。
这么做的原因是防止在遍历的过程中由于修改操作，有可能造成ArrayIndexOutOfBoundsException，这样的异常属于设计ArrayList这种动态数组的缺陷，应从设计层面避免。
举个栗子：

   // 用户代码
   ArrayList<String> list = new ArrayList<String>();
   list.add("a");
   Iterator<String> iterator = list.iterator();
       while(iterator.hasNext()){
           String next = iterator.next();
           if("a".equals(next))
               list.remove(next);   
   }
   
   // 迭代器的hasNext方法
   public boolean hasNext() {
       return cursor != size();  // 注意这里的判断条件是游标cursor不等于size
}

list中只有一个元素，在remove时cursor为1，size已经为0。下一次调用hasNext方法会继续遍历，但数组有可能已经越界了。
这里有一个疑问，为什么hasNext方法的判断条件不写成cursor <= size()呢？暂时还没答案，等有更深入理解后再补充吧

还有一种特殊情况这里也记录一下，在遍历时用ArrayList的remove方法(注意并不是iterator提供的remove方法)移除元素，并不会报ConcurrentModificationException

// 用户代码
ArrayList<String> list = new ArrayList<String>();
list.add("a");
list.add("b");   
Iterator<String> iterator = list.iterator();
    while(iterator.hasNext()){
        String next = iterator.next();
        if("a".equals(next))   //移除的是倒数第二个元素
            list.remove(next);   
}

当移除的是ArrayList中倒数第二个元素时，remove后curosor的值是原来的size-1，而此时size也变为跟curosor相等。所以当下次遍历调用hasNext方法会结束遍历，并不会继续调用next方法，所以不会去检查modCount，也就不会报异常。

成员方法

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;
    // 记录lastRet，返回元素
    return (E) elementData[lastRet = i];
}

// 迭代器内部的remove方法，移除当前遍历到的元素(lastRet指向的)
public void remove() {
    // 还没进行遍历
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        // 调用的是ArrayList的remove方法
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        // lastRet置为-1，所以不能连续remove
        lastRet = -1;
        // 不会报异常
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

总结

ArrayList非线程安全，只能应用在单线程环境下。
多线程情况下，JDK提供有Vector、Collections.SynchronizedList(List list)。推荐JDK并发包的CopyOnWriteArrayList，Guava和Apache Common等提供的线程安全的List。

第一次写技术博客，想法由来已久，与其说是技术博客，不如算是对自己知识的回顾与总结。
写的过程中，发现很久知识已经生疏，整理的时候又有新的认识。
过程中也查了很多资料，借鉴了下面两篇文章，在这里向作者表达感谢。

参考资料

微信公众号：我是攻城师
 tinylcy.me

JJz

A place where JJz wirting