文章目录：
1.HashMap源码注释翻译
* Hash table based implementation of the <tt>Map</tt> interface. This
* implementation provides all of the optional map operations, and permits
* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
* class is roughly equivalent to <tt>Hashtable</tt>, except that it is
* unsynchronized and permits nulls.) This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.
翻译一下大概就是在说，这个哈希表是基于 Map 接口的实现的，它允许 null 值和null 键，它不是线程同步的，同时也不保证有序。
* <p>This implementation provides constant-time performance for the basic
* operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
* disperses the elements properly among the buckets. Iteration over
* collection views requires time proportional to the "capacity" of the
* <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
* of key-value mappings). Thus, it's very important not to set the initial
* capacity too high (or the load factor too low) if iteration performance is
* important.
再来看看这一段，讲的是Map 的这种实现方式为 get（取）和 put（存）带来了比较好的性能。但是如果涉及到大量的遍历操作的话，就尽量不要把 capacity 设置得太高（或 load factor 设置得太低），否则会严重降低遍历的效率。
影响 HashMap 性能的两个重要参数：“initial capacity”（初始化容量）和”loadfactor“（负载因子）。简单来说，容量就是哈希表桶的个数，负载因子就是键值对个数与哈希表长度的一个比值，当比值超过负载因子之后，HashMap 就会进行 rehash操作来进行扩容。
· HashMap集合底层结构是数组 + 单向链表 + 红黑树。
· HashMap集合中的key、value均可为 null，其中key是无序不可重复的。
· HashMap集合的默认初始化容量是16，默认加载因子是 0.75，扩容之后是原容量的2倍。
· 如果HashMap集合中某个桶中的结点数超过了8，则单向链表结点会被替换成红黑树结点；当桶中的结点数小于6时，会将树形结点转回单向链表结点。只有当哈希表中的元素数量超过64时，才会进行树形化（即转换成红黑树这种结构）。否则只是进行扩容。
HashMap 的大致结构如下图所示，其中哈希表是一个数组，我们经常把数组中的每一个节点称为一个桶，哈希表中的每个节点都用来存储一个键值对。在插入元素时，如果发生冲突（即多个键值对映射到同一个桶上）的话，就会通过链表的形式来解决冲突。因为一个桶上可能存在多个键值对，所以在查找的时候，会先通过 key 的哈希值先定位到桶，再遍历桶上的所有键值对，找出 key 相等的键值对，从而来获取 value。
2.HashMap中的属性
//默认的初始容量为 2^4=16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大的容量上限为 2^30 static final int MAXIMUM_CAPACITY = 1 << 30; //默认的加载因子为 0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //变成树型结构的临界值为 8 static final int TREEIFY_THRESHOLD = 8; //恢复链式结构的临界值为 6 static final int UNTREEIFY_THRESHOLD = 6; //当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突 static final int MIN_TREEIFY_CAPACITY = 64; //哈希表 transient Node<K,V>[] table; //哈希表中键值对的个数 transient int size; //哈希表被修改的次数 transient int modCount; //它是通过 capacity*load factor 计算出来的，当 size 到达这个值时，就会进行扩容操作 int threshold; //负载因子，决定了HashMap集合的数据密度 //负载因子过大，发生碰撞的几率会越高 //负载因子过小，就越容易触发扩容，扩容自然也会影响性能 //按照其他语言的参考及研究经验，会考虑将负载因子设置为0.75，此时平均检索长度接近于常数 final float loadFactor;
下面是 Node 类的定义，它是 HashMap 中的一个静态内部类，哈希表中的每一个节点都是 Node 类型。我们可以看到 Node 类中有4 个属性，其中除了 key 和
value 之外，还有hash和next 两个属性。hash 是用来存储 key 的哈希值的，next是在构建链表时用来指向后继节点的。
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) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
3.HashMap中的方法
3.1 构造方法
关于HashMap源码中的构造方法，无非是在更改初始化容量、加载因子这些参数。这里就不再多说了。（主要是后面的get、put方法）
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 } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
3.2 get方法
get方法首先是创建了一个 Node 结点对象，然后其中调用了 getNode 方法，所以我们着重来看一下这个 getNode 方法。
这个 getNode() 方法首先：如果哈希表不为空 && key 对应的桶上不为空，然后根据哈希表元素个数与哈希值求模（使用的公式是 (n - 1) &hash ）得到 key 所在的桶的头结点，如果头结点恰好命中（是我们要get的那个key），则直接返回。如果头结点没有命中，则继续向后续结点进行判断，如果头节点恰好是红黑树节点TreeNode，就调用红黑树节点的 getTreeNode() 方法，否则就执行 do-while 遍历链表节点。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //如果哈希表不为空 && key 对应的桶上不为空 if ((tab = table) != null && (n = tab.length) > 0 && //根据哈希表元素个数与哈希值求模（ 使用的公式是 (n - 1) &hash ）得到 key 所在的桶的头结点 (first = tab[(n - 1) & hash]) != null) { //是否直接命中 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; }
get方法实现原理叙述：假如我们调用原型是map.get("a")，首先会调用 a 的 hash() 方法得到 a 所对应的哈希值，然后通过哈希算法 tab[(n-1) & hash] 转换成桶下标（数组下标），通过这个桶下标快速定位到当前桶结点上，如果比对成功（hashCode、equals都返回true），则返回这个桶结点，如果当前桶结点上什么都没有则返回null。如果当前桶结点没有直接命中，它下面还挂载了其他结点，则继续判断后续结点，为红黑树结构则转为红黑树的get方法获取结点；如果不是则为普通单向链表结构，此时拿着a 和单向链表上的每一个结点进行 equals 方法比对（因为hashCode只有比对成功才会到当前桶结点下继续比对），有一个equals返回 true 则比对成功，返回对应的结点，比对不成功最终返回 null。
3.3 put方法
put 方法的具体实现是在 putVal 方法中，所以我们重点看下面的 putVal 方法。
第一个if判断，我们一看就知道：做的是哈希表是否为空的判断，如果为空，调用 resize 方法，这个方法作用就是新创建一个哈希表。
第二个if判断：如果要插入的键值对的key对应的哈希值与当前桶结点的哈希值比对为null（不冲突），则直接为这个key创建一个新结点newNode()插入就行了。
下面走到else：与第二个if相反，走到else则说明，要插入的键值对与当前桶结点发生冲突了。if是说如果桶上结点的key与我们要插入的key重复，直接确定插入的位置就是该结点（e = p）。else if是指采用红黑树方法则调用红黑树对应的方法进行插入。else表示不是红黑树，那只能是传统的单向链表结构，只有桶上结点在上面的if中比对不成功，才会走到这个else，它执行的就是将要插入的key与当前桶下挂载的结点一一进行比对，如果比对到链表末尾还没找到重复的key，则newNode创建新结点将要插入的key添加到链表末尾。如果链表长度超过临界值，则转为红黑树。else的最后如果找到了重复的key，就break跳出。
else下面的if：就是说明此时已经找到了（我们要插入的key与桶中某个结点的key相等），那么就将要插入key对应的value值覆盖掉原先的旧值，同时返回覆盖掉的那个旧值。
最后的if则是进行是否扩容的判断。
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<K,V>[] tab; Node<K,V> p; int n, i; //如果哈希表为空，则先创建一个哈希表 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果当前桶没有碰撞冲突，则直接把键值对插入，完事 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //如果桶上节点的 key 与当前 key 重复，那你就是我要找的节点了 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果是采用红黑树的方式处理冲突，则通过红黑树的 putTreeVal 方法去插入这个键值对 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //否则就是传统的单向链表结构 else { for (int binCount = 0; ; ++binCount) { //到了链尾还没找到重复的 key，则说明 HashMap 没有包含该键 if ((e = p.next) == null) { //创建一个新节点插入到尾部 p.next = newNode(hash, key, value, null); //如果链的长度大于 TREEIFY_THRESHOLD 这个临界值，则把链变为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //找到了重复的 key if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //这里表示在上面的操作中找到了重复的键，所以这里把该键的值替换为新值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //判断是否需要进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
put方法实现原理叙述：如果哈希表为null，则创建哈希表；通过计算哈希值确定要映射到哪个桶，如果要插入的key与当前桶没有冲突，则直接插入；如果要插入的key与当前桶上结点冲突，则处理碰撞冲突（如果是红黑树则采用红黑树方法进行插入；否则就是单向链表，对当前桶上结点一一遍历，如果最终都不冲突，则将该key插入到链表末尾；如果链表长度达到临界值，则转为红黑树）；如果桶中存在重复的键，则将该键的旧值替换为要插入的新值。最终判断size是否大于阈值，大于则执行扩容操作。
3.4 remove方法
remove 方法的具体实现在 removeNode 方法中，所以我们重点看下面的 removeNode 方法。
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } 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; //如果当前 key 映射到的桶不为空 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，则直接命中 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); } } //比对找到的 key 的 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); //使用链表的操作来删除桶上节点 else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
