Java源码分析：深入探讨Iterator模式——迭代器模式
引言java.util 包中包含了一系列重要的集合类。本文将从源码分析入手，深入研究集合类的内部结构，以及遍历集合的迭代器模式（Iterator Pattern）的源码实现内幕。我们将先讨论根接口 Collection，然后分析抽象类 AbstractList 及其对应的 Iterator 接口，仔细研究迭代器模式的实现原理。说明：本文讨论的源代码版本基于 JDK 1.4.2。JDK 1.5 及后续版本在 java.util 中引入了泛型（Generics），为了简化问题并聚焦核心原理，本文主要讨论 1.4 版本的代码逻辑，但核心设计思想在后续版本中依然适用。集合类的根接口 CollectionCollection 接口是所有集合类的根类型。它的一个主要接口方法如下：boolean add(Object o)add() 方法用于添加一个新元素。注意该方法返回一个 boolean 值，但返回值不是表示添加成功与否。仔细阅读文档可以看到，Collection 规定：如果一个集合拒绝添加这个元素（无论任何原因），都必须抛出异常。返回值表示的意义是：add() 方法执行后，集合的内容是否改变了（即元素有无数量、位置等变化），具体行为由实现类决定。即：如果方法出错，总会抛出异常；返回值仅仅表示该方法执行后这个 Collection 的内容有无变化。类似的方法还有：boolean addAll(Collection c); boolean remove(Object o); boolean removeAll(Collection c); boolean retainAll(Collection c);Object[] toArray() 方法很简单，把集合转换成数组返回。Object[] toArray(Object[] a) 方法则稍微复杂一些：返回的 Object[] 仍然是把集合的所有元素变成的数组，但是类型和参数 a 的类型是相同的。例如执行：String[] o = (String[])c.toArray(new String[0]);得到的 o 实际类型是 String[]。如果参数 a 的大小装不下集合的所有元素，返回的将是一个新的数组。如果参数 a 的大小能装下集合的所有元素，则返回的还是 a，但 a 的内容用集合的元素来填充。尤其要注意的是，如果 a 的大小比集合元素的个数还多，a 后面的部分全部被置为 null。最后一个最重要的方法是 iterator()，返回一个 Iterator（迭代器），用于遍历集合的所有元素。使用 Iterator 模式遍历集合Iterator 模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。例如，如果没有使用 Iterator，遍历一个数组的方法是使用索引：for(int i = 0; i < array.size(); i++) { // TODO: get(i) ... }而访问一个链表（LinkedList）又必须使用 while 循环：while((e = e.next()) != null) { // TODO: e.data() ... }以上两种方法客户端都必须事先知道集合的内部结构，访问代码和集合本身是紧耦合，无法将访问逻辑从集合类和客户端代码中分离出来。每一种集合对应一种遍历方法，客户端代码无法复用。更严重的是，如果以后需要把 ArrayList 更换为 LinkedList，则原来的客户端代码必须全部重写。为解决以上问题，Iterator 模式总是用同一种逻辑来遍历集合：for(Iterator it = c.iterator(); it.hasNext(); ) { // ... }奥秘在于客户端自身不维护遍历集合的“指针”，所有的内部状态（如当前元素位置，是否有下一个元素）都由 Iterator 来维护。而这个 Iterator 由集合类通过工厂方法生成，因此，它知道如何遍历整个集合。客户端从不直接和集合类打交道，它总是控制 Iterator，向它发送“向前”、“向后”、“取当前元素”的命令，就可以间接遍历整个集合。首先看看 java.util.Iterator 接口的定义：public interface Iterator { boolean hasNext(); Object next(); void remove(); }依赖前两个方法就能完成遍历，典型的代码如下：for(Iterator it = c.iterator(); it.hasNext(); ) { Object o = it.next(); // 对 o 的操作... }在 JDK 1.5 中，还对上面的代码在语法上作了简化（增强型 for 循环）：// Type 是具体的类型，如 String for(Type t : c) { // 对 t 的操作... }每一种集合类返回的 Iterator 具体类型可能不同，Array 可能返回 ArrayIterator，Set 可能返回 SetIterator，Tree 可能返回 TreeIterator。但是它们都实现了 Iterator 接口，因此，客户端不关心到底是哪种 Iterator，它只需要获得这个 Iterator 接口即可，这就是面向对象的威力。Iterator 源码剖析让我们来看看 AbstractList 如何创建 Iterator。首先 AbstractList 定义了一个内部类（inner class）：private class Itr implements Iterator { ... }而 iterator() 方法的定义是：public Iterator iterator() { return new Itr(); }因此客户端不知道它通过 Iterator it = a.iterator() 所获得的 Iterator 的真正类型。现在我们关心的是这个声明为 private 的 Itr 类是如何实现遍历 AbstractList 的：private class Itr implements Iterator { int cursor = 0; int lastRet = -1; int expectedModCount = modCount; }Itr 类依靠 3 个 int 变量（还有一个隐含的 AbstractList 的引用）来实现遍历：cursor：是下一次 next() 调用时元素的位置，第一次调用 next() 将返回索引为 0 的元素。lastRet：记录上一次游标所在位置，因此它总是比 cursor 少 1。expectedModCount：表示期待的 modCount 值，用来判断在遍历过程中集合是否被修改过。变量 cursor 和集合的元素个数决定 hasNext()：public boolean hasNext() { return cursor != size(); }方法 next() 返回的是索引为 cursor 的元素，然后修改 cursor 和 lastRet 的值：public Object next() { checkForComodification(); try { Object next = get(cursor); lastRet = cursor++; return next; } catch(IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } }AbstractList 包含一个 modCount 变量，它的初始值是 0，当集合每被修改一次时（调用 add，remove 等方法），modCount 加 1。因此，modCount 如果不变，表示集合内容未被修改。Itr 初始化时用 expectedModCount 记录集合的 modCount 变量，此后在必要的地方它会检测 modCount 的值：final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }如果 modCount 与一开始记录在 expectedModCount 中的值不等，说明集合内容被修改过，此时会抛出 ConcurrentModificationException。这个 ConcurrentModificationException 是 RuntimeException，不要在客户端捕获它。如果发生此异常，说明程序代码的编写有问题，应该仔细检查代码而不是在 catch 中忽略它。但是调用 Iterator 自身的 remove() 方法删除当前元素是完全没有问题的，因为在这个方法中会自动同步 expectedModCount 和 modCount 的值：public void remove() { ... AbstractList.this.remove(lastRet); ... // 在调用了集合的 remove() 方法之后重新设置了 expectedModCount expectedModCount = modCount; ... }要确保遍历过程顺利完成，必须保证遍历过程中不更改集合的内容（Iterator 的 remove() 方法除外）。因此，确保遍历可靠的原则是只在一个线程中使用这个集合，或者在多线程中对遍历代码进行同步。示例与总结最后给个完整的示例：Collection c = new ArrayList(); c.add("abc"); c.add("xyz"); for(Iterator it = c.iterator(); it.hasNext(); ) { String s = (String)it.next(); System.out.println(s); }如果你把第一行代码的 ArrayList 换成 LinkedList 或 Vector，剩下的代码不用改动一行就能编译，而且功能不变。这就是针对抽象编程的原则：对具体类的依赖性最小。版本说明：本文基于 JDK 1.4.2 源码分析，未涉及泛型特性。现代 Java 开发中建议使用泛型集合（如 List<String>）及增强型 for 循环，但迭代器底层原理（包括 fail-fast 机制）依然保持一致。
前言在 JDK 1.8 中，AbstractQueuedSynchronizer（简称 AQS）拥有众多子类，如下图所示：可以看到，公平锁与非公平锁（包括 ReentrantLock）都是基于 AQS 实现的。公平锁（Fair Lock）：线程抢占锁的顺序严格按照调用 lock 方法的先后顺序，依次获取锁。非公平锁（Unfair Lock）：线程抢占锁的顺序不定。线程尝试获取锁时，无论是否有其他线程在等待，都先尝试直接获取。若失败则加入等待队列。这意味着后来者可能“插队”成功（但因为抢占锁失败而加入到等待队列的线程不能参与下一次抢占，直到被 unpark）。AQS 核心结构AQS 通过内置的 FIFO 同步队列来完成资源获取线程的排队工作。如果当前线程获取同步状态失败（即获取锁失败），AQS 会将当前线程及等待状态等信息构造成一个节点（Node）并加入同步队列，同时阻塞当前线程。当同步状态释放时，则会把节点中的线程唤醒，使其再次尝试获取同步状态。类结构public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable { protected AbstractQueuedSynchronizer() { } // 同步器队列头结点 private transient volatile Node head; // 同步器队列尾结点 private transient volatile Node tail; // 同步状态（当 state 为 0 时，无锁；当 state > 0 时，说明有锁） private volatile int state; // 获取锁状态 protected final int getState() { return state; } // 设置锁状态 protected final void setState(int newState) { state = newState; } // ... 其他方法 }通过 AQS 的类结构可以看到，其内部核心包含一个队列和一个 state 变量：队列：通过双向链表实现，用于存储等待获取锁的线程。state：锁的状态标志。volatile 关键字：head、tail 和 state 都是 volatile 类型的变量，保证了多线程环境下的内存可见性。同步队列的基本结构如下：Node 节点结构static final class Node { static final Node SHARED = new Node(); static final Node EXCLUSIVE = null; // 表示当前的线程被取消 static final int CANCELLED = 1; // 表示当前节点的后继节点包含的线程需要运行，也就是 unpark static final int SIGNAL = -1; // 表示当前节点在等待 condition，也就是在 condition 队列中 static final int CONDITION = -2; // 表示当前场景下后续的 acquireShared 能够得以执行 static final int PROPAGATE = -3; // 表示节点的状态。默认为 0，表示当前节点在 sync 队列中，等待着获取锁 volatile int waitStatus; // 前驱节点 volatile Node prev; // 后继节点 volatile Node next; // 获取锁的线程 volatile Thread thread; // 存储 condition 队列中的后继节点 Node nextWaiter; }Node 节点中除了存储当前线程、节点类型、队列中前后元素的引用外，还有一个关键变量 waitStatus。该变量用于描述节点的状态。由于 AQS 队列中存在并发，队列中会存取一定数量的节点，每个节点代表了一个线程的状态。有的线程可能因超时或中断需要放弃竞争（取消），有的线程在等待条件满足（Condition）。因此需要一个变量来描述这些状态，waitStatus 主要有以下几种状态：static final int CANCELLED = 1; static final int SIGNAL = -1; static final int CONDITION = -2; static final int PROPAGATE = -3;CANCELLED (1)：因为超时或者中断，节点会被设置为取消状态。被取消状态的节点不应再去竞争锁，只能保持取消状态不变，不能转换为其他状态。处于这种状态的节点会被踢出队列，最终被 GC 回收。SIGNAL (-1)：表示这个节点的后继节点被阻塞了。当自己释放锁或取消的时候，需要通知（unpark）后继节点。CONDITION (-2)：表示这个节点在条件队列中，因为等待某个条件而被阻塞。它不会被作为同步节点直到其状态被置为 0。PROPAGATE (-3)：使用在共享模式下，头结点有可能处于这种状态，表示锁的下一次获取可以无条件传播。0 (None)：新结点会处于这种状态，表示正常等待中。应用之——公平锁公平锁的获取锁公平锁的 lock 方法直接调用 AQS 的 acquire 方法：final void lock() { acquire(1); }进入 AQS 的 acquire 方法：public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); // 自己给自己设置了一个中断标志，只有之前被中断过，前面才会返回 true，这里相当于重新设置一个中断标志 }从方法语义上看，尝试获取一把锁。如果获取不到（tryAcquire 返回 false），则尝试将该线程封装成 Node 对象放入等待队列中（利用 && 实现了短路性质）。tryAcquire 方法在 AQS 中是留空的，留给子类实现：protected boolean tryAcquire(int arg) { throw new UnsupportedOperationException(); }设计理念：既然要给子类实现，通常应该用抽象方法。但是 Doug Lea 没有这么做，原因是 AQS 有两种功能（独占与共享），面向两种使用场景。如果都需要给子类定义的方法都是抽象方法，会导致子类无论如何都需要实现另外一种场景的抽象方法，这对子类来说是不友好的。以下是 FairSync（公平锁内部类）的 tryAcquire 方法实现：protected final boolean tryAcquire(int acquires) { final Thread current = Thread.currentThread(); // 获取当前线程 int c = getState(); // 获取父类 AQS 中的标志位 if (c == 0) { // 0 意味着锁空闲 if (!hasQueuedPredecessors() && // 如果前面没有已在队列中的线程！ compareAndSetState(0, acquires)) { // 修改一下状态位，注意：这里的 acquires 是在 lock 的时候传递来的，值为 1 setExclusiveOwnerThread(current); // 如果通过 CAS 操作将状态位更新成功，则代表当前线程获取锁，将当前线程设置到 AQS 的一个变量中 return true; } } else if (current == getExclusiveOwnerThread()) { // 如果不为 0 意味着，锁已经被拿走了。因为 ReentrantLock 是重入锁，判断获取锁的线程是不是当前请求锁的线程 int nextc = c + acquires; // 如果是的，累加在 state 字段上就可以了 if (nextc < 0) // 重入次数太多，溢出了 throw new Error("Maximum lock count exceeded"); setState(nextc); return true; } return false; }其中 hasQueuedPredecessors 方法用于判断队列中是否有前驱节点（保证公平性）：public final boolean hasQueuedPredecessors() { // The correctness of this depends on head being initialized // before tail and on head.next being accurate if the current // thread is first in queue. Node t = tail; // Read fields in reverse initialization order Node h = head; Node s; return h != t && ((s = h.next) == null || s.thread != Thread.currentThread()); }到此，如果获取锁，tryAcquire 返回 true，反之返回 false。回到 AQS 的 acquire 方法，如果没有获取到锁，按照逻辑应将当前线程放到队列中去。在入队之前，需要做些包装：public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }addWaiter 方法用于创建节点并加入队列：/** * Creates and enqueues node for current thread and given mode. * 用当前线程去构造一个 Node 对象，mode 是一个表示 Node 类型的字段， * 仅仅表示这个节点是独占的，还是共享的。 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared * @return the new node */ private Node addWaiter(Node mode) { Node node = new Node(Thread.currentThread(), mode); // Try the fast path of enq; backup to full enq on failure Node pred = tail; if (pred != null) { node.prev = pred; if (compareAndSetTail(pred, node)) { pred.next = node; return node; } } enq(node); return node; }创建好节点后，将节点加入到队列尾部。此处，在队列不为空的时候，先尝试通过 CAS 方式修改尾节点为最新的节点。如果修改失败，意味着有并发，这个时候才会进入 enq 中死循环，“自旋”方式修改。private Node enq(final Node node) { for (;;) { Node t = tail; if (t == null) { // Must initialize if (compareAndSetHead(new Node())) tail = head; } else { node.prev = t; if (compareAndSetTail(t, node)) { t.next = node; return t; } } } }在解释 acquireQueued 之前，我们需要先看下 AQS 中队列的内存结构。队列由 Node 类型的节点组成，其中至少有两个变量，一个封装线程，一个封装节点类型。实际上，它的内存结构是这样的（第一次节点插入时，第一个节点是一个空节点，代表有一个线程已经获取锁，事实上，队列的第一个节点就是代表持有锁的节点）：黄色节点为队列默认的头节点，每次有线程竞争失败，进入队列后其实都是插入到队列的尾节点（tail 节点）后面。final boolean acquireQueued(final Node node, int arg) { boolean failed = true; try { boolean interrupted = false; for (;;) { final Node p = node.predecessor(); // 前任节点 if (p == head && tryAcquire(arg)) { // 如果当前的节点的前一个节点是 head，说明他是队列中第一个“有效的”节点，因此尝试获取锁 setHead(node); // 成功后，将上图中的黄色节点移除，node 变成头节点 p.next = null; // help GC failed = false; return interrupted; } // 如果 p 节点不是头节点，或者 tryAcquire 返回 false，说明请求失败。 // 那么首先需要判断请求失败后 node 节点是否应该被阻塞，如果应该 // 被阻塞，那么阻塞 node 节点，并检测中断状态。 if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) // 如果需要，借助 JUC 包下的 LockSupport 类的静态方法 park 挂起当前线程，直到被唤醒 interrupted = true; } } finally { if (failed) // 如果有异常 cancelAcquire(node); // 取消请求，对应到队列操作，就是将当前节点从队列中移除 } }判断是否应该被挂起（当且仅当前一个节点是 SIGNAL 状态时，才会 return true，这之后才会执行挂起方法；若返回 false，则跳出上面的 if 判定，会继续自旋）：private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { int ws = pred.waitStatus; if (ws == Node.SIGNAL) // 如果这一步不满足，都会 return false /* * 前一节点已经设置了 signal 状态，释放锁后会通知后继节点 * 所以可以安全挂起 */ return true; if (ws > 0) { /* 判断如果前驱节点状态为 CANCELLED，那就一直往前找，直到找到最近一个正常等待的状态 */ do { node.prev = pred = pred.prev; } while (pred.waitStatus > 0); // 放置在其后面 pred.next = node; } else { /* * waitStatus must be 0 or PROPAGATE. Indicate that we * need a signal, but don't park yet. Caller will need to * retry to make sure it cannot acquire before parking. */ // 如果前驱节点正常，则修改前驱节点状态为 SIGNAL compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; }关于状态设置的疑问：为什么不关心是否成功却还要设置呢？如果设置失败，表示前驱已经被 signal 了。如果前驱是 head，说明有机会获取锁，所以返回 false 后还可以再次 tryAcquire。如果设置成功，表示前驱等待 signal。如果再次确认 pred.waitStatus 仍然是 Node.SIGNAL，则表明前驱等待释放锁的情况下必须阻塞当前线程，所以返回 true 后即被 park。private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); // 返回在这过程中是否被中断过，如果是，返回 true，同时将 interrupted 标志（acquireQueued 方法中）设为 true }在 acquireQueued 方法中，当前线程通过自旋的方式来尝试获取同步状态：当前节点的前驱节点为头节点才能尝试获得锁。如果获得成功，则把当前线程设置成头结点，把之前的头结点从队列中移除，等待垃圾回收（没有对象引用）。如果获取锁失败，则进入 shouldParkAfterFailedAcquire 方法中检测当前节点是否可以被安全的挂起（阻塞）。如果可以安全挂起，则进入 parkAndCheckInterrupt 方法，把当前线程挂起，并将 interrupted 置为 true。挂起的线程被唤醒后，继续在 acquireQueued 的 for 死循环中运行，直到获取锁后可以跳出循环。待验证结论：没有获得锁的线程，有可能在下次获得锁之前都不会被挂起。因为无法被安全挂起时，会把节点移到前驱节点为 SIGNAL 的节点后（这样下次就可以安全挂起了），然后再进行自旋。有可能在自旋的过程中，该节点已经成为了头结点后的节点，因此可以直接尝试获取锁而避免被挂起。公平锁的释放锁阶段（非公平锁调用的也是同一个方法）public void unlock() { sync.release(1); }public final boolean release(int arg) { if (tryRelease(arg)) { Node h = head; // 0 是初始值，不对应某个具体状态，所以不能为 0 if (h != null && h.waitStatus != 0) unparkSuccessor(h); return true; } return false; }unlock 方法调用了 AQS 的 release 方法，同样传入了参数 1。和获取锁相对应，获取一个锁，标志位 +1；释放一个锁，标志位 -1。protected final boolean tryRelease(int releases) { int c = getState() - releases; if (Thread.currentThread() != getExclusiveOwnerThread()) // 如果释放的线程和获取锁的线程不是同一个，抛出非法监视器状态异常 throw new IllegalMonitorStateException(); boolean free = false; if (c == 0) { // 因为是重入的关系，不是每次释放锁 c 都等于 0，直到最后一次释放锁时，才通知 AQS 不需要再记录哪个线程正在获取锁，即当前锁是 free 状态 free = true; setExclusiveOwnerThread(null); } setState(c); return free; }释放锁成功后，找到 AQS 的头节点，并唤醒它即可：/** * Wakes up node's successor, if one exists. * * @param node the node */ private void unparkSuccessor(Node node) { /* * If status is negative (i.e., possibly needing signal) try * to clear in anticipation of signalling. It is OK if this * fails or if status is changed by waiting thread. */ /* * 为什么不关心是否成功却还要设置呢？ * * 注意这里的 Node 实际就是 head * * 如果设置成功，即 head.waitStatus=0，则可以让这时即将被阻塞的线程有机会再次调用 tryAcquire 获取锁。 * 也就是让 shouldParkAfterFailedAcquire 方法里的 compareAndSetWaitStatus(pred, ws, Node.SIGNAL) 执行失败返回 false，这样就能再有机会再 tryAcquire 了 * * 如果设置失败，新跟随在 head 后面的线程被阻塞，但是没关系，下面的代码会立即将这个阻塞线程释放掉 */ int ws = node.waitStatus; if (ws < 0) compareAndSetWaitStatus(node, ws, 0); /* * Thread to unpark is held in successor, which is normally * just the next node. But if cancelled or apparently null, * traverse backwards from tail to find the actual * non-cancelled successor. */ Node s = node.next; if (s == null || s.waitStatus > 0) { s = null; // 从后往前找，但仍是找离 node 最近的一个有效节点（也就是它的继承者） for (Node t = tail; t != null && t != node; t = t.prev) if (t.waitStatus <= 0) s = t; } if (s != null) LockSupport.unpark(s.thread); }应用之——非公平锁其实，非公平锁和公平锁的唯一区别就是获取锁的方式不同：一个是按前后顺序依次获取锁，一个是抢占式的获取锁。获取锁final void lock() { if (compareAndSetState(0, 1)) setExclusiveOwnerThread(Thread.currentThread()); else acquire(1); }非公平锁的 lock 方法处理方式是：在 lock 的时候先直接 CAS 修改一次 state 变量（尝试获取锁），成功就返回，不成功再排队，从而达到不排队直接抢占的目的。关于具体场景的解析，可参考：关于具体场景的解析当等待队列中，某个结点内的线程被唤醒后，它参与到锁竞争中。同它一起竞争的有可能是之前没有竞争失败过的线程。等待队列中的其他结点，不会参与到竞争中。说明本文基于 JDK 1.8 版本源码进行分析。文中代码片段为核心逻辑摘录，实际源码可能包含更多细节处理。AQS 是 Java 并发包（J.U.C）的基石，理解其原理有助于深入掌握 ReentrantLock、CountDownLatch 等同步工具。
通过 HashMap、HashSet 的源代码分析其 Hash 存储机制集合和引用就像引用类型的数组一样，当我们把 Java 对象放入数组时，并不是真正把 Java 对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是一个引用变量。实际上，HashSet 和 HashMap 之间有很多相似之处。对于 HashSet 而言，系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于 HashMap 而言，系统将 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。在介绍集合存储之前需要指出一点：虽然集合号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入 Set 集合中，只是在 Set 集合中保留这些对象的引用。也就是说：Java 集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的 Java 对象。HashMap 的存储实现当程序试图将多个 key-value 放入 HashMap 中时，以如下代码片段为例：HashMap<String, Double> map = new HashMap<String, Double>(); map.put("语文", 80.0); map.put("数学", 89.0); map.put("英语", 78.2);HashMap 采用一种所谓的"Hash 算法”来决定每个元素的存储位置。当程序执行 map.put("语文", 80.0); 时，系统将调用"语文"的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。我们可以看 HashMap 类的 put(K key, V value) 方法的源代码：public V put(K key, V value) { // 如果 key 为 null，调用 putForNullKey 方法进行处理 if (key == null) return putForNullKey(value); // 根据 key 的 hashCode 计算 Hash 值 int hash = hash(key.hashCode()); // 搜索指定 hash 值在对应 table 中的索引 int i = indexFor(hash, table.length); // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素 for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; // 找到指定 key 与需要放入的 key 相等（hash 值相同 // 通过 equals 比较返回 true） if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry modCount++; // 将 key、value 添加到 i 索引处 addEntry(hash, key, value, i); return null; }JDK 源码在 JDK 安装目录下可以找到一个 src.zip 压缩文件，该文件里包含了 Java 基础类库的所有源文件。只要读者有学习兴趣，随时可以打开这份压缩文件来阅读 Java 类库的源代码，这对提高读者的编程能力是非常有帮助的。需要指出的是：src.zip 中包含的源代码并没有包含像上文中的中文注释，这些注释是笔者自己添加进去的。上面程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出：当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。上面方法提供了一个根据 hashCode() 返回值来计算 Hash 码的方法：hash()，这个方法是一个纯粹的数学计算，其方法如下：static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：static int indexFor(int h, int length) { return h & (length - 1); }这个方法非常巧妙，它总是通过 h & (table.length - 1) 来得到该对象的保存位置——而 HashMap 底层数组的长度总是 2 的 n 次方，这一点可参看后面关于 HashMap 构造器的介绍。当 length 总是 2 的倍数时，h & (length - 1) 将是一个非常巧妙的设计：假设 h=5, length=16, 那么 h & length - 1 将得到 5；如果 h=6, length=16, 那么 h & length - 1 将得到 6 …… 如果 h=15, length=16, 那么 h & length - 1 将得到 15；但是当 h=16 时，length=16 时，那么 h & length - 1 将得到 0 了；当 h=17 时，length=16 时，那么 h & length - 1 将得到 1 了…… 这样保证计算得到的索引值总是位于 table 数组的索引之内。根据上面 put 方法的源代码可以看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（就是 Entry 对象）的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值相同时，将由 key 通过 equals() 比较值决定是采用覆盖行为（返回 true），还是产生 Entry 链（返回 false）。上面程序中还调用了 addEntry(hash, key, value, i); 代码，其中 addEntry 是 HashMap 提供的一个包访问权限的方法，该方法仅用于添加一个 key-value 对。下面是该方法的代码：void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry Entry<K, V> e = table[bucketIndex]; // ① // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry table[bucketIndex] = new Entry<K, V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限 if (size++ >= threshold) // 把 table 对象的长度扩充到 2 倍。 resize(2 * table.length); // ② }上面方法的代码很简单，但其中包含了一个非常优雅的设计：系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序①号代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。Hash 算法的性能选项根据上面代码可以看出，在同一个 bucket 存储 Entry 链的情况下，新放入的 Entry 总是位于 bucket 中，而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端。上面程序中还有这样两个变量：size：该变量保存了该 HashMap 中所包含的 key-value 对的数量。threshold：该变量包含了 HashMap 能容纳的 key-value 对的极限，它的值等于 HashMap 的容量乘以负载因子（load factor）。从上面程序中②号代码可以看出，当 size++ >= threshold 时，HashMap 会自动调用 resize 方法扩充 HashMap 的容量。每扩充一次，HashMap 的容量就增大一倍。上面程序中使用的 table 其实就是一个普通数组，每个数组都有一个固定的长度，这个数组的长度就是 HashMap 的容量。HashMap 包含如下几个构造器：HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。当创建一个 HashMap 时，系统会自动创建一个 table 数组来保存 HashMap 中的 Entry，下面是 HashMap 中一个构造器的代码：// 以指定初始化容量、负载因子创建 HashMap public HashMap(int initialCapacity, float loadFactor) { // 初始容量不能为负数 if (initialCapacity < 0) throw new IllegalArgumentException( "Illegal initial capacity: " + initialCapacity); // 如果初始容量大于最大容量，让出示容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 负载因子必须大于 0 的数值 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException( loadFactor); // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; // 设置容量极限等于容量 * 负载因子 threshold = (int)(capacity * loadFactor); // 初始化 table 数组 table = new Entry[capacity]; // ① init(); }上面代码中粗体字代码包含了一个简洁的代码实现：找出大于 initialCapacity 的、最小的 2 的 n 次方值，并将其作为 HashMap 的实际容量（由 capacity 变量保存）。例如给定 initialCapacity 为 10，那么该 HashMap 的实际容量就是 16。initialCapacity 与 HashMap 的容量创建 HashMap 时指定的 initialCapacity 并不等于 HashMap 的实际容量，通常来说，HashMap 的实际容量总比 initialCapacity 大一些，除非我们指定的 initialCapacity 参数值恰好是 2 的 n 次方。当然，掌握了 HashMap 容量分配的知识之后，应该在创建 HashMap 时将 initialCapacity 参数值指定为 2 的 n 次方，这样可以减少系统的计算开销。程序①号代码处可以看到：table 的实质就是一个数组，一个长度为 capacity 的数组。对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如图 1 所示：图 1. HashMap 的存储示意HashMap 的读取实现当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，再根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：public V get(Object key) { // 如果 key 是 null，调用 getForNullKey 取出对应的 value if (key == null) return getForNullKey(); // 根据该 key 的 hashCode 值计算它的 hash 码 int hash = hash(key.hashCode()); // 直接取出 table 数组中指定索引处的值， for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; // 搜索该 Entry 链的下一个 Entry e = e.next) // ① { Object k; // 如果该 Entry 的 key 与被搜索 key 相同 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }从上面代码中可以看出，如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生"Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。掌握了上面知识之后，我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity * load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的 Entry 数组），因此创建 HashMap 时初始化容量设置也需要小心对待。HashSet 的实现对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层采用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，查看 HashSet 的源代码，可以看到如下代码：public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 使用 HashMap 的 key 保存 HashSet 中所有元素 private transient HashMap<E, Object> map; // 定义一个虚拟的 Object 对象作为 HashMap 的 value private static final Object PRESENT = new Object(); ... // 初始化 HashSet，底层会初始化一个 HashMap public HashSet() { map = new HashMap<E, Object>(); } // 以指定的 initialCapacity、loadFactor 创建 HashSet // 其实就是以相应的参数创建 HashMap public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<E, Object>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<E, Object>(initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E, Object>(initialCapacity , loadFactor); } // 调用 map 的 keySet 来返回所有的 key public Iterator<E> iterator() { return map.keySet().iterator(); } // 调用 HashMap 的 size() 方法返回 Entry 的数量，就得到该 Set 里元素的个数 public int size() { return map.size(); } // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空， // 当 HashMap 为空时，对应的 HashSet 也为空 public boolean isEmpty() { return map.isEmpty(); } // 调用 HashMap 的 containsKey 判断是否包含指定 key // HashSet 的所有元素就是通过 HashMap 的 key 来保存的 public boolean contains(Object o) { return map.containsKey(o); } // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap public boolean add(E e) { return map.put(e, PRESENT) == null; } // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中对应的元素 public boolean remove(Object o) { return map.remove(o) == PRESENT; } // 调用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素 public void clear() { map.clear(); } ... }由上面源程序可以看出，HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。HashMap 的 put 与 HashSet 的 add由于 HashSet 的 add() 方法添加集合元素时实际上转变为调用 HashMap 的 put() 方法来添加 key-value 对，当新放入 HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 相同（hashCode() 返回值相等，通过 equals 比较也返回 true），新添加的 Entry 的 value 将覆盖原来 Entry 的 value，但 key 不会有任何改变，因此如果向 HashSet 中添加一个已经存在的元素，新添加的集合元素（底层由 HashMap 的 key 保存）不会覆盖已有的集合元素。掌握上面理论知识之后，接下来看一个示例程序，测试一下自己是否真正掌握了 HashMap 和 HashSet 集合的功能。class Name { private String first; private String last; public Name(String first, String last) { this.first = first; this.last = last; } public boolean equals(Object o) { if (this == o) { return true; } if (o.getClass() == Name.class) { Name n = (Name)o; return n.first.equals(first) && n.last.equals(last); } return false; } } public class HashSetTest { public static void main(String[] args) { Set<Name> s = new HashSet<Name>(); s.add(new Name("abc", "123")); System.out.println( s.contains(new Name("abc", "123"))); } }上面程序中向 HashSet 里添加了一个 new Name("abc", "123") 对象之后，立即通过程序判断该 HashSet 是否包含一个 new Name("abc", "123") 对象。粗看上去，很容易以为该程序会输出 true。实际运行上面程序将看到程序输出 false，这是因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外，还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法，两个 Name 对象的 hashCode() 返回值并不相同，因此 HashSet 会把它们当成 2 个对象处理，因此程序返回 false。由此可见，当我们试图把某个类的对象当成 HashMap 的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。hashCode() 和 equals()关于如何正确地重写某个类的 hashCode() 方法和 equals() 方法，请参考疯狂 Java 体系的《疯狂 Java 讲义》一书中相关内容。如下程序就正确重写了 Name 类的 hashCode() 和 equals() 方法，程序如下：class Name { private String first; private String last; public Name(String first, String last) { this.first = first; this.last = last; } // 根据 first 判断两个 Name 是否相等 public boolean equals(Object o) { if (this == o) { return true; } if (o.getClass() == Name.class) { Name n = (Name)o; return n.first.equals(first); } return false; } // 根据 first 计算 Name 对象的 hashCode() 返回值 public int hashCode() { return first.hashCode(); } public String toString() { return "Name[first=" + first + ", last=" + last + "]"; } } public class HashSetTest2 { public static void main(String[] args) { HashSet<Name> set = new HashSet<Name>(); set.add(new Name("abc", "123")); set.add(new Name("abc", "456")); System.out.println(set); } }上面程序中提供了一个 Name 类，该 Name 类重写了 equals() 和 toString() 两个方法，这两个方法都是根据 Name 类的 first 实例变量来判断的，当两个 Name 对象的 first 实例变量相等时，这两个 Name 对象的 hashCode() 返回值也相同，通过 equals() 比较也会返回 true。程序主方法先将第一个 Name 对象添加到 HashSet 中，该 Name 对象的 first 实例变量值为"abc"，接着程序再次试图将一个 first 为"abc"的 Name 对象添加到 HashSet 中，很明显，此时没法将新的 Name 对象添加到该 HashSet 中，因为此处试图添加的 Name 对象的 first 也是"abc"，HashSet 会判断此处新增的 Name 对象与原有的 Name 对象相同，因此无法添加进入，程序在①号代码处输出 set 集合时将看到该集合里只包含一个 Name 对象，就是第一个、last 为"123"的 Name 对象。相关主题"Java 理论与实践：哈希"（developerWorks，2003 年 8 月）：介绍在创建 Java 类以有效和准确定义 hashCode() 和 equals() 时应遵循的规则和指南。"Java 理论与实践：构建一个更好的 HashMap"（developerWorks，2003 年 8 月）：Brian Goetz 仔细分析了 ConcurrentHashMap 的代码，并探讨 Doug Lea 是如何在不损失线程安全的情况下取得这么骄人成绩的。"Merlin 的魔力：维护插入顺序使用新链接的 HashSet 和 HashMap 实现”（developerWorks，2001 年 10 月）：学习如何按插入顺序迭代散列集合中的各个元素，以及如何使用 J2SE，版本 1.4 中的新 Collections Framework 按存取顺序维护元素。在 developerWorks Java 技术专区 上可以找到数百篇其他的 Java 参考资料。说明本文基于 JDK 7 及之前版本的源码进行分析。JDK 8 及后续版本对 HashMap 底层实现进行了重大优化（如引入红黑树、改用 Node 节点等），具体实现细节可能有所不同，但核心 Hash 存储机制原理依然具有参考价值。
LinkedHashMap 的实现原理LinkedHashMap 概述LinkedHashMap 是 Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。与 HashMap 不同，LinkedHashMap 维护着一个运行于所有条目的双向链接列表，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。LinkedHashMap 的实现原理对于 LinkedHashMap 而言，它继承自 HashMap，底层使用哈希表与双向链表来保存所有元素。其基本操作与父类 HashMap 相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析 LinkedHashMap 的源代码。Entry 元素LinkedHashMap 采用的 hash 算法和 HashMap 相同，但是它重新定义了数组中保存的元素 Entry。该 Entry 除了保存当前对象的引用外，还保存了其上一个元素 before 和下一个元素 after 的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：/** * 双向链表的表头元素。 */ private transient Entry<K,V> header; /** * LinkedHashMap 的 Entry 元素。 * 继承 HashMap 的 Entry 元素，又保存了其上一个元素 before 和下一个元素 after 的引用。 */ private static class Entry<K,V> extends HashMap.Entry<K,V> { Entry<K,V> before, after; // ... } 初始化通过源代码可以看出，在 LinkedHashMap 的构造方法中，实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组。例如：public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } HashMap 中的相关构造方法：public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); } 我们已经知道 LinkedHashMap 的 Entry 元素继承 HashMap 的 Entry，提供了双向链表的功能。在上述 HashMap 的构造器中，最后会调用 init() 方法，进行相关的初始化。这个方法在 HashMap 的实现中并无意义，只是提供给子类实现相关的初始化调用。LinkedHashMap 重写了 init() 方法，在调用父类的构造方法完成构造后，进一步实现了对其元素 Entry 的初始化操作：void init() { header = new Entry<K,V>(-1, null, null, null); header.before = header.after = header; } 存储操作LinkedHashMap 并未重写父类 HashMap 的 put 方法，而是重写了父类 HashMap 的 put 方法调用的子方法 void addEntry(int hash, K key, V value, int bucketIndex) 和 void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。void addEntry(int hash, K key, V value, int bucketIndex) { // 调用 create 方法，将新元素以双向链表的形式加入到映射中。 createEntry(hash, key, value, bucketIndex); // 删除最近最少使用元素的策略定义 Entry<K,V> eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else { if (size >= threshold) resize(2 * table.length); } } void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e; // 调用元素的 addBefore 方法，将元素加入到哈希、双向链接列表。 e.addBefore(header); size++; } private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } 读取操作LinkedHashMap 重写了父类 HashMap 的 get 方法，实际在调用父类 getEntry() 方法取得查找的元素后，再判断当排序模式 accessOrder 为 true 时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于链表的增加、删除操作是常数级时间复杂度，故并不会带来性能的损失。public V get(Object key) { // 调用父类 HashMap 的 getEntry() 方法，取得要查找的元素。 Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; // 记录访问顺序。 e.recordAccess(this); return e.value; } void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; // 如果定义了 LinkedHashMap 的迭代顺序为访问顺序， // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。 if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } 排序模式LinkedHashMap 定义了排序模式 accessOrder，该属性为 boolean 型变量。对于访问顺序，为 true；对于插入顺序，则为 false。private final boolean accessOrder; 一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看 LinkedHashMap 的构造方法：public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } 这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个 LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造 LinkedHashMap：public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } 该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建 LRU 缓存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法，在将新条目插入到映射后，put 和 putAll 将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回 false。这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } 此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建 LRU 缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。例如：重写此方法，维持此映射只保存 100 个条目的稳定状态，在每次添加新条目时删除最旧的条目。private static final int MAX_ENTRIES = 100; protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } 相关说明在阅读本文前，请先了解：深入 Java 集合学习系列：HashMap 的实现原理。相关 HashSet 的实现原理，请参考：深入 Java 集合学习系列：HashSet 的实现原理。相关 LinkedHashSet 的实现原理，请参考：深入 Java 集合学习系列：LinkedHashSet 的实现原理。版本说明注意：本文源码分析基于 Java 7 及之前版本（如 HashMap.Entry、init() 钩子方法等）。在 Java 8 及后续版本中，HashMap 与 LinkedHashMap 的底层实现进行了重构（例如引入 Node 节点、红黑树优化等），部分方法签名与内部结构有所变化，但核心设计思想（哈希表 + 双向链表）保持一致。
HashMap 源码分析（基于 JDK 1.6）编者注：本文为历史博文归档，主要基于 JDK 1.6 版本源码进行分析。涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。在 Java 集合类中，除了 ArrayList 之外，最常用的莫过于 HashMap 了。本文旨在尽可能详细地解析 HashMap 的源码实现。水平有限，若有不足之处，欢迎指正，定当及时修正。在深入 HashMap 源码之前，我们先简要复习一下相关的数据结构。数据结构基础Java 最基本的数据结构包括数组（Array）和链表（Linked List）。数组：空间连续（大小固定）、寻址迅速。但插入和删除时需要移动元素，因此查询快，增删慢。链表：可动态增加或减少空间以适应元素变化。但查找时只能顺着节点逐个查找，因此增删快，查询慢。有没有一种结构能综合数组和链表的优点呢？当然有，那就是哈希表（Hash Table）。虽然说是综合优点，但实际上查找速度肯定没有数组快，插入删除也没有链表快，这是一种折中的方案。哈希表一般采用拉链法（Chaining）实现。（图片源自网络，多处文章均有引用，因无法确认出处未申明作者）计算机相关专业通常都会学习这些内容，此处不再赘述。铺垫了数组、链表、哈希表和拉链法，接下来进入正题：我们在什么时候用到了这些内容？具体是如何实现的？其实我们一直在使用（想必大家对 HashMap 都不陌生），可能未曾深究其内部实现。下面主要分析 HashMap 的源码。类定义与继承结构HashMap 继承自 AbstractMap，实现了 Map 接口（相关内容可参考 《Java 集合类》）。类的定义如下：public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, SerializableMap 接口定义了所有 Map 子类必须实现的方法。Map 接口中还定义了一个内部接口 Entry（为何设计成内部接口值得探讨，此处暂不展开），Entry 将在后文详细介绍。AbstractMap 也实现了 Map 接口，并且提供了两个实现 Entry 的内部类：SimpleEntry 和 SimpleImmutableEntry。定义了接口，接口中又有内部接口，然后有抽象类实现接口，抽象类里面又有内部类实现接口的内部接口，结构略显复杂。暂且不管设计缘由，先看 HashMap 的具体实现。核心属性HashMap 中定义的关键属性如下（部分注释为原文保留）：/** * 默认的初始容量，必须是 2 的幂。 */ static final int DEFAULT_INITIAL_CAPACITY = 16; /** * 最大容量（必须是 2 的幂且小于 2 的 30 次方，传入容量过大将被这个值替换） */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认装载因子，后面会做解释 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 存储数据的 Entry 数组，长度是 2 的幂。 * 看到数组的内容了，接着看数组中存的内容就明白为什么博文开头先复习数据结构了 */ transient Entry[] table; /** * map 中保存的键值对的数量 */ transient int size; /** * 需要调整大小的极限值（容量 * 装载因子） */ int threshold; /** * 装载因子 */ final float loadFactor; /** * map 结构被改变的次数 */ transient volatile int modCount;构造方法接着是 HashMap 的构造方法：/** * 使用默认的容量及装载因子构造一个空的 HashMap */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // 计算下次需要调整大小的极限值 table = new Entry[DEFAULT_INITIAL_CAPACITY]; // 根据默认容量（16）初始化 table init(); } /** * 根据给定的初始容量和装载因子创建一个空的 HashMap * 初始容量小于 0 或装载因子小于等于 0 将报异常 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) // 调整最大容量 initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); int capacity = 1; // 设置 capacity 为大于 initialCapacity 且是 2 的幂的最小值 while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); } /** * 根据指定容量创建一个空的 HashMap */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); // 调用上面的构造方法，容量为指定的容量，装载因子是默认值 } /** * 通过传入的 map 创建一个 HashMap * 容量为默认容量（16）和 (map.size()/DEFAULT_LOAD_FACTOR)+1 的较大者，装载因子为默认值 */ public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); }上述构造方法中调用到了 init() 方法，最后一个方法还调用了 putAllForCreate(Map<? extends K, ? extends V> m)。init() 方法是一个空方法，里面没有任何内容（留给子类重写）。putAllForCreate 看方法名可知，是在创建时将传入的 map 全部放入新创建的对象中。该方法涉及的其他逻辑将在后面介绍。内部类 Entry初始化 table 时均使用了 Entry，这是 HashMap 的一个内部类，实现了 Map 接口的内部接口 Entry。Map.Entry 接口定义的方法：K getKey(); // 获取 Key V getValue(); // 获取 Value V setValue(); // 设置 Value，至于具体返回什么要看具体实现 boolean equals(Object o); // 定义 equals 方法用于判断两个 Entry 是否相同 int hashCode(); // 定义获取 hashCode 的方法HashMap.Entry 类的具体实现：static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; // 对下一个节点的引用（看到链表的内容，结合定义的 Entry 数组，是不是想到了哈希表的拉链法实现？！） final int hash; // 哈希值 Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; // 返回的是之前的 Value } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) // 先判断类型是否一致 return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); // Key 相等且 Value 相等则两个 Entry 相等 if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } // hashCode 是 Key 的 hashCode 和 Value 的 hashCode 的异或的结果 public final int hashCode() { return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode()); } // 重写 toString 方法，使输出更清晰 public final String toString() { return getKey() + "=" + getValue(); } /** * 当调用 put(k,v) 方法存入键值对时，如果 k 已经存在，则该方法被调用 */ void recordAccess(HashMap<K,V> m) { } /** * 当 Entry 被从 HashMap 中移除时被调用 */ void recordRemoval(HashMap<K,V> m) { } }核心方法分析看完属性和构造方法，接着分析 HashMap 中的其他方法。从最常用的 put 和 get 说起。put() 方法public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }当存入的 key 是 null 的时候将调用 putForNullKey 方法，暂时将这段逻辑放一边，先看 key 不为 null 的情况。先调用 hash(int h) 方法获取了一个 hash 值。static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }这个方法的主要作用是防止质量较差的哈希函数带来过多的冲突（碰撞）问题。Java 中 int 值占 4 个字节，即 32 位。根据这 32 位值进行移位、异或运算得到一个值。计算索引位置。static int indexFor(int h, int length) { return h & (length - 1); }indexFor 返回 hash 值和 table 数组长度减 1 的与运算结果。为什么使用的是 length-1？因为这样可以保证结果的最大值是 length-1，不会产生数组越界问题（前提是 length 为 2 的幂）。获取索引位置之后做了什么？探测 table[i] 所在的链表，若发现 key 值与传入的 key 值相同的对象，则替换并返回 oldValue。若找不到，则通过 addEntry(hash, key, value, i) 添加新的对象。void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }这就是在一个链表头部插入一个节点的过程。获取 table[i] 的对象 e，将 table[i] 的对象修改为新增对象，让新增对象的 next 指向 e。之后判断 size 是否到达了需要扩充 table 数组容量的界限并让 size 自增 1，如果达到了则调用 resize(int capacity) 方法将数组容量拓展为原来的两倍。void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; // 这个 if 块表明，如果容量已经到达允许的最大值，即 MAXIMUM_CAPACITY，则不再拓展容量 // 而将装载拓展的界限值设为计算机允许的最大值。不会再触发 resize 方法 // 而是不断的向 map 中添加内容，即 table 数组中的链表可以不断变长，但数组长度不再改变 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 创建新数组，容量为指定的容量 Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; // 设置下一次需要调整数组大小的界限 threshold = (int)(newCapacity * loadFactor); }结合上面给出的注释，调整数组容量的内容仅剩下将原 table 中的内容复制到 newTable 中并将 newTable 返回给原 table。即上面代码中的 transfer(newTable); table = newTable;。来看 transfer(Entry[] newTable) 方法。void transfer(Entry[] newTable) { // 保留原数组的引用到 src 中 Entry[] src = table; // 新容量是新数组的长度 int newCapacity = newTable.length; // 遍历原数组 for (int j = 0; j < src.length; j++) { // 获取元素 e Entry<K,V> e = src[j]; if (e != null) { // 将原数组中的元素置为 null src[j] = null; // 遍历原数组中 j 位置指向的链表 do { Entry<K,V> next = e.next; // 根据新的容量计算 e 在新数组中的位置 int i = indexFor(e.hash, newCapacity); // 将 e 插入到 newTable[i] 指向的链表的头部 e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }从上面的代码可以看出，HashMap 之所以不能保持元素的顺序有以下几点原因：插入元素的时候对元素进行哈希处理，不同元素分配到 table 的不同位置；容量拓展的时候又进行了 hash 处理；复制原表内容的时候链表被倒置。一个 put 方法带出了这么多内容，接着看看 putAll 吧。public void putAll(Map<? extends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; // 为什么判断条件是 numKeysToBeAdded，不是 (numKeysToBeAdded+table.length)>threshold??? if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); put(e.getKey(), e.getValue()); } }先回答上面的问题：为什么判断条件是 numKeysToBeAdded，而不是 (numKeysToBeAdded + table.length) > threshold？这是一种保守的做法。明显地，我们应该在 (numKeysToBeAdded + table.length) > threshold 的时候去拓展容量，但是考虑到将被添加的元素可能会有 Key 与原本存在的 Key 相同的情况（覆盖而非新增），所以采用保守的做法，避免拓展到过大的容量。接着是遍历 m 中的内容，然后调用 put 方法将元素添加到 table 数组中。遍历的时候涉及到了 entrySet 方法，这个方法定义在 Map 接口中，HashMap 中也有实现，后面会解释 HashMap 的这个方法。putForNullKey 方法下面介绍在 put 方法中被调用到的 putForNullKey 方法。private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }这是一个私有方法，在 put 方法中被调用。它首先遍历 table 数组，如果找到 key 为 null 的元素，则替换元素值并返回 oldValue；否则通过 addEntry 方法添加元素，之后返回 null。putAllForCreate 与 putForCreate还记得上面构造方法中调用到的 putAllForCreate 吗？一口气将 put 操作的相关方法看完。private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); putForCreate(e.getKey(), e.getValue()); } }先将遍历的过程放在一边，因为它同样涉及到了 entrySet() 方法。剩下的代码很简单，只是调用 putForCreate 方法逐个元素加入。private void putForCreate(K key, V value) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } createEntry(hash, key, value, i); }该方法先计算需要添加的元素的 hash 值和在 table 数组中的索引 i。接着遍历 table[i] 的链表，若有元素的 key 值与传入 key 值相等，则替换 value，结束方法。若不存在 key 值相同的元素，则调用 createEntry 创建并添加元素。void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); size++; }这个方法的内容就不解释了，上面都解释过。至此所有 put 相关操作都解释完毕了。get() 方法put 之外，另一个常用的操作就是 get，下面就来看 get 方法。public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }该方法分为 key 为 null 和不为 null 两块。先看不为 null 的情况：先获取 key 的 hash 值，之后通过 hash 值及 table.length 获取 key 对应的 table 数组的索引，遍历索引的链表，若找到 key 相同的元素，则返回元素的 value，否则返回 null。key 为 null 的情况调用了 getForNullKey() 方法。private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }这是一个私有方法，只在 get 中被调用。该方法判断 table[0] 中的链表是否包含 key 为 null 的元素，包含则返回 value，不包含则返回 null。为什么是遍历 table[0] 的链表？因为 key 为 null 的时候获得的 hash 值都是 0。判断元素是否存在添加（put）和获取（get）都结束了，接着看如何判断一个元素是否存在。HashMap 没有提供判断元素是否存在的方法，只提供了判断 Key 是否存在及 Value 是否存在的方法，分别是 containsKey(Object key)、containsValue(Object value)。containsKey(Object key)containsKey(Object key) 方法很简单，只是判断 getEntry(key) 的结果是否为 null，是则返回 false，否返回 true。public boolean containsKey(Object key) { return getEntry(key) != null; } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }getEntry(Object key) 也没什么内容，只是根据 key 对应的 hash 值计算在 table 数组中的索引位置，然后遍历该链表判断是否存在相同的 key 值。containsValue(Object value)public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; for (int i = 0; i < tab.length; i++) for (Entry e = tab[i]; e != null; e = e.next) if (value.equals(e.value)) return true; return false; } private boolean containsNullValue() { Entry[] tab = table; for (int i = 0; i < tab.length; i++) for (Entry e = tab[i]; e != null; e = e.next) if (e.value == null) return true; return false; }判断一个 value 是否存在比判断 key 是否存在还要简单，就是遍历所有元素判断是否有相等的值。这里分为两种情况处理，value 为 null 和不为 null 的情况，但内容差不多，只是判断相等的方式不同。这个判断是否存在必须遍历所有元素，是一个双重循环的过程，因此是比较耗时的操作。删除操作接着看 HashMap 中“删除”相关的操作，有 remove(Object key) 和 clear() 两个方法。remove(Object key)public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); }看这个方法，removeEntryForKey(key) 的返回结果应该是被移除的元素，如果不存在这个元素则返回为 null。remove 方法根据 removeEntryForKey 返回的结果 e 是否为 null 返回 null 或 e.value。final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; }上面的这个过程就是先找到 table 数组中对应的索引，接着就类似于一般的链表的删除操作，而且是单向链表删除节点，很简单。在 C 语言中就是修改指针，这个例子中就是将要删除节点的前一节点的 next 指向被删除节点的 next 即可。clear()public void clear() { modCount++; Entry[] tab = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; }clear() 方法删除 HashMap 中所有的元素，这里就不用一个个删除节点了，而是直接将 table 数组内容都置空，这样所有的链表都已经无法访问，Java 的垃圾回收机制会去处理这些链表。table 数组置空后修改 size 为 0。这里为什么不直接操作 table 而是通过 tab 呢？若有了解其原因的读者，欢迎指点。集合视图方法主要方法看的差不多了，接着看一个上面提到了好几次但是都搁在一边没有分析的方法：entrySet()。entrySet()public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); }为什么会有这样的方法，只是调用了一下 entrySet0，而且 entrySet0 的名称看着就很奇怪。再看 entrySet0 方法中为什么不直接 return entrySet != null ? entrySet : (entrySet = new EntrySet) 呢？上面的疑问还没解开，但是先看 entrySet 这个属性吧，在文章开头的属性定义中并没有给出这个属性，下面先看一下它的定义：private transient Set<Map.Entry<K,V>> entrySet = null;它是一个内容为 Map.Entry<K,V> 的 Set。看看在哪些地方往里面添加了元素。为什么上面的那句话我要把它标成红色？因为这是一个陷阱，在看代码的时候我就陷进去了。仔细看 EntrySet 这个类。private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<K,V> e = (Map.Entry<K,V>) o; Entry<K,V> candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return size; } public void clear() { HashMap.this.clear(); } }看到了什么？这个类根本没属性，它只是个代理。因为它是内部类，可以访问外部类的内容，debug 的时候能看到的属性都是继承或者外部类的属性，输出的时候其实也是调用到了父类的 toString 方法将 HashMap 中的内容输出了。keySet()public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); }是不是和 entrySet0() 方法很像！private final class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } public void clear() { HashMap.this.clear(); } }同样是个代理类，contains、remove、clear 方法都是调用的 HashMap 的方法。values()public Collection<V> values() { Collection<V> vs = values; return (vs != null ? vs : (values = new Values())); } private final class Values extends AbstractCollection<V> { public Iterator<V> iterator() { return newValueIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsValue(o); } public void clear() { HashMap.this.clear(); } }values() 方法也一样是代理。只是 Values 类继承自 AbstractCollection 类，而不是 AbstractSet。总结还有一个重要的内容没有进行说明，那就是迭代器。HashMap 中的 entrySet()、keySet()、values() 等方法都使用到了迭代器 Iterator 的知识。其他集合类也有使用到迭代器，将另写博文总结讨论集合类的迭代器。说明：本文基于 JDK 1.6 版本源码进行分析。JDK 1.8 及后续版本中 HashMap 引入了红黑树优化链表过长的问题，底层结构与扩容机制有较大变化，阅读新版本源码时请注意区别。
JDK源码分析之Set类详解——适配器模式的应用
JDK 源码分析之 Set 类详解——适配器模式的应用编者注：本文为历史博文归档；涉及 JDK、框架与工具链版本请以当前官方文档为准。引用外链图片可能失效，阅读时请注意时效性。JDK 源码中的 Set 类是开发过程中经常使用的集合类型。本文将对 JDK 源码中 Set 类的构造进行深入分析，帮助开发者在编程中更高效地应用。Set 类的核心特性与实现原理在 JDK 源码中，Set 类最常用的特性是不允许包含重复元素。那么，判断元素是否相同是如何实现的呢？我们可以通过下面的类图来直观理解：观察上述类图，我们可以发现一个经典设计模式的应用，那就是适配器模式（Adapter Pattern）。源码将 Map 接口的对象包装成为了 Set 接口。下面我们通过代码具体分析这一实现机制。HashSet 源码分析首先查看 HashSet 的核心成员变量：private transient HashMap<E, Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();可见，HashSet 内部适配了 HashMap。那么它的功能是如何委托给 HashMap 结构的呢？关键在于 add 方法的实现：public boolean add(E e) { return map.put(e, PRESENT) == null; }在 HashMap 中，我们大多数时候关注的是 value，但是在 Set 的实现中，却很好地利用了已有类 HashMap 的特性。它利用了 HashMap 的 key 的唯一性来保证存储在 Set 中的元素的唯一性。private static final Object PRESENT = new Object();上述 PRESENT 对象是 HashMap 所有 key 对应的 value，它只是一个形式占位符，而我们真正的数据是存储在 key 中的资源。此外，HashSet 拿到的迭代器也是基于 Map 的 keySet：public Iterator<E> iterator() { return map.keySet().iterator(); }即直接返回 Map 的 keySet 的迭代器。LinkedHashSet 源码分析同理，我们看看 LinkedHashSet 的实现。它提供了多个构造方法：public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } /** * Constructs a new, empty linked hash set with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity of the LinkedHashSet * @throws IllegalArgumentException if the initial capacity is less * than zero */ public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } /** * Constructs a new, empty linked hash set with the default initial * capacity (16) and load factor (0.75). */ public LinkedHashSet() { super(16, .75f, true); }这些构造方法均调用了父类（HashSet）的构造函数。父类中对应的构造函数如下：HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }由此可见，LinkedHashSet 内部实例化了 LinkedHashMap，从而保持了元素的插入顺序。TreeSet 源码分析同理，我们亦可见到 TreeMap 的实现影子。在 TreeSet 中，底层存储结构为：private transient NavigableMap<E, Object> m; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();设计模式总结综上所述，Set 接口的实现类内部均委托给了 Map 接口的实现类。虽然从某些角度理解，这也可以被视为桥接模式（Bridge Pattern）的一种变形，但从语义意义上分析，我更倾向于认为这是适配器模式的应用：将 Map 适配为 Set 接口供外部使用。希望这篇对 JDK 源码中 Set 类的分析能对你有所帮助。说明：本文基于早期 JDK 版本源码分析（参考图片上传时间为 2009 年）。虽然核心实现原理（基于 Map 实现 Set）在后续版本（如 JDK 1.8+）中依然保持兼容，但具体内部类名或方法细节可能随版本迭代有所调整，请以当前官方文档为准。