HashMap，顾名思义，是一种基于哈希函数实现的map，又被称为哈希表、散列表。它是基于快速存取的角度设计的，也是一种典型的空间换时间的做法。map表示一种一对一的映射关系，一个键对应一个值，键不可重复（重复的键只会存储最后一次的值）。它允许使用 null 值和 null 键。除了不同步和允许使用 null 之外，HashMap与Hashtable大致相同。该类是不能保证顺序的，进行某些操作后，键值对的顺序可能会发生变化。由于使用哈希函数定位，所以它的存取非常高效。本篇我们将对HashMap的数据结构及核心方法进行分析。下面开始我们的主题。
Java版本
1 2 3 java version "1.8.0_211" Java(TM) SE Runtime Environment (build 1.8 .0 _211-b12) Java HotSpot (TM) 64-Bit Server VM (build 25.211 -b12, mixed mode)
数据结构
JDK8中HashMap底层是基于数组、链表、红黑树实现的。其内部有如下几个主要的成员变量。
1 2 3 4 transient Node<K,V>[] table;private int size;int threshold;final float loadFactor;
table是一个Node<K,V>类型的数组，每个元素指向一个单链表，链表中每个节点存储一个键值对，当链表长度大于8时，将链表转成红黑树；size 记录了实际存储的键值对个数。
loadFactor负载因子表示哈希表中元素的填满的程度。负载因子越大，填满的元素越多，空间利用率越高。但同时冲突几率也会变大，从而导致链表长度会越来越长，查找效率降低。反之，负载因子越小，填满的元素越少，冲突几率减小了。但表中的数据将过于稀疏（很多空间还没用，就开始扩容了），造成了空间浪费。因此，必须在冲突几率与空间利用率之间做一种权衡的选择。如果不特别指定，默认负载因子是0.75。
threshold表示扩容临界值。值为容量与负载因子的乘积。当实际大小超过这个临界值时，会自动扩容。
Node<K,V>是HashMap的一个内建数据类型，用来存储实际的key、value、key的hash值和下一个节点的引用。这里直接存储hash值是为了在比较的时候加快计算。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 static class Node <K ,V > implements Map .Entry <K ,V > { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this .hash = hash; this .key = key; this .value = value; this .next = next; } ...... }
table初始值为空，当第一次添加键值对时，初始化为容量16的数组。它随着键值对的添加会自动扩容。大概扩容策略是，当实际存储的键值对个数超过临界值threshold (= capacity * load factor)时，就会重新分配。
实现原理
继承与实现
1 2 public class HashMap <K ,V > extends AbstractMap <K ,V > implements Map <K ,V >, Cloneable , Serializable
成员属性
以下是HashMap的成员属性。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 // 默认初始容量，必须是2的整数次幂 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ; // aka 16 // 最大容量，这里表示的数字是 2的30次幂 // // 这里为什么这么写，又为什么是这个数字？ // 1.使用位运算效率更高 // 2.如果写成 2 << 31则超过int最大值，而2 << 30 是仅仅比最大值小的整数次幂 // // 为什么是int最大值？ // 1.因为size、容量等字段数据类型都是int // // 为什么一定要是2的整数次幂？ // 1.HashMap定位下标，采用的是(length-1) & hash这样的方式，为了元素更均匀的分布。 static final int MAXIMUM_CAPACITY = 1 << 30 ;// 默认负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f ;// 当桶中的节点数大于8时，将链表转成红黑树。 static final int TREEIFY_THRESHOLD = 8 ;// 红黑树的节点数小于6时，将红黑树转回链表。 static final int UNTREEIFY_THRESHOLD = 6 ;// 最小的树化容量临界值。实际容量大于该值时，才允许树化。否则直接扩容。 // 为了避免扩容和树化之间选择的冲突，该值不能小于4 * TREEIFY_THRESHOLD。 static final int MIN_TREEIFY_CAPACITY = 64 ;// 实际存储数据的数组。该表在首次使用时初始化，并根据需要调整大小。分配后，长度始终是2的整数次幂。 transient Node<K,V>[] table;// 键值对集合视图，对其修改会直接修改map本身。 transient Set<Map.Entry<K,V>> entrySet;// 实际存储的键值对个数 transient int size;// 对map结构性修改的次数(用于fail-fast机制) transient int modCount;// 扩容临界值 int threshold;// 负载因子变量 final float loadFactor;
构造函数
HasMap有如下四个构造方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 // 构建一个指定初始容量和负载因子的map 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); this .loadFactor = loadFactor; this .threshold = tableSizeFor(initialCapacity); } // 构建指定初始容量的map public HashMap (int initialCapacity) this (initialCapacity, DEFAULT_LOAD_FACTOR); } // 无参构造，初始容量为16，默认负载因子为0.75。第一次使用时才真正分配存储空间。 public HashMap () this .loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 从一个已有的map构建新map public HashMap (Map<? extends K, ? extends V> m) this .loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false ); }
构造方法中调用了一个名为tableSizeFor的函数，下面一起看下这个方法是做什么的。通过源码注释可以了解，它的作用是根据传入的值，计算返回一个刚好大于这个值的2的整数次幂。
1 2 3 4 5 6 7 8 9 10 11 12 /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor (int cap) int n = cap - 1 ; n |= n >>> 1 ; n |= n >>> 2 ; n |= n >>> 4 ; n |= n >>> 8 ; n |= n >>> 16 ; return (n < 0 ) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1 ; }
比如我们指定容量值是10，那么n = cap - 1 = 9，对应的二进制是1001。
n |= n >>> 1
1 2 3 4 0000 1001 0000 0100 --------- 0000 1101
n |= n >>> 2
1 2 3 4 0000 1101 0000 0011 --------- 0000 1111
n |= n >>> 4
1 2 3 4 0000 1111 0000 0000 --------- 0000 1111
n |= n >>> 8
1 2 3 4 0000 1111 0000 0000 --------- 0000 1111
n |= n >>> 16
1 2 3 4 0000 1111 0000 0000 --------- 0000 1111
最后的n+1，得到结果0001 1111 = 16。刚好大于10的2的整数次幂。
核心方法
添加
HashMap有如下三个添加方法。
1 2 3 public V put (K key, V value) // 添加键值对 public V putIfAbsent (K key, V value) // 添加键值对 public void putAll (Map<? extends K, ? extends V> m) // 将参数m中的键值对全部添加到当前map中
解释一下put方法和putIfAbsent方法的区别：
下面以分析put方法为例。
1 2 3 4 5 6 7 8 9 10 11 12 13 // 添加键值对。 // 如果不存在相同的key，直接添加，并返回null。 // 存在相同的key，覆盖旧值，并返回旧值。 public V put (K key, V value) return putVal(hash(key), key, value, false , true ); } // 添加键值对， // 如果不存在相同的key，直接添加，并返回null。 // 存在相同的key，则保留旧值，并返回旧值。 public V putIfAbsent (K key, V value) return putVal(hash(key), key, value, true , true ); }
根据key的hashCode计算得出hash值，连同key、value一同传给putVal方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果是空表，直接调用扩容方法。 if ((tab = table) == null || (n = tab.length) == 0 ) n = (tab = resize()).length; // 这里的 （n-1）& hash 是为了确定具体存储位置。 // 根据参数key的hash值，计算应该存储在哪个索引处 // 如果该位置上没有存储过键值对，则直接新建一个node，存储在该位置。 if ((p = tab[i = (n - 1 ) & hash]) == null ) tab[i] = newNode(hash, key, value, null ); // 当前位置已经存储节点了。 else { Node<K,V> e; K k; // 判断key是否相同，如果相同，赋值给临时变量e。 // 可以看到这里先比较hash值，然后再用equals方法比较（非null情况）。 // 采用这种比较方式，效率更高。这也是node节点为什么存储hash值的原因。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断是否属于红黑树的节点 // 如果是, 则在红黑树中先查找是否存在该key。 // 如果不存在，直接添加节点到红黑树上，e=null。 // 如果存在，将该节点赋值给临时变量e。 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this , tab, hash, key, value); else { // 新添加的节点，不属于头节点，也不属于红黑树节点 // 遍历链表，如果有key相等的节点，则赋值给临时变量e。 // 如果没有key相等的节点，则在链表尾添加新节点。 // 同时判断链表长度，如果大于等于8，将链表转成红黑树。e=null for (int binCount = 0 ; ; ++binCount) { if ((e = p.next) == null ) { p.next = newNode(hash, key, value, null ); if (binCount >= TREEIFY_THRESHOLD - 1 ) // -1 for 1st treeifyBin(tab, hash); break ; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break ; p = e; } } // 表示要添加的key，在map中已经存在了。 if (e != null ) { // existing mapping for key V oldValue = e.value; // 此处可看出put和putIfAbsent两个方法的区别。 if (!onlyIfAbsent || oldValue == null ) e.value = value; // HashMap中空实现，为了提供给子类LinkedHashMap重写实现。 afterNodeAccess(e); return oldValue; } } // 添加方法属于结构性修改，递增modCount值。 ++modCount; // 当实际存储键值对个数大于临界值(= 容量 x 负载因子），则调用扩容方法。 if (++size > threshold) resize(); // 该方法在HashMap类中是空实现，只要是为了提供给子类LinkedHashMap重写实现。 afterNodeInsertion(evict); return null ; }
总结一下流程：1、是否空表，空表则扩容；2、定位应该存储的索引位置；3、判断该索引处是否有节点、是否是链表头节点、是否属于红黑树节点；4、map中没有相同的key，直接存放；5、map中有相同的key，根据参数onlyIfAbsent判断是否覆盖原值。
哈希函数
接下来看一下哈希函数，可以从两方面来选择使用哪种哈希函数：一个是数据分布是否均匀，也就是哈希碰撞几率的大小，另一个就是能否高效的计算出hash值。不同的应用场景对哈希函数有着不同的要求，比如用于查找的哈希函数主要考虑它映射到小范围的碰撞率，因为几率越大，链表越长，查询效率也就越低。JDK中，HashMap在权衡了效率与碰撞几率的情况下，实现了自己的哈希函数。
1 2 3 4 static final int hash (Object key) int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
解释一下上面的代码，为什么不直接使用key的hashCode作为hash值，而又执行了异或操作？
因为我们平时使用map的时候，存储键值对数量绝大多数都在 2^16 以内。在取余定位的时候，使用的是（n-1）& hash，这个&运算，只有hash值的低16位（甚至更低）参与运算，如果两个key的hash只有高16位有变化，那么此时也会映射到同一索引，产生碰撞。
所以 h >>> 16 取到hashCode高16位，再与hashCode本身异或运算，可以得到更加随机的效果，达到了散列的目的。这里使用异或也是为了更加随机，如果使用 & 、| 都会令结果偏向0或1。
为什么是 (n - 1) & hash？
在定位存储位置的时候，使用的是 (n - 1) & hash。那么为什么要这么写呢？
我们想要把一个数映射到一个给定的范围，通常可以采用除数取余的方式，假设数组长度为16，可以使用 hash % 16，结果在0 ~ 15 之间。这种方法虽然可以将哈希值映射到一个给定范围的确切位置，但不够高效。有一种更加高效的方式 – 位运算。也就是说 (n - 1) & hash 与hash % n是等价的，但这个等价有个前提，那就是n一定是2的整数次幂。可以表示为x%2^n = x&(2^n-1)。
下面举个例子演示一下为什么一定要是2的整数次幂。假设数组长度分别为15和16，分别用来存储hash值0 ~ 14 和 0 ~ 15，那么&运算后的结果如图所示。
可以看到，当数组长度为2的整数次幂时，与hash % 16的结果一样。分布均匀，碰撞几率小，且空间利用合理。具体原因是，n-1的低位二进制全是1，经过(n - 1) & hash的计算结果，可能是偶数，也可能是奇数（这取决于原值的奇偶）。这样便可以保证散列的均匀性。再加上hash函数对key的hashCode高位异或运算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。
当数组长度为奇数时，偶数索引处产生哈希碰撞，而且是不同的哈希值碰撞在一起。需要用链表存储他们。这就大大降低了将来查询的效率。而且有近一半的空间被浪费掉。为什么会产生这种现象，当数组长度为奇数时，那么n-1对应的二进制最后一位一定是0，表示成xxx0，当任何一个数同它 & 运算后得到的结果最后一位仍然是0。看出什么问题没有？索引值二进制最后一位是1的位置（也就是奇数索引），永远不会被用到，造成了空间的浪费。
既然奇数不可以，那么我们能不能采用一个不是2的整数次幂的偶数呢？也是不可以的，我们看个例子。假设数组长度为14，我们向数组中添加元素0 ~ 13（这些key对应的hash仍然是其本身），那么这些元素经过计算后的存储位置如图所示。
当数组长度是非2的整数次幂的偶数时，同一范围下出现很大的碰撞概率的同时，又浪费了很多空间。使用链表解决碰撞问题，又带来查询效率问题。
所以说，当数组长度为2的整数次幂时，不同的key定位到相同的索引几率很小，数据分布均匀。相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就高了。
扩容
下面我们来看一下HashMap的扩容机制。扩容方法主要做了这几件事：1、计算新容量和新临界值；2、基于新容量创建新数组；3、转移数据。首次put元素需要进行扩容为默认容量16，临界值16*0.75=12，以后扩容后的数组长度和临界值都变为原来的两倍。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null ) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0 ; // 旧数组不为null if (oldCap > 0 ) { // 容量已经达到或超过最大值，不再扩容，直接返回旧数组。 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 新数组长度和临界值都设置之前的两倍 else if ((newCap = oldCap << 1 ) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1 ; // double threshold } // 这种情况是在调用两个传递负载因子、初始容量的构造方法产生的。 // 还记得前面分析过这个方法么，this.threshold = tableSizeFor(initialCapacity); // 这时候，临界值记录的是刚好大于initialCapacity的2的整数次幂 // 此时数组还没初始化，用这个值作为新数组容量 else if (oldThr > 0 ) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults // 调用无参构造，容量和负载因子都是默认值。 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int )(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 按照公式计算新临界值 if (newThr == 0 ) { float ft = (float )newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float )MAXIMUM_CAPACITY ? (int )ft : Integer.MAX_VALUE); } threshold = newThr; // 按照扩容的容量新建数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // table变量指向新数组 table = newTab; // 旧数组不为空，可能存储数据，将数据转移到新数组上 if (oldTab != null ) { // 遍历旧数组 for (int j = 0 ; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null ) { oldTab[j] = null ; // 旧数组第j位索引处的节点没有后置节点 if (e.next == null ) // 不用重新计算key的hash值 // 使用节点中存储的hash值，按照hash & (newCap-1)在新数组中定位存储位置 newTab[e.hash & (newCap - 1 )] = e; // 旧数组第j位索引处的节点，如果属于红黑树的节点 // 先拆分红黑树再映射 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this , newTab, j, oldCap); // 只剩最后一种情况：这是一个多于一个节点的链表 // 先对链表进行分组，然后再映射。 else { // preserve order Node<K,V> loHead = null , loTail = null ; Node<K,V> hiHead = null , hiTail = null ; Node<K,V> next; // 遍历链表，根据(e.hash & oldCap) == 0对链表分两组 // 每组一条链表，相对位置不变（旧链表在前边的节点，在新链表一样在前）。 do { next = e.next; if ((e.hash & oldCap) == 0 ) { if (loTail == null ) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null ) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null ); if (loTail != null ) { loTail.next = null ; // 不需要变化位置的链表一组，还留在原数组位置 newTab[j] = loHead; } if (hiTail != null ) { hiTail.next = null ; // 将需要变化位置的链表一组，放到数组中的新位置 newTab[j + oldCap] = hiHead; } } } } } return newTab; }
解释一下对链表的分组操作。首先旧链表会被分成两组，按照(e.hash & oldCap) == 0这个规则去分，一组等于0，一组不等。上面的loHead、lotTail、hiHead、hiTail就是分别指向两条新链表的头尾。
下面解释一下e.hash & oldCap这个表达式的意思。假设现在有一个容量为16的数组，和两个hash值，如下。
(n-1) & hash
&运算结果
0000 1111 & 1101 1001
0000 1001
0000 1111 & 1010 1001
0000 1001
两个hash映射到同一位置，用一条链表存储。此时数组扩容为32。
(n-1) & hash
&运算结果
0001 1111 & 1101 1001（hash1）
0001 1001 （原数组容量 + 原位置）
0001 1111 & 1010 1001（hash2）
0000 1001 （原位置）
由上面的例子，可以得出一个公式：在新数组的位置 = 原数组容量 + 原位置。
扩容后，n-1 = 32 - 1= 0001 1111 ，此时参与计算的位数多了一个1。如果hash值对应位置上也是1，则位置需要变化（也就是根据上面的公式变）。而如果hash值对应位置上是0，则计算结果完全没变化，还在原位置。基于上面的思路，JDK中想出了这样的写法，用来区分需要变位置和不需要变位置的节点。
JDK1.8重写了扩容方法resize，取代了1.7中的rehash操作，避免了rehash引起的死循环及低效的问题。这里简单提一句，死循环是在多线程环境下，扩容时，put操作导致了环形链表，但此时并不会发生错误，只是埋下了祸根。一旦调用get方法，获取这条链表上的节点值的时候，就会一直循环下去。系统CPU占用100%。
查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 // 根据key获取value，如果不存在返回null public V get (Object key) Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } // 根据key获取value，如果不存在返回默认值defaultValue public V getOrDefault (Object key, V defaultValue) Node<K,V> e; return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; } final Node<K,V> getNode (int hash, Object key) Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 哈希表不为空并且定位到的索引处存在头节点 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1 ) & hash]) != null ) { // 比较头节点的key，如果相等直接将头节点返回 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 头节点是否存在后续节点 if ((e = first.next) != null ) { // 头节点是否是红黑树中的节点 if (first instanceof TreeNode) // 从红黑树中查询 return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 以上情况都不是，则遍历整个链表查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null ); } } return null ; }
总结一下查找流程：1、通过key的hash值定位到某个索引；2、如果该索引处存在节点，判断key是否相等；3、如果该头节点是红黑树的根节点，则去红黑树中查找；4、以上情况没查到，则遍历该索引处整个链表，先比较key的hash值，再用equals方法比较key。
删除
有两个删除方法，和一个清空方法。清空操作比较简单，我们重点看删除操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 // 根据指定key删除对应键值对。 // 如果存在，则返回对应的value；如不存在，则返回null。 public V remove (Object key) Node<K,V> e; return (e = removeNode(hash(key), key, null , false , true )) == null ? null : e.value; } // 根据指定key删除对应键值对。只有当value值等于key对应的值才会执行删除操作。 // 删除成功，返回true。 // 删除失败，返回false。这里有两点可能，一是没有找到key对应的键值对；二是value不等于key对应的值。 public boolean remove (Object key, Object value) return removeNode(hash(key), key, value, true , true ) != null ; } final Node<K,V> removeNode (int hash, Object key, Object value, boolean matchValue, boolean movable) Node<K,V>[] tab; Node<K,V> p; int n, index; // 哈希表不为空并且定位到的索引处存在头节点 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1 ) & hash]) != null ) { Node<K,V> node = null , e; K k; V v; // 比较头节点的key，如果相等，则将头节点赋值给临时变量node if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // 头节点是否存在后续节点 else if ((e = p.next) != null ) { // 头节点是否是红黑树中的节点 if (p instanceof TreeNode) // 从红黑树中按key查找，赋值给变量node node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 以上情况都不是，则遍历整个链表查找，并赋值给变量node do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break ; } p = e; } while ((e = e.next) != null ); } } // 这里可以看到两个remove方法，传递参数不同的分支判断 // remove(Object key, Object value)方法，传递过来一个value值 // 如果该值与待删除的节点值相等，则执行删除。 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 待删除的节点属于红黑树，则从红黑树中删除 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this , tab, movable); // 待删除节点如果是链表的头节点，直接将node.next放到数组中 else if (node == p) tab[index] = node.next; // 待删除节点既不是红黑树节点，也不是链表的头结点。 // p是node的前置节点，令p的next指针指向node的下一节点 else p.next = node.next; // 递增modCount，递减size ++modCount; --size; // HashMap中空实现，为了LinkedHashMap重写 afterNodeRemoval(node); return node; } } return null ; }
总结
基于数组、链表、红黑树和哈希函数实现。
允许使用 null 值和 null 键。
键值对是无序的，因为hash值随机。想要保证插入顺序可以使用LinkedHashMap。
除了不同步和允许使用 null 之外，HashMap与Hashtable大致相同。
虽然Hashtable是同步的，但在多线程下建议使用ConcurrentHashMap替代。
因为使用哈希函数定位，存取的效率都很高，时间复杂度为O(1)。
写在最后
其实HashMap的原理很简单，就是通过哈希函数将key映射到数组上，如果出现碰撞，则用链表解决，JDK1.8又新加了一条，为了查询效率，当链表长度大于8转成红黑树。这个想必大家都懂。但Java实现里面有好多细节，比如通过位运算代替取余运算来定位；再比如在存取的过程中，都有比较操作，先比较hash值，再用equals方法比较等等，这些为了性能而设计的点，只有看了源码才能体会到有多精妙。由于时间和能力有限，本篇源码分析并没有面面俱到，讲到的也难免出现错误，希望大家批评指正，一起学习。本文先写到这里了，谢谢各位观看。
