一、ArrayList 的线程不安全的问题要理解ArrayList为什么线程不安全我们必须扒开它的源码看看在 CPU 眼里它到底是怎么运作的。ArrayList的底层本质极其简单它就是一个普通的数组Object[] elementData加上一个记录当前元素数量的整数int size。它内部没有任何像synchronized或Lock这样的保护机制。当我们在代码里调用arrayList.add(数据)时它的核心源码简化后只有两行public boolean add(E e) { // 1. 检查内部数组的容量是否足够不够就触发扩容 ensureCapacityInternal(size 1); // 2. 把新元素放到数组的当前 size 位置然后把 size 加 1 elementData[size] e; return true; }问题就出在第 2 步的elementData[size] e;。在 CPU 执行指令时这行代码绝对不是“一步到位”的不是原子操作它会被拆分成三个微小的底层步骤读读取当前size的值。写把新元素e存入数组的elementData[size]位置。加把size的值加 1写回内存。正因为这三步可以被随时打断在多线程并发时会引发两个极其经典的灾难。1-1、灾难现场一数据被覆盖丢失值被吞了假设当前ArrayList里面有 5 个元素也就是说当前的size 5。现在有线程 A和线程 B同时执行add()操作。底层并发执行轨迹线程 A执行到“写”这一步它把自己的数据放到了elementData[5]的位置。此时还没来得及把size变成 6。【CPU 发生切换】CPU 暂停了 A切到了线程 B。线程 B去内存里读size因为 A 还没改B 读到的size依然是5。线程 B执行“写”操作它也把自己的数据放到了elementData[5]的位置。结果线程 A 刚刚写进去的数据被线程 B 无情地覆盖抹除了线程 B 接着执行“加”操作把size改成了6。CPU 切回线程 A线程 A 从刚才被打断的地方继续执行它也执行“加”操作把size强制改成了7。最终诡异的后果你明明向集合里add了两次但数组的第 5 个位置只存了 B 的数据A 的数据丢失了。更诡异的是size变成了 7这意味着数组的第 6 个位置elementData[6]是空的值为null。这就导致了集合内部出现了数据空洞和错乱。1-2、灾难现场二数组越界异常直接崩溃这个灾难发生在第 1 步的“容量检查”环节。假设ArrayList底层的数组总长度是 10现在已经装了 9 个元素size 9。也就是说只剩最后 1 个空位了。此时线程 A和线程 B同时进来执行add()。底层并发执行轨迹线程 A执行第 1 步ensureCapacityInternal(9 1)。发现 10 个容量刚好够装不需要扩容。【CPU 发生切换】CPU 暂停了 A切到了线程 B。线程 B也执行第 1 步ensureCapacityInternal(9 1)。因为 A 还没把数据放进去size还是 9B 也发现容量够装不需要扩容。线程 A恢复执行开始塞数据把数据塞进elementData[9]然后size变成了10。此时数组已经完完全全装满了。线程 B继续执行它之前已经检查过认为不需要扩容于是它直接去塞数据准备把数据塞进elementData[10]。最终诡异的后果数组的下标是从 0 开始的长度为 10 的数组最大下标是 9。线程 B 强行往elementData[10]里写数据内存瞬间越界。JVM 会立刻抛出极其著名的ArrayIndexOutOfBoundsException数组越界异常导致你的业务线程直接崩溃。总结ArrayList为了追求极致的单线程读写速度完全剥离了锁的开销。在并发环境下多个线程同时去读写它内部那个共享的size变量和底层的elementData数组时没有排队机制必然导致数据被互相覆盖或者因为跳过了扩容机制而引发数组越界崩溃。在企业级开发中如果在多线程环境下需要用到 List绝对不能直接用ArrayList。如果是写多读多的普通场景我们会用Collections.synchronizedList(new ArrayList())把方法全部锁住。如果是读多写少比如系统配置列表、黑名单列表我们会使用并发包里的CopyOnWriteArrayList。二、HashMap的底层原理2-1、无序性HashMap中的 key 是绝对无序的它绝对不会按照你put的顺序来保存数据。不仅你刚放进去的时候是无序的甚至在程序运行的过程中它的顺序还会发生动态改变。第一步HashMap底层是怎么存数据的HashMap的底层本质上是一个数组默认长度是 16。你可以把它想象成一排连续的 16 个内存坑位。当你调用put(key, value)时HashMap根本不关心这是你第几个放进来的数据它只关心一件事这个数据该落到数组的哪一个坑位里它的核心寻址逻辑如下算哈希值它会调用 key 的hashCode()方法算出一个整数。比如hash(Alice) 23456。算数组下标它用这个哈希值和当前数组的长度做一个位运算相当于取模运算算出一个范围在 0 到 15 之间的下标。假设算出来是5。落位无论这是你第几个插入的数据它都会直接被塞进数组下标为5的位置。第二步为什么插入顺序会被彻底打乱假设我们按顺序执行以下三行代码HashMapString, String map new HashMap(); map.put(Alice, 111); // 第 1 个插入 map.put(Bob, 222); // 第 2 个插入 map.put(Cindy, 333); // 第 3 个插入在 CPU 的计算下底层的落位可能是这样的算 Alice 的下标得出5放在elementData[5]。算 Bob 的下标得出1放在elementData[1]。算 Cindy 的下标得出14放在elementData[14]。当你使用for循环去遍历打印这个 Map 时遍历的底层逻辑是从数组的下标 0 一直往下循环到 15。所以它最先碰到的是下标1里的 Bob然后是下标5里的 Alice最后是 Cindy。打印出来的顺序变成了Bob - Alice - Cindy。你原本的插入顺序被哈希算法的随机性彻底撕碎了。第三步更极端的现象 —— 顺序甚至会中途改变扩容机制这还不是最糟的。在HashMap中顺序不仅不按put来它还是动态变化的。HashMap底层有一个机制叫扩容Resize。当数组里的数据塞得太满默认超过容量的 75%时为了防止哈希冲突太严重HashMap会申请一个比原来大一倍的新数组比如从 16 扩容到 32。扩容时会发生什么它会把老数组里的所有数据拿出来重新计算一次下标塞到新数组里。原本在老数组下标5的 Alice重新计算后可能跑到了新数组的下标21。原本在下标14的 Cindy计算后可能还在下标14。这就意味着只要触发了扩容你昨天遍历HashMap打印出来的顺序跟今天打印出来的顺序可能会完全不一样第四步如果没有它有什么弊端为什么非要这么设计你可能会问既然这么乱为什么 Java 还要设计这种数据结构因为极致的查询速度。如果不做哈希运算而是按你put的顺序把数据挨个排成一列就像 ArrayList 或 LinkedList当你想去查map.get(Cindy)的时候程序必须从头开始一个一个字符串去比对直到找到为止。如果里面有 100 万条数据最差的情况要比对 100 万次。时间复杂度是 O(N)。而HashMap通过哈希算法直接算出了 Cindy 就在下标14。它直接一步跨到内存的那个位置把数据拿出来。时间复杂度是 O(1)。它是牺牲了“顺序”换取了“极速的随机读写性能”。终极解法如果你在业务里非要保持put顺序怎么办在很多业务场景比如你在内存里缓存了一批菜单希望在页面上按你的加载顺序显示我们既想要 HashMap 的查询极速又想要保持插入的顺序。这时候你应该抛弃普通的HashMap去使用它的子类LinkedHashMap。LinkedHashMap的底层依然有那个哈希数组保证查询速度。但它在代码层面多做了一件事它在后台偷偷地给每一个落位的节点加上了before前驱和after后继两个指针硬生生地把那些散落在数组各处的节点用一条双向链表串在了一起。当你去遍历LinkedHashMap时它不再去傻傻地循环那个哈希数组而是顺着这条额外加上的双向链表去遍历。这样就完美地还原了你当初put进来的顺序。2-2、底层数据结构与JDK8 的优化——红黑树【问题】在 HashMap 的底层原理中如果两个完全不同的 key 通过哈希公式算出了同一个数组下标也就是发生了哈希冲突HashMap 会怎么处理存进去的数据会被覆盖吗明确地回答你如果是两个不同的 Key 算出了相同的下标存进去的数据绝对不会被覆盖。在计算机科学中不同的输入数据经过哈希计算后得出相同的结果这被称为哈希冲突Hash Collision。这是不可避免的必然现象。为了完美地处理这种冲突Java 的HashMap经历过一次极其重要的底层代码重构从 JDK 7 到 JDK 8。我们纯粹从内存数据结构的角度一步步来看看它是怎么兜底的。第一阶段基础解法 —— “拉链法”单向链表你可能以为HashMap的底层数组里直接存的是你要放的Value。其实不是。数组的每一个坑位里存放的是一个Node节点对象。这个对象内部有四个极度重要的属性int hash(当前 Key 的哈希值)K key(真正的 Key)V value(真正的 Value)Node next(一个指向下一个节点的内存指针)当冲突发生时底层的执行轨迹你执行put(Alice, 111)。哈希算出来下标是5。此时elementData[5]是空的系统直接把 Alice 包装成一个 Node 丢进这个坑位。你执行put(Bob, 222)。哈希算出来下标恰好也是5。系统去elementData[5]一看发现里面已经住着 Alice 了。【核心动作】系统会去调用 Alice 的equals()方法跟 Bob 对比一下。发现 Alice 和 Bob 不是同一个字符串。既然不是同一个 Key绝对不能覆盖。系统会把 Bob 也包装成一个 Node然后让 Alice 节点里的next指针指向 Bob 这个新节点。结果在数组的下标5这个位置不再是一个单一的数据而是形成了一条单向链表Alice - Bob。(注如果你再去put(Alice, 333)系统依然会算出下标 5然后遍历链表用equals()发现存在一模一样的 Key这时候才会把 111覆盖成 333。)第二阶段怎么把数据准确无误地取出来既然下标 5 的位置串成了一根链表那执行get(Bob)时系统怎么知道哪个是 Bob 的数据查询轨迹算哈希定位到下标5。拿到下标 5 排在第一位的 Node也就是 Alice。比较if (Alice的Key.equals(Bob))。结果为false。顺着 Alice 的next指针往下找拿到下一个 NodeBob。比较if (Bob的Key.equals(Bob))。结果为true。成功把 Bob 节点里存的value222返回。这就是为什么在 Java 中有一条铁律重写对象的hashCode()方法时必须同时重写equals()方法。因为哈希值只负责帮你找到“属于哪个数组下标”而equals()负责在发生冲突的链表中精确地找出“到底哪一个是你的数据”。第三阶段遭遇性能绝境与 JDK 8 的终极进化用单向链表解决冲突逻辑上很完美但在极端的并发和海量数据场景下暴露出了致命的性能漏洞。绝境推演假设你的哈希算法写得很烂或者黑客在恶意攻击你的服务器故意构造了 10,000 个能算出同一个哈希值的不同 Key。当你把这 10,000 个数据全put进去后HashMap其他 15 个数组坑位全空着唯独某一个坑位里挂着一条长达 10,000 个节点的链表当你去get最后一个节点时系统必须从头开始比对顺着指针往下爬 10,000 次。后果HashMap引以为傲的 O(1) 极速查询性能被彻底摧毁退化成了 O(N) 的线性级慢速查询。JDK 8 的重构红黑树的引入为了防止链表过长导致性能崩溃JDK 8 的底层代码中加入了一个阈值TREEIFY_THRESHOLD 8。现在的运转逻辑变成了这样冲突了继续在链表尾部挂载新节点。每次挂载完系统都会检查这条链表的长度。如果这条链表的长度达到了 8 个节点并且整个 HashMap 的数组总长度已经达到了 64。【底层变异】HashMap会瞬间把这条普通的单向链表撕裂并重构成一种极其复杂的数据结构红黑树Red-Black Tree。为什么换成树在一条长度为 10,000 的链表里找数据最差要找 10,000 次。而在包含 10,000 个节点的红黑树里找数据依靠二分查找的逻辑最多只需要查找约 14 次时间复杂度从 O(N) 瞬间被优化到了 O(log N)。总结当HashMap发生哈希冲突时底层的演进逻辑是少量冲突采用“数组 单向链表”兜底。数据不会覆盖而是追加到链表尾部。海量冲突采用“数组 红黑树”兜底。当链表长度超过 8 时动态转为树结构强行保住查询性能的下限。