看本篇文章之前如果没有看过红黑树原理建议提前阅读红黑树原理分析，hashmap源码分析前菜
JDK1.2版本，线程不安全，运行效率快；允许使用null作为key和value
存储结构：JDK1.8之前（数组+链表）；JDK1.8之后（数组+链表+红黑树）
源码分析：
默认参数
参数解释默认值DEFAULT_INITIAL_CAPACITY默认初始容量，必须是2的次幂1<<4MAXIMUM_CAPACITY最大容量1<<30DEFAULT_LOAD_FACTOR默认加载因子0.75fTREEIFY_THRESHOLD链表转换为红黑树的门槛8UNTREEIFY_THRESHOLD红黑树转换为链表的门槛6MIN_TREEIFY_CAPACITY转换为树的最小表容量，最小为4*TREEIFY_THRESHOLD64tableNode<K,V>[]第一次使用时初始化，长度必须为2的次幂entrySetSet<Map.Entry<K,V>>，保存缓存的entry的set集合size包含键值对的数量modCount记录被修改的次数threshold如果尚未分配表数组，则字段保留初始阵列容量，或零表示默认初始容量。loadFactor加载因子 构造函数 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 } class Node & TreeNode 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; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { 0 Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } 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); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } put()方法 public V put(K key, V value) { //计算key的hash值，直接调用putval()方法 return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab table //p 数组中node，存在链表或树，即为链表的头node，或树的根node Node<K,V>[] tab; Node<K,V> p; int n, i; //如果原有table等于null或原有table的长度为0，则初始化 if ((tab = table) == null || (n = tab.length) == 0) //调用resize()初始化table，记录table长度 n = (tab = resize()).length; //如果待插入的hash值对应数组位置为null,则说明数组内对应位置没有node，则直接将值插入数组即可 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //如果待插入的hash值对应数组位置已有node，则进行链表插入或树插入 else { Node<K,V> e; K k; //如果待插入node和数组中对应位置的hash和key相同，则记录e为待插入节点，用于value更新 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果数组中第一个node为树node，则进行树的node插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //进行链表插入 else { //遍历链表，记录链表节点数，并将待插入node插入到链表的尾部 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; } //如果链表内存在相同hash和key，则记录e为待插入节点，用于更新value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果允许更新已有key的value，或原有value为空，则更新value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //访问回调，将node插入到链表尾部 afterNodeAccess(e); return oldValue; } } ++modCount; //如果插入新node后size大于阈值，则resize() if (++size > threshold) resize(); // Callbacks to allow LinkedHashMap post-actions //允许LinkedHashMap post操作的回调 afterNodeInsertion(evict); return null; } final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //获取原有table的容量和阈值 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //如果原有table的容量大于0，则说明是原有table有值，执行扩容 if (oldCap > 0) { //原有table的容量超过最大容量，则阈值设置为Integer的最大值，数据不变 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //新容量扩容为原有容量的2倍后<最大容量，并且原有table的容量>=初始容量，则扩容为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //原有table未初始化，并且在调用构造函数的时候设置了阈值，则初始化容量为阈值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults //原有table未初始化，设置容量和阈值为默认值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果阈值为0 if (newThr == 0) { //根据加载因子计算阈值 float ft = (float)newCap * loadFactor; //如果容量和tf小于最大容量，则设置阈值为刚计算的tf newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //如果原有table为空，此处为初始化table，否则为构建的是扩容后的table，并赋值给table变量 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //如果原有table不为空，则将原有table的node赋值给新的table if (oldTab != null) { //遍历原有table里的所有node for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //将不为空的node复制到新的table if ((e = oldTab[j]) != null) { //将原有的node引用清空，便于GC oldTab[j] = null; //如果当前node的不存在下一个节点，也就是当前node位置不存在链表或树 if (e.next == null) //重新计算node的hash值，并将node复制到新的table中 newTab[e.hash & (newCap - 1)] = e; //如果当前节点为treeNode，则将原来的红黑树拆分成新的红黑树 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //此时，当前node位置存在链表结构，并且node作为所在链表的头部 else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; //遍历链表内所有node do { next = e.next; //node的hash值与原有容量进行与运算，判断node移动到新数组中对应位置是否需要改变 //此处采用尾插法 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); //清除node无用链接，并将不换位置节点组成的链表放在新数组中对应为的位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //清除node无用链接，将需要换位置的节点组成的链表放在新数组中，索引为原有索引+原有tbale容量 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; //this是待插入node，parent是node的属性parent，下句代码的目的是查找根节点 TreeNode<K,V> root = (parent != null) ? root() : this; //遍历红黑树，查找插入位置 for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } //初始插入 TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; //自平衡调整并且将红黑树根node放在数组对应位置一个元素 moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //如果table为空或table的长度<table转换树的阈值容量，则新建table或扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //通过hash计算存放数组上的位置，并将该位置的node赋值给e else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //遍历树或链表 do { //将遍历的node转换为树node，将所有node构成双向链表 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); if ((tab[index] = hd) != null) //将双向链表转换为树 hd.treeify(tab); } } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { return new TreeNode<>(hash, key, value, next); } //将链表node转换为树node TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); } final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; //遍历需要转换为树的双向链表,x为头node， for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; //如果根node为空，则设置x为根节点， if (root == null) { x.parent = null; x.red = false; root = x; } //如果根node不为空，node x为待插入node，继续构建红黑树 else { K k = x.key; int h = x.hash; Class<?> kc = null; //遍历已有红黑树 for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; //如果hash相同，则通过compareTo进行比较 else if ((kc == null && //获取k的Class (kc = comparableClassFor(k)) == null) || //通过compareTo比较k和pk (dir = compareComparables(kc, k, pk)) == 0) //当k和pk的hash和comparaTo都相同时，系统采用identityHashCode来保证排序规则的一致性 dir = tieBreakOrder(k, pk); //初始插入 TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; //红黑树自平衡调整 root = balanceInsertion(root, x); break; } } } } //将红黑树根node调整到数组的对应位置的第一个元素 moveRootToFront(tab, root); } /** * Returns x's Class if it is of the form "class C implements * Comparable<C>", else null. */ //获取x的Class static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } /** * Returns k.compareTo(x) if x matches kc (k's screened comparable * class), else 0. */ @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable static int compareComparables(Class<?> kc, Object k, Object x) { //如果x的Class为空返回0，如果x的Class==kc，将k强转为Comparable，通过compareTo进行比较k和x return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); } static int tieBreakOrder(Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; } static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) { x.red = true; //变量解释： //xp为x的父node //xpp为x的父node的父node //xppl为x的父node的父node的左node，xppr同理 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //红黑树原理情况1，红黑树原理见我写的红黑树原理一篇 //如果x节点无父node，意思是x为根node，设置颜色为黑，返回根node x if ((xp = x.parent) == null) { x.red = false; return x; } //红黑树原理情况2 //如果xp为黑色或者xpp为null，说明二叉树就两层，直接返回root else if (!xp.red || (xpp = xp.parent) == null) return root; //如果xp为xppl if (xp == (xppl = xpp.left)) { //红黑树原理情况3 //如果xppr不为空且xppr为红色，则调整颜色 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } //红黑树原理情况4 //如果xppr为空或xppr为黑色 else { //红黑树原理情况4.2 //如果x是xp的右node if (x == xp.right) { //进行左旋操作 root = rotateLeft(root, x = xp); //更新xpp xpp = (xp = x.parent) == null ? null : xp.parent; } //红黑树原理情况4.1 //如果xp不为空，调整xp颜色 if (xp != null) { xp.red = false; //如果xpp不为空，调整xpp颜色，右旋 if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } //如果xp不是xppl,即xp是xppr else { //红黑树原理情况3 //如果xppl不为空，xppl为红色则调整颜色 if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } //否则 else { //红黑树原理情况4.2 //如果x为xp的左节点，则右旋，更新xpp if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //红黑树原理情况4.1 //如果xp不为空，调整xp为黑色， if (xp != null) { xp.red = false; //如果xpp不为空，则调整xpp为红色，左旋 if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } } /** * Ensures that the given root is the first node of its bin. */ static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; //如果红黑树根root不是数组对应位置的第一个元素，则进行调整 if (root != first) { Node<K,V> rn; tab[index] = root; TreeNode<K,V> rp = root.prev; if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } //进行红黑树性质校验 assert checkInvariants(root); } } static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; } static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; } static <K,V> boolean checkInvariants(TreeNode<K,V> t) { TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, tb = t.prev, tn = (TreeNode<K,V>)t.next; if (tb != null && tb.next != t) return false; if (tn != null && tn.prev != t) return false; if (tp != null && t != tp.left && t != tp.right) return false; if (tl != null && (tl.parent != t || tl.hash > t.hash)) return false; if (tr != null && (tr.parent != t || tr.hash < t.hash)) return false; if (t.red && tl != null && tl.red && tr != null && tr.red) return false; if (tl != null && !checkInvariants(tl)) return false; if (tr != null && !checkInvariants(tr)) return false; return true; }