首先hashmap的继承图
当链表下方数据过多时，hashmap在1.8改为数组加红黑树
进入hashmap的成员变量
private static final long serialVersionUID = 362498820763181265L; /**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; //加载因子0.75 扩容使用，当数量达到 容量 * 负载因子 时， 则扩充当前HashMap的容量 为当前的2倍。 static final float DEFAULT_LOAD_FACTOR = 0.75f; //某个桶的结点数大于1.8时则转化为红黑树 static final int TREEIFY_THRESHOLD = 8; //某个桶的结点数小于6时转化为链表，前提他是红黑树 static final int UNTREEIFY_THRESHOLD = 6; //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。 static final int MIN_TREEIFY_CAPACITY = 64; //将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。 transient Set<Map.Entry<K,V>> entrySet; //元素数量 transient int size; //统计该map修改的次数 transient int modCount; //临界值，也就是元素数量达到临界值时，会进行扩容。 int threshold; //也是加载因子，只不过这个是变量。 final float loadFactor;下面介绍内部类
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; }单向链表结点的数据结构下面是红黑树的数据结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); }通过数组Node与以上两个数据结构形成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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //传入map public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } // final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //取得map的长度 int s = m.size(); if (s > 0) { 判断是否初始化 if (table == null) { // pre-size //求出需要的容量 float ft = ((float)s / loadFactor) + 1.0F; //判断该容量大小是否超出上限。 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); /**对临界值进行初始化，tableSizeFor(t)这个方法会返回大于t值的，且离其最近的2次幂，例如t为29，则返回的值是32**/ if (t > threshold) threshold = tableSizeFor(t); } //如果table已经初始化，则进行扩容操作，resize()就是扩容。 else if (s > threshold) resize(); //遍历，把map中的数据转到hashMap中。 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }先来看看hashmapd类里面属行
内部类
方法
剩余方法与成员属性
下面看看hashmap的核心方法
put:
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) { //tab数组，node是指结点，n数组长度，i是下标 Node<K,V>[] tab; Node<K,V> p; int n, i; //使用的懒初始化，如果判断数组不存在与长度为0则进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /**如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p**/ if ((p = tab[i = (n - 1) & hash]) == null) //经过计算发现没有值就new一个 tab[i] = newNode(hash, key, value, null); else { //如果有值与首结点一样 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; /**为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功，如果添加成功返回null**/ else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点 else { //记录最大数字 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; } //如果链表中有重复的key，e则为当前重复的节点，结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //有重复的key，则用待插入值进行覆盖，返回旧值。 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null //修改次数+1 ++modCount; //实际长度+1，判断是否大于临界值，大于则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict);//移除之前的对象map return null; }1.首先获取Node数组table对象和长度，若table为null或长度为0，则调用resize()扩容方法获取table最新对象，并通过此对象获取长度大小2.判定数组中指定索引下的节点是否为Null，若为Null 则new出一个单向链表赋给table中索引下的这个节点3.若判定不为Null,我们的判断再做分支 -3.1 首先对hash和key进行匹配,若判定成功直接赋予e3.2 若匹配判定失败,则进行类型匹配是否为TreeNode 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e3.3 若以上判定全部失败则进行最后操作,向单向链表中添加数据若单向链表的长度大于等于8,则将其转为红黑树保存，记录下一个节点,对e进行判定若成功则返回旧值4.最后判定数组大小需不需要扩容
接下来看resize方法
final Node<K,V>[] resize() { //之前的数组作为老数组 Node<K,V>[] oldTab = table; //获取数组长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //old的临界值 int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //oldCap > 0也就是说不是首次初始化，因为hashMap用的是懒加载 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //其它情况，扩容两倍，并且扩容后的长度要小于最大值，old长度也要大于16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } 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; @SuppressWarnings({"rawtypes","unchecked"}) //初始化 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //此处自然是把old中的元素，遍历到new中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //临时变量 Node<K,V> e; //当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突 if ((e = oldTab[j]) != null) { //把已经赋值之后的变量置位null，当然是为了好回收，释放内存 oldTab[j] = null; //如果下标处的节点没有下一个元素 if (e.next == null) //把该变量的值存入newCap中，e.hash & (newCap - 1)并不等于j newTab[e.hash & (newCap - 1)] = e; //该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素 else if (e instanceof TreeNode) //把此树进行转移到newCap中 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); /**此处表示为链表结构，同样把链表转移到newCap中，就是把链表遍历后，把值转过去，在置位null**/ else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //如果为0就在原位置如果不是就newTab[j + oldCap] = hiHead; 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; }1.判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回2.若新表大小(oldCap2)小于数组极限大小&老表大于等于数组初始化大小 判定成功则 旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr2当作新数组的大小2.1. 若[2]的判定不成功，则继续判定 oldThr （代表 老表的下一次扩容量）大于0，若判定成功 则将oldThr赋给newCap作为新表的容量2.2 若 [2] 和[2.1]判定都失败,则走默认赋值 代表 表为初次创建3.确定下一次表的扩容量, 将新表赋予当前表4.通过for循环将老表中的值存入扩容后的新表中4.1 获取旧表中指定索引下的Node对象 赋予e 并将旧表中的索引位置数据置空4.2 若e的下面没有其他节点则将e直接赋到新表中的索引位置4.3 若e的类型为TreeNode红黑树类型4.3.1 分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储4.3.2 通过Do循环 不断获取新旧索引的节点4.3.3 通过判定将旧数据和新数据存储到新表指定的位置5.最后返回值为 扩容后的新表。
接下来是remove操作：
public V remove(Object key) { //临时变量 Node<K,V> e; /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作**/ return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /**第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value，不删除key,第四个如果为false，则表示删除后，不移动节点**/ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标 Node<K,V>[] tab; Node<K,V> p; int n, index; //数组不为空，长度大于0，然后获得到要删除key的节点所在是数组下标位置 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { //要删除的结点，e临时变量，K key V value Node<K,V> node = null, e; K k; V v; //如果数组下标的节点正好是要删除的节点，把值赋给临时变量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) //遍历红黑树找到结点返回 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; }get方法
public V get(Object key) { Node<K,V> e; //也是调用getNode方法来完成的 return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { //first 头结点，e 临时变量，n 长度,k 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) { //如果是头结点，则直接返回头结点 if (first.hash == hash && ((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.判定三个条件 table不为Null & table的长度大于0 & table指定的索引值不为Null2.判定 匹配hash值 & 匹配key值 成功则返回 该值3.若 first节点的下一个节点不为Null3.1 若first的类型为TreeNode 红黑树 通过红黑树查找匹配值 并返回查询值3.2若上面判定不成功 则认为下一个节点为单向链表,通过循环匹配值 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; /* * 如果元素数组为空 或者 数组长度小于 树结构化的最小限制 * MIN_TREEIFY_CAPACITY 默认值64，对于这个值可以理解为：如果元素数组长度小于这个值，没有必要去进行结构转换 * 当一个数组位置上集中了多个键值对，那是因为这些key的hash值和数组长度取模之后结果相同。（并不是因为这些key的hash值相同） * 因为hash值相同的概率不高，所以可以通过扩容的方式，来使得最终这些key的hash值在和新的数组长度取模之后，拆分到多个数组位置上。 */ if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 扩容，可参见resize方法解析 // 如果元素数组长度已经大于等于了 MIN_TREEIFY_CAPACITY，那么就有必要进行结构转换了 // 根据hash值和数组长度进行取模运算后，得到链表的首节点 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; // 定义首、尾节点 do { TreeNode<K,V> p = replacementTreeNode(e, null); // 将该节点转换为 树节点 if (tl == null) // 如果尾节点为空，说明还没有根节点 hd = p; // 首节点（根节点）指向 当前节点 else { // 尾节点不为空，以下两行是一个双向链表结构 p.prev = tl; // 当前树节点的 前一个节点指向 尾节点 tl.next = p; // 尾节点的 后一个节点指向 当前节点 } tl = p; // 把当前节点设为尾节点 } while ((e = e.next) != null); // 继续遍历链表 // 到目前为止 也只是把Node对象转换成了TreeNode对象，把单向链表转换成了双向链表 // 把转换后的双向链表，替换原来位置上的单向链表 if ((tab[index] = hd) != null) hd.treeify(tab);//此处单独解析 }
1.做判定 tab 为Null 或 tab的长度小于红黑树最小容量， 判定成功则通过扩容,扩容table数组大小2.做判定 若tab索引位置下数据不为空，判定成功则通过循环将单向链表转换为红黑树存储 2.1 通过Do循环将当前节点下的单向链表转换为红黑树，若下一个不为Null,则继续遍历2.2 构建红黑树，以头部节点定为根节点
关于扩容后链表的排列问题。
(a) 是未扩容时， key1 和 key2 得出的 hash & (n - 1) 均为 5。 (b) 是扩容之后，key1 计算出的 newTab 角标依旧为 5，但是 key2 由于 扩容， 得出的角标 加了 16，即21， 16是oldTab的length，再来看e.hash & oldCap，oldCap.length即n 本身为 0000 0000 0000 0000 0000 0000 0001 0000 ，这个位与运算可以得出扩容后哪些key 在 扩容新增位时1，哪些是0，一个位运算替换了rehash过程，是不是得给100个赞~大概扩容的过程如下：
1.关于（n-1）&hash?
n是数组的长度，是hashmap基表的长度，这个表的长度在定义的时候是2的N次幂，这里n-1用二进制表示各位都是1，然后和hash进行与运算其实就是求hash除以n的余数。hash map默认初始n为16如果此时存入的key的hash为16，那么（n-1）&hash就是15&16结果为0，此时数据的节点就会被放在数组索引0的位置，这也是hashmap的散列算法的最后一步，其实就是讲hash散布到16个表格中。
2.关于为什么进行hash运算解决冲突原因https://blog.csdn.net/weixin_43689776/article/details/99999126
HashMap面试指南 - 孤独烟的文章 - 知乎 https://zhuanlan.zhihu.com/p/76735726
关于并发下put可能丢失数据的情形https://www.imooc.com/article/71730?block_id=tuijian_wz
