CAS（Compare and Swap）和 ConcurrentHashMap 经常绑在一起问：一个是硬件级的无锁更新，一个是并发 Map 怎么既线程安全又比整表锁更快。
JDK 5 之前同步几乎全靠 synchronized：竞争时上下文切换多、持锁会把别人挂起、还可能优先级倒置。volatile 能保证可见性，但不保证复合操作的原子性，所以还是要回到「锁」——只不过乐观锁用的是 CAS，而不是独占。
一、悲观锁、乐观锁与 CAS
| 类型 |
做法 |
典型 |
| 悲观 / 独占 |
先抢锁，别人等着；持锁线程不放，其余全挂起 |
synchronized |
| 乐观 |
先假设没冲突做完，失败就重试直到成功 |
CAS / compareAndSet |
CAS 三个操作数
内存位置 V、预期原值 A、新值 B。若 V 仍等于 A，处理器原子地把 V 改成 B；否则不动。无论成败都会带回该位置当前值（有的变体只返回成功与否）。口语就是：我认为 V 里是 A；若是，就写成 B；否则告诉我现在是多少。
常见用法：从 V 读出 A，算出 B，再用 CAS 把 V 从 A 改成 B。别人若已改过，CAS 失败，算法重算即可。Intel 上对应 cmpxchg；Java 早期用不上这些指令，有了 JNI 之后，Doug Lea 的 concurrent 包才把 CAS 当成整包基石。
AtomicInteger 怎么无锁 +1
没有锁时，值本身仍要 volatile，保证读到的是共享的最新值：
private volatile int value;
public final int get() {
return value;
}
incrementAndGet 是典型的自旋 CAS：
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
compareAndSet 经 JNI 落到 CPU 指令：
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
非阻塞算法的要求是：一个线程失败或挂起，不该拖死别的线程。compareAndSet 正是用硬件更新 + 冲突检测，代替整段加锁。
二、ConcurrentHashMap 的设计
并发里 ConcurrentHashMap 比 Hashtable 和 Collections.synchronizedMap() 写并发更好，代价是放宽了读的强一致性。
| 版本 |
锁策略 |
结构 |
| JDK 7 |
分段锁 Segment：同段才竞争，不同段不抢 |
段数组 + 链表 |
| JDK 8 |
去掉 Segment，节点上 CAS / synchronized，扩容也靠 CAS |
数组 + 链表 + 红黑树，另有 TreeBin、Traverser 等辅助类 |
三、接口限流里的计数陷阱
统计 URL 调用次数，第一反应常是 ConcurrentHashMap<String, Long>。下面这段没显式加锁，输出却经常对不上：
public class CounterDemo1 {
private final Map<String, Long> urlCounter = new ConcurrentHashMap<>();
//接口调用次数+1
public long increase(String url) {
Long oldValue = urlCounter.get(url);
Long newValue = (oldValue == null) ? 1L : oldValue + 1;
urlCounter.put(url, newValue);
return newValue;
}
//获取调用次数
public Long getCount(String url){
return urlCounter.get(url);
}
public static void main(String[] args) {
ExecutorService executor = Executors.newFixedThreadPool(10);
final CounterDemo1 counterDemo = new CounterDemo1();
int callTime = 100000;
final String url = "http://localhost:8080/hello";
CountDownLatch countDownLatch = new CountDownLatch(callTime);
//模拟并发情况下的接口调用统计
for(int i=0;i<callTime;i++){
executor.execute(new Runnable() {
@Override
public void run() {
counterDemo.increase(url);
countDownLatch.countDown();
}
});
}
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
executor.shutdown();
//等待所有线程统计完成后输出调用次数
System.out.println("调用次数："+counterDemo.getCount(url));
}
}
console output：
调用次数：96526
ConcurrentHashMap 保证的是 单个 get/put/delete 原子，increase 却是 get 再 put 的组合，多线程会互相覆盖。给整个方法加锁又浪费了并发容器。
ConcurrentMap.replace(key, old, new) 才是原子 CAS：
/**
* Replaces the entry for a key only if currently mapped to a given value.
* This is equivalent to
*
* if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {
* map.put(key, newValue);
* return true;
* } else
* return false;
* }
*
* except that the action is performed atomically.
*/
boolean replace(K key, V oldValue, V newValue);
旧值被别人改过，replace 失败；循环里拿最新值再试，就能计准。首次还要用 putIfAbsent 做初始化：
public long increase2(String url) {
Long oldValue, newValue;
while (true) {
oldValue = urlCounter.get(url);
if (oldValue == null) {
newValue = 1l;
//初始化成功，退出循环
if (urlCounter.putIfAbsent(url, 1l) == null)
break;
//如果初始化失败，说明其他线程已经初始化过了
} else {
newValue = oldValue + 1;
//+1成功，退出循环
if (urlCounter.replace(url, oldValue, newValue))
break;
//如果+1失败，说明其他线程已经修改过了旧值
}
}
return newValue;
}
console output：
调用次数：100000
/** If the specified key is not already associated
* with a value, associate it with the given value.
* This is equivalent to
*
* if (!map.containsKey(key))
* return map.put(key, value);
* else
* return map.get(key);
* }
value 不能为 null。也可以换成 AtomicLong / AtomicLongMap，计数更直：
private AtomicLongMap<String> urlCounter3 = AtomicLongMap.create();
public long increase3(String url) {
long newValue = urlCounter3.incrementAndGet(url);
return newValue;
}
public Long getCount3(String url) {
return urlCounter3.get(url);
java.util.concurrent.atomic 把常用类型包一层原子方法。参考：乐观锁与悲观锁、ConcurrentHashMap、CHM 总结、并发实践。
一句话总结：CAS 用「比较再交换」在硬件上完成无锁更新；ConcurrentHashMap 保证的是单次操作线程安全，组合更新必须自己用 replace/putIfAbsent 自旋，或直接上 AtomicLongMap。
