public Node remove(int key){ int hashValue = https://www.it610.com/article/hash(key); //通过hash函数找到对应的位置 if(hashArray[hashValue]==null){ return null; }//判断是否正确 else{ Node current = null; if(hashArray[hashValue].key = key){ current = hashArray[hashValue]; hashArray[hashValue] = current.next; return current; }else{ current = hashArray[hashValue]; while(current!=null && current.next.key != key){ current = current.next; } current.next = current.next.next; } } }

• 根节点是黑色，其余节点要么黑色要么红色
• 每个红色节点必须有两个黑色子节点
• 所有叶子节点皆为黑色
• 从任一节点到其每个叶子节点的所有简单路径上的黑色节点数量相同
• 插入的新节点为红色

• 被删结点是叶结点（左、右子树都空 ）：只需要将其双亲节点指向他的节点赋值为null即可。
• 被删结点只有1个孩子结点 （左子树空或右子树空）：只需要将其双亲节点指向他的节点直接指向其被删除节点的孩子节点即可
• 被删结点有2个孩子结点（左、右子树都不空）：若直接选择一个子节点替换被删除的节点，可能会导致其不满足排序二叉树的属性，我们可以选择其左子树最大的的节点或右子树最小的节点来替换该节点。

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {private static final long serialVersionUID = 362498820763181265L; static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; //默认负载因子为0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //链表转红黑树阈值，节点数为9时链表转换为红黑树 static final int TREEIFY_THRESHOLD = 8; //红黑树转链表阈值，节点数为6时红黑树转换为链表 static final int UNTREEIFY_THRESHOLD = 6; //只有当table长度超过64时，才进行红黑树的转换 static final int MIN_TREEIFY_CAPACITY = 64; }

• 因为其hash算法实际就是取模，使用 hash & (length - 1)，而实际上 hash % length 等于 hash & ( length - 1) ,所以前提必须是 length 是 2 的 n 次幂。
• 如果数组长度不是2的次幂,计算出的索引特别容易相同,及其容易发生hash碰撞,导致其余数组空间很大程度上并没有存储数据,链表或者红黑树过长,效率降低.

• 因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。说白了就是空间和时间的权衡。
• 链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。

• loadFactor 越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加。
• loadFactor 越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。

//一、链表节点 static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = https://www.it610.com/article/value; this.next = next; } //二、红黑树节点 static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } }

• n 表示数组初始化的长度是 16。
• &（按位与运算）：运算规则：相同的二进制数位上，都是 1 的时候，结果为 1，否则为0。
• ^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为 0，不同为 1。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 校验table是否为空或者length等于0，如果是则调用resize方法进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 通过hash值计算索引位置，将该索引位置的头节点赋值给p，如果p为空则直接在该索引位置新增一个节点即可 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // table表该索引位置不为空，则进行查找 Node e; K k; // 判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，使用binCount统计链表的节点数 for (int binCount = 0; ; ++binCount) { //如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //校验节点数是否超过8个，如果超过则调用treeifyBin方法将链表节点转为红黑树节点， // 减一是因为循环是从p节点的下一个节点开始的 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } //如果e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 将p指向下一个节点 } } //如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue if (e != null) { V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 用于LinkedHashMap return oldValue; } } ++modCount; //如果插入节点后节点数超过阈值，则调用resize方法进行扩容 if (++size> threshold) resize(); afterNodeInsertion(evict); // 用于LinkedHashMap return null; }

final Node[] resize() { // 得到当前数组 Node[] oldTab = table; // 如果当前数组等于null长度返回0，否则返回当前数组的长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //当前阀值点 默认是12(16*0.75) int oldThr = threshold; int newCap, newThr = 0; // 如果老的数组长度大于0 // 开始计算扩容后的大小 if (oldCap > 0) { // 超过最大值就不再扩充了，就只好随你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { // 修改阈值为int的最大值 threshold = Integer.MAX_VALUE; return oldTab; } /* 没超过最大值，就扩充为原来的2倍 1) (newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后容量要小于最大容量 2）oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度16 */ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 阈值扩大一倍 newThr = oldThr << 1; // double threshold } // 老阈值点大于0 直接赋值 else if (oldThr > 0) // 老阈值赋值给新的数组长度 newCap = oldThr; else { // 直接使用默认值 newCap = DEFAULT_INITIAL_CAPACITY; //16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新的resize最大上限 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 新的阀值 默认原来是12 乘以2之后变为24 threshold = newThr; // 创建新的哈希表 @SuppressWarnings({"rawtypes","unchecked"}) //newCap是新的数组长度--》32 Node[] newTab = (Node[])new Node[newCap]; table = newTab; // 判断旧数组是否等于空 if (oldTab != null) { // 把每个bucket都移动到新的buckets中 // 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置 for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { // 原来的数据赋值为null 便于GC回收 oldTab[j] = null; // 判断数组是否有下一个引用 if (e.next == null) // 没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入 newTab[e.hash & (newCap - 1)] = e; //判断是否是红黑树 else if (e instanceof TreeNode) // 说明是红黑树来处理冲突的，则调用相关方法把树分开 ((TreeNode)e).split(this, newTab, j, oldCap); else { // 采用链表处理冲突 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; // 通过上述讲解的原理来计算结点的新位置 do { // 原索引 next = e.next; // 这里来判断如果等于true e这个结点在resize之后不需要移动位置 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 原索引放到bucket里 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 原索引+oldCap放到bucket里 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

final TreeNode getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } final TreeNode find(int h, Object k, Class kc) { TreeNode p = this; do { int ph, dir; K pk; TreeNode pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; // 找到之后直接返回 else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; // 递归查找 else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; }

• 用hash(K)方法计算K的hash值,然后结合数组长度,计算得数组下标;
• 调整数组大小(当容器中的元素个数大于capacity*loadfactor时,容器会进行扩容resize为2n);
• 如果K的hash值在HashMap中不存在,则执行插入,若存在,则发生碰撞;
• 如果K的hash值在HashMap中存在,且它们两者equals返回true,则更新键值对;
• 如果K的hash值在HashMap中存在,且它们两者equals返回false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。

• 调用hash(K)方法(计算K的hash值)从而获取该键值所在链表的数组下标;
• 顺序遍历链表,equals()方法查找相同Node链表中K值对应的V值。

• 两个线程执行put()操作时，可能导致数据覆盖。
• 扩容时导致死循环：只有 JDK7 及以前的版本会存在死循环现象，在 JDK8 中，resize()方式已经做了调整，使用两队链表，且都是使用的尾插法，及时多线程下，也顶多是从头结点再做一次尾插法，不会造成死循环。

推荐阅读

• 

  工作分析中方法分析常用的方法是
• 

  未来中国的第一富豪会是谁？
• 

  冬天木耳泡多久就不能吃了
• 

  p50|华为Mate50新消息：明年6月首发，不仅有望回归5G还有强大新功能
• 

  雅阁哪个颜色比较好看 雅阁怎么样
• 

  科技股如何估值 试试这几个方法
• 

  众享亿家的货是真的吗
• 

  线上英语机构排名前十 商务英语培训机构前十名
• 

  南风未起我遇见你什么意思
• 

  牛仔夹克衣领脏了怎么办 牛仔夹克领子
• 

  梦见丈夫出轨会变成真的吗 梦见丈夫出轨怎么解释
• 

  英国商标 如何在英国注册商标，在哪里注册商标
• 

  尼康d7200自拍功能在哪 尼康d7200照片能洗多大
• 

  app调试分析,蓝牙调试助手app
• 

  独孤一门三皇后真实历史原型：独孤伽罗最有名 隋文帝皇后
• 

  高尔夫场上的草都是什么品种
• 

  小776论坛,776冒险岛论坛有木马
• 

  卫星在太空靠什么做动力
• 

  肃杀之气的拼音 什么叫肃杀之气
• 

  传说中的豹2A7+主战坦克,为何被一些人称为世界最佳？

• Java编程开发|java开发（Class.forName 和 ClassLoader的区别和联系 | 使用场景 | 多方位解析）
• #|Zookeeper后端开发工具Curator的使用 | Curator对节点的增删改查 | ACL权限控制 | 分布式锁 | 分布式计数器 | 附带最新版本下载
• Java编程开发|Java多线程（synchronized | Volatile 和Lock和ReadWriteLock多方位剖析（一））
• java|springBoot自动装配原理
• linux|zookeeper-3.4.14 出现 Client port found: 2181. Client address: localhost. 的解决办法
• java|spring boot报错org.springframework.context.ApplicationContextException:Unable to start Embedded
• Java|Java 8（JDK 1.8）升级更新至 Java 11（JDK 11）/ Java 17（JDK 17）LTS
• java|Spring框架漏洞总结
• spring|Spring Boot Actuator 漏洞复现合集