摘要：表示该类本身不可比表示与对应的之间不可比。当数目满足时，链表将转为红黑树结构，否则继续扩容。至此，插入告一段落。当超出时，哈希表将会即内部数据结构重建至大约两倍。要注意的是使用许多有这相同的键值肯定会降低哈希表性能。
回顾上期✈观光线路图：putAll() --> putMapEntries() --> tableSizeFor() --> resize() --> hash() --> putVal()...
本期与您继续一起前进：putVal() --> putTreeVal() --> find() --> balanceInsertion() --> rotateLeft()/rotateRight() --> treeifyBin()...
// 为了找到合适的位置插入新节点，源码中进行了一系列比较。
final TreeNode putTreeVal(HashMap map, Node[] tab,
int h, K k, V v) {
Class kc = null;
boolean searched = false;
TreeNode root = (parent != null) ? root() : this; // 获取根节点，从根节点开始遍历
for (TreeNode 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 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 xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node xpn = xp.next;
TreeNode 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)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
当前节点hash值(ph)与插入节点hash值(h)比较，
若ph > h(dir=-1)，将新节点归为左子树;
若ph < h(dir=1)，右子树;
否则即表示hash值相等，然后又对key进行了比较。
“kc = comparableClassFor(k)) == null”表示该类本身不可比（class C don"t implements Comparable）；“dir = compareComparables(kc, k, pk)) == 0”表示k与pk对应的Class之间不可比。searched为一次性开关仅在p为root时生效，遍历比较左右子树中是否存在于插入节点相等的。
最后比到tieBreakOrder()中的“System.identityHashCode(a) <= System.identityHashCode(b)”，即对象的内存地址来生成的hashCode相互比较。堪称铁杵磨成针的比较。
这里循环的推进是靠“if ((p = (dir <= 0) ? p.left : p.right) == null)”，之前千辛万苦比较出的dir也在这使用。直到为空的左/右子树节点，插入新值（新值插入的过程参考下图理解）。
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;
}
有没有发现，如果当你看懂putTreeVal，类比find是不是变得很好理解了呢？
static TreeNode balanceInsertion(TreeNode root,
TreeNode x) {
x.red = true; // x为红
for (TreeNode xp, xpp, xppl, xppr;;) {
// x为根
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// x父节点为黑 || x父节点为根（黑）
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//
if (xp == (xppl = xpp.left)) {
// ①
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// ②
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
在插入新值后，可能打破了红黑树原有的“平衡”，balanceInsertion()的作用就是要维持这种“平衡”，保证最佳效率。所谓的红黑树“平衡”即：
①：所有节点非黑即红；
②：根为黑，叶子为null且为黑，红的两子节点为黑；
③：任一节点到叶子节点的黑子节点个数相同；
下面，以“(xp == (xppl = xpp.left))”简(chou)单(lou)的给大家画个图例（其中①②与源码注释相对应）。
图②中打钩的都是合格的红黑树其实，图②右边方框内为左旋右旋节点关系变化图解。
// 左旋 与 右旋
static TreeNode rotateLeft(TreeNode root, TreeNode p) {
TreeNode 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; // p为pp左子节点
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
static TreeNode rotateRight(TreeNode root, TreeNode p) {
TreeNode 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;
}
左旋右旋过程包含在上面的图例中了，另附上两张网上看到的动图便于大家理解。
同时，在线红黑树插入删除动画演示【点我】，还不理解的童鞋可以亲自直观的试试。
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
do {
TreeNode 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);
}
}
putVal()的treeifyBin()在链表中数目大于等于“TREEIFY_THRESHOLD - 1”时触发。当数目满足MIN_TREEIFY_CAPACITY时，链表将转为红黑树结构，否则继续扩容。treeify()类似putTreeVal()。
至此，HashMap插入告一段落。有误或有读不懂的地方欢迎交流。时间有限，江湖再见。
更多有意思的内容，欢迎访问笔者小站： rebey.cn
彩蛋
附上前一段时间翻译的HashMap源码开篇注释，将开头作为总结。也算收尾呼应吧。
/**
* Hash table based implementation of the Map interface. This
* implementation provides all of the optional map operations, and permits
* null values and the null key. (The HashMap
* class is roughly equivalent to Hashtable, 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接口。该接口提供了所有可选的map操作，且允许键、值为空。（HashMap近似Hashtable，除了异步和
* 允许空值。）HashMap无法保证map的顺序；尤其是持久不变。（译者注：比如rehash。）
*
* This implementation provides constant-time performance for the basic
* operations (get and put), assuming the hash function
* disperses the elements properly among the buckets. Iteration over
* collection views requires time proportional to the "capacity" of the
* HashMap 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.
*
* 在哈希函数将元素恰当的分布在桶中的情况下，接口提供了稳定的基础操作（get和put）。
* 遍历集合的时间与HashMap实例的 “容量”(hash桶的数量) + “大小”（键值对数量）的和成正比。
* 因此，当循环比重较大时，初始容量值不能设的太大（或者负载因子太小）是非常重要的。
*
*
An instance of HashMap has two parameters that affect its
* performance: initial capacity and load factor. The
* capacity is the number of buckets in the hash table, and the initial
* capacity is simply the capacity at the time the hash table is created. The
* load factor is a measure of how full the hash table is allowed to
* get before its capacity is automatically increased. When the number of
* entries in the hash table exceeds the product of the load factor and the
* current capacity, the hash table is rehashed (that is, internal data
* structures are rebuilt) so that the hash table has approximately twice the
* number of buckets.
*
* 两个参数影响着HashMap实例：“初始容量”和“负载因子”。“初始容量”指的是哈希表中桶的数量，在哈希表创建的同时初始化。
* “负载因子”度量着哈希表能装多满（译者注：相对于桶的形象概念，建议参看网上hashMap结构图理解）直到在自动扩容。
* 当超出时，哈希表将会rehashed（即内部数据结构重建）至大约两倍。
*
*
As a general rule, the default load factor (.75) offers a good
* tradeoff between time and space costs. Higher values decrease the
* space overhead but increase the lookup cost (reflected in most of
* the operations of the HashMap class, including
* get and put). The expected number of entries in
* the map and its load factor should be taken into account when
* setting its initial capacity, so as to minimize the number of
* rehash operations. If the initial capacity is greater than the
* maximum number of entries divided by the load factor, no rehash
* operations will ever occur.
*
* 一般来说，默认负载因子（0.75）在时间和空间之间起到了很好的权衡。更大的值虽然减轻了空间负荷却增加了查找花销
* （在大多数HashMap操作上都有体现，包括get和put）。当设置map初始容量时，需要考虑预期条目数和它的负载因子
* 使得rehash操作次数最少。如果初始容量大于最大条目数/负载因子，甚至不会发生rehash。
*
*
If many mappings are to be stored in a HashMap
* instance, creating it with a sufficiently large capacity will allow
* the mappings to be stored more efficiently than letting it perform
* automatic rehashing as needed to grow the table. Note that using
* many keys with the same {@code hashCode()} is a sure way to slow
* down performance of any hash table. To ameliorate impact, when keys
* are {@link Comparable}, this class may use comparison order among
* keys to help break ties.
*
* 如果大量的键值对将存储在HashMap实例中，使用一个足够大的容量来初始化远比让它自动按需rehash扩容的效率高。
* 要注意的是使用许多有这相同hashCode()的键值肯定会降低哈希表性能。为了降低影响，当key支持Comparable接口时，
* 在keys间比较排序来打破瓶颈。
*
*
Note that this implementation is not synchronized.
* If multiple threads access a hash map concurrently, and at least one of
* the threads modifies the map structurally, it must be
* synchronized externally. (A structural modification is any operation
* that adds or deletes one or more mappings; merely changing the value
* associated with a key that an instance already contains is not a
* structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the map.
*
* HashMap是非线程安全的。如果多线程同时访问一个哈希表，并且至少一个线程在修改map结构是，必须在外加上
* synchronized关键字。（结构化修改包括任何增删一个或者多个键值对；只修改一个已存在的key的值不属于
* 结构修改。）典型的是用同步对象封装map实现。
*
* If no such object exists, the map should be "wrapped" using the
* {@link Collections#synchronizedMap Collections.synchronizedMap}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the map:
* Map m = Collections.synchronizedMap(new HashMap(...));
*
* 如果没有这样的对象，map需要使用Collections.synchronizedMap方法封装。最好室在创建的时候，防止意外
* 异步访问map，如：Map m = Collections.synchronizedMap(new HashMap(...));
*
* The iterators returned by all of this class"s "collection view methods"
* are fail-fast: if the map is structurally modified at any time after
* the iterator is created, in any way except through the iterator"s own
* remove method, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
* future.
*
* 迭代器返回了类所有“集合视图方法”是fail-fast（错误的原因）：迭代器创建后，在任何时候进行结构化修改将会抛出
* ConcurrentModificationException，不包括迭代器本身的remove方法，因此，在并发修改时，迭代器宁
* 可快速而干净的抛错，也不任意存在，在不确定的行为，在不确定的时间的未来。（译者注：意会下吧各位- -）
*
*
Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw ConcurrentModificationException on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: the fail-fast behavior of iterators
* should be used only to detect bugs.
*
* 迭代器不能保证fail-fast行为，一般而言，在异步并发修改面前，不可能做 任何严格的保证。Fail-fast迭代器尽力地抛
* ConcurrentModificationException。因此，编写一个依赖于这个异常正确性的程序是错误的：
* fail-fast行为只是用来检测BUG.
*
*
This class is a member of the
*
* Java Collections Framework.
*
* @param the type of keys maintained by this map
* @param the type of mapped values
*
* @author Doug Lea
* @author Josh Bloch
* @author Arthur van Hoff
* @author Neal Gafter
* @see Object#hashCode()
* @see Collection
* @see Map
* @see TreeMap
* @see Hashtable
* @since 1.2
*/
