remove 方法
remove 方法的本质是将 key 值所在的节点的值设置为 nu
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }
removeNode 方法
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; // tab 不为空, 数组长度大于 0, 当前节点数据不为 null // 不得不说 hashmap 源码的逻辑还是非常严谨的 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { // node 用来存储当前节点信息 Node<K,V> node = null, e; K k; V v; 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) // 获取节点 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { // 链表查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 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); else if (node == p) // 如果是头节点 // 那么头节点指针指向移除节点的后驱节点 tab[index] = node.next; else // 前驱节点的后驱指针，指向当前节点的后驱指针 p.next = node.next; // 修改次数累加 ++modCount; // 数据长度减少 --size; afterNodeRemoval(node); return node; } } return null; }
removeTreeNode 方法
removeTreeNode 是删除节点的核心方法，删除的时候如果是一个普通节点就可以直接情况，如果是链表的话需要将当前节点删除。如果是红黑树的话，需要删除 TreeNode , 然后进行一次树平衡，或者将树转换为链表。
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; // 获取索引值 int index = (n - 1) & hash; // 获取头节点，即树的根节点 TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; // 当前节点的后驱节点，当前节点的前驱节点保存 TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; // 前驱节点为 null if (pred == null) // 当前是头节点，删除之后，头节点直接指向了删除节点的后继节点 tab[index] = first = succ; else pred.next = succ; if (succ != null) succ.prev = pred; // 如果头节点（即根节点）为空，说明当前节点删除后，红黑树为空，直接返回 if (first == null) return; // 如果头接单不为空，直接调用 root() 方法获取根节点 if (root.parent != null) root = root.root(); if (root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) { // 链表化，英文前面的链表节点完成删除操作，故这里直接返回，即可完成节点删除 tab[index] = first.untreeify(map); // too small return; } // p 当前节点; pl 当前节点左节点，pr 当前节点右节点 // replacement p 节点删除后替代的节点 TreeNode<K,V> p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { // p 节点删除后， 他的左右节点不为空时， 遍历他的右节点上的左子树 // （以下操作先让 p 节点和 s 节点交换位置，然后再找到 replacement 节点替换他 ） TreeNode<K,V> s = pr, sl; while ((sl = s.left) != null) // find successor s = sl; // 通过上述操作 s 节点是大于 p 节点的最小节点（替换它的节点） // 将 s 节点和 p 节点的颜色交换 boolean c = s.red; s.red = p.red; p.red = c; // swap colors // sr s 节点的右节点 TreeNode<K,V> sr = s.right; // pp p 节点的父节点 TreeNode<K,V> pp = p.parent; // 如果 pr 就是 s 节点 if (s == pr) { // p was s's direct parent // 节点交换 p.parent = s; s.right = p; } else { // 获取 s 的父节点 TreeNode<K,V> sp = s.parent; // 将 p 节点的父节点指向 sp, 且 sp 节点存在 if ((p.parent = sp) != null) { // 判断 s 节点的 sp 节点在左侧还是右侧， 将 p 节点存放在 s 节点一侧 if (s == sp.left) sp.left = p; else sp.right = p; } // 将 pr 节点编程 s 节点的右节点，并且 pr 节点存在 if ((s.right = pr) != null) // 将 s 节点编程 pr 节点的父节点 pr.parent = s; } // 因为 s 节点的性质， s 节点没有左节点 // 当 p 节点和 s 节点交换了位置，所以将 p 节点的左几点指向空 p.left = null; // 将 sr 节点编程 p 节点的左节点，并且 sr 节点存在 if ((p.right = sr) != null) // 将 p 节点编程 sr 的父节点 sr.parent = p; // 将 pl 节点编程 s 节点的左节点，并且存在 pl 节点 if ((s.left = pl) != null) // 将 pl 父节点赋值为s pl.parent = s; // s 父节点设置为 pp 并且 pp 节点存在 if ((s.parent = pp) == null) // root 节点为 s root = s; // p 节点等于 pp.left else if (p == pp.left) // pp 的左节点为 s pp.left = s; else // p 节点等于 pp.right // pp 右节点为 s pp.right = s; // sr 不为空 if (sr != null) // 替换节点为 sr replacement = sr; else // 否则替换节点为 p replacement = p; } else if (pl != null) // 如果 pl 节点存在， pr 节点不存在，不用交换位置， pl 节点为替换为 replacement 节点 replacement = pl; else if (pr != null) // 如果 pr 节点存在, pl 节点不存在， 不用交换位置， pr 节点为替换为 replacement 节点 replacement = pr; else // 如果都不存在 p 节点成为 replacement 节点 replacement = p; // 以下判断根据上述逻辑查看，仅以p 节点的当前位置为性质， 对 replacement 节点进行操作 if (replacement != p) { // 如果 replacement 不是 p 节点 // 将 p 节点的父节点 pp 变成 replacement 节点的父节点 TreeNode<K,V> pp = replacement.parent = p.parent; // 如果 pp 节点不存在 if (pp == null) // replacement 变成根节点 root = replacement; else if (p == pp.left) // 如果 pp 节点存在，根据 p 节点在 pp 节点的位置，设置 replacement 节点的位置 pp.left = replacement; else pp.right = replacement; // 将 p 节点所有的引用关系设置为 null p.left = p.right = p.parent = null; } // 如果 p 节点是红色，删除后不影响 root 节点，如果是黑色，找到平衡后的根节点，并且用 r 表示 TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); // 如果 p 是 replacement 节点 if (replacement == p) { // detach // 得到 pp TreeNode<K,V> pp = p.parent; p.parent = null; if (pp != null) { // pp 存在 // 根据 p 节点的位置，将 pp 节点的对应为位置设置为空 if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; } } // 移动新的节点到数组上 if (movable) moveRootToFront(tab, r); }
balanceDeletion 方法
删除节点后的树平衡方法 。
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { // x 当前需要删除的节点 // xp x 父节点 // xpl x 父节点的左子节点 // xpr x 父节点的右子节点 for (TreeNode<K,V> xp, xpl, xpr;;) { if (x == null || x == root) // x 为空或者 x 为根节点 return root; else if ((xp = x.parent) == null) { // 当 xp 为空，说明 x 为根节点，将 x 设置为黑色并且返回 x 节点。 x.red = false; return x; } else if (x.red) { // x节点是红色，无需调整 x.red = false; return root; } else if ((xpl = xp.left) == x) { // 如果x节点为xpl节点 if ((xpr = xp.right) != null && xpr.red) { // 如果xpr节点不为空，且xpr节点是红色的 // 将xpr设置为黑色，xp设置为红色 xpr.red = false; xp.red = true; // 左旋 root = rotateLeft(root, xp); // 重新将xp节点指向x节点的父节点，并将xpr节点指向xp的右节点 xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr == null) // 若xpr节点不存在 // 则将x节点指向xp节点向上调整 x = xp; else { // sl xpr节点的左节点 // sr xpr节点的右节点 TreeNode<K,V> sl = xpr.left, sr = xpr.right; if ((sr == null || !sr.red) && (sl == null || !sl.red)) { // 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的 // 将xpr节点变成红色 xpr.red = true; // 则将x节点指向xp节点向上调整 x = xp; } else { //sr和sl中存在一个红节点 if (sr == null || !sr.red) { //此处说明sl是红节点,将sl节点设置为黑色 if (sl != null) sl.red = false; //将xpr节点设置为红色 xpr.red = true; //右旋 root = rotateRight(root, xpr); //将xpr节点重新指向xp节点的右节点 xpr = (xp = x.parent) == null ? null : xp.right; } if (xpr != null) { //如果xpr节点不为空,让xpr节点与xp节点同色 xpr.red = (xp == null) ? false : xp.red; //当sr节点不为空，变成黑色 if ((sr = xpr.right) != null) sr.red = false; } //存在xp节点 if (xp != null) { //将xp节点设置为黑色 xp.red = false; //进行左旋 root = rotateLeft(root, xp); } //将x节点指向root进行下一次循环时跳出 x = root; } } } else { // symmetric //当x节点是右节点 if (xpl != null && xpl.red) { //当xpl节点存在且为红色 //将xpl变为黑色，xp变为红色 xpl.red = false; xp.red = true; //右旋 root = rotateRight(root, xp); //将xpl节点重新指向xp节点的左节点 xpl = (xp = x.parent) == null ? null : xp.left; } if (xpl == null) //如果xpl节点不存在，则xp节点没有子节点了 //将x节点指向xp节点向上调整 x = xp; else { //sl xpl节点的左节点 //sr xpl节点的右节点 TreeNode<K,V> sl = xpl.left, sr = xpl.right; if ((sl == null || !sl.red) && (sr == null || !sr.red)) { //若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的 //将xpl节点变成红色 xpl.red = true; //则将x节点指向xp节点向上调整 x = xp; } else { //sr和sl中存在一个红节点 if (sl == null || !sl.red) { //此处说明sr是红节点,将sr节点设置为黑色 if (sr != null) sr.red = false; //将xpr节点设置为红色 xpl.red = true; //左旋 root = rotateLeft(root, xpl); //将xpl节点重新指向xp节点的左节点 xpl = (xp = x.parent) == null ? null : xp.left; } //如果xpl节点存在 if (xpl != null) { //使xpl节点与xp节点同色 xpl.red = (xp == null) ? false : xp.red; //如果sl节点存在 if ((sl = xpl.left) != null) //将sl节点变为黑色 sl.red = false; } // 如果xp节点存在 if (xp != null) { // 将xp节点设置为黑色 xp.red = false; // 右旋 root = rotateRight(root, xp); } // 将x节点指向root进行下一次循环时跳出 x = root; } } } } }
线程安全
HashMap 不是线程安全的集合， 如果要使用线程安全的 k-v 集合可以使用 CurrentHashMap.
注意事项
使用 Map 的方法 keySet()/values()/entrySet()返回集合对象时，不可以对其进行添加元素操作，否则会抛出 UnsupportedOperationException 异常。
集合初始化时，指定集合初始值大小解释：HashMap 使用 HashMap(int initialCapacity) 初始化，如果暂时无法确定集合大小，那么指定默认值（16）即可。 initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子（即 loader factor）默认为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）举例：HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素增加而被迫不断扩容， resize()方法总共会调用 8 次，反复重建哈希表和数据迁移。当放置的集合元素个数达千万级时会影响程序性能。
使用 entrySet 遍历 Map 类集合 KV，而不是 keySet 方式进行遍历。说明：keySet 其实是遍历了 2 次，一次是转为 Iterator 对象，另一次是从 hashMap 中取出 key 所对应的value。而 entrySet 只是遍历了一次就把 key 和 value 都放到了 entry 中，效率更高。如果是 JDK8，使用Map.forEach 方法。values()返回的是 V 值集合，是一个 list 集合对象；keySet()返回的是 K 值集合，是一个 Set 集合对象；entrySet()返回的是 K-V 值组合集合。
Map 类集合 K/V 能不能存储 null 值的情况，如下表格：
| **集合类 ** | Key | Value | Super | 说明 |
| hashtable | 不允许为 null | 不允许为 null | Dictionary | 线程安全 |
| ConcurrentHashMap | 不允许为 null | 不允许为 null | AbstractMap | 锁分段技术（JDK8: CAS） |
| TreeMap | 不允许为 null | 允许为 null | AbstractMap | 线程不安全 |
| HashMap | 允许为 null | 允许为 null | AbstractMap | 线程不安全 |
由于 HashMap 的干扰，很多人认为 ConcurrentHashMap 是可以置入 null 值，而事实上，存储null 值时会抛出 NPE 异常
本文总结
- 本文主要是说了 hashmap 的初始化过程，以及 hashcode 的计算方式。对于红黑树转化这部分只代码做了一些简单的代码翻译。
- 对于 hashmap 红黑树这块逻辑由于涉及到数据结构，以后再希望有时间在做一篇文章单独描述。
- 对于 hashmap 拓容，以及红黑树转链表部分也会在后面的更新中补充。
