1、初始化的时候，只是指定了负载因子为0.75.
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
hashmap的计算hash值得方式：key得hashcode和hashcode得高16位异或，因为hashcode往右移动了16尾后，其高16位都是0，所以这个计算hashcode得方式就是，hashcode的高16位和低16位进行异或。
为什么则会么做？
很容易想到的hash算法是：hashcode % table长度，也就是取余算法。但是取余算法效率并不高。所以hashmap采用的方式是：hashmap维护的node数组的长度永远是2的n次方。如此数据的hash值 & （node数组长度 - 1)得到的值就是取余效果。这也就对直接取模做的一个优化。
而为什么要hashcode高低16位进行异或呢？因为当node数组长度比较小，而hashcode的值比较大的时候，直接hashcode & (node数组长度 - 1）运算，hashcode的高16位是不会参加运算的，因为node数组长度 - 1的高16位都是0。所以hashcode的高低16位进行异或，就达到了高16位和低16位都参与运算的效果，让hash算法更加均匀。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table长度为0则进行resize方法扩容。扩容方法下面单独研究
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果这个数组的这个位置没有node
// hash和（数组长度 -1）进行与运算，达到取模的效果
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// node数组该位置的的node的key和put的key相同，则替换value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 红黑树，则进行树的操作，暂时不细讲
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// l链表的尾部为null，则放到这里
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// static final int TREEIFY_THRESHOLD = 8;
// 当bincount为7的时候，也就是这个链表的长度已经为8，则再插入新元素，则进行树化。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 当前元素和put的元素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;
// 这个方法是null的，linkedhashmap会实现这个方法
afterNodeAccess(e);
return oldValue;
}
}
// modCount记录hashmap结构变化次数，这个值用于迭代的时候快速失败，就是说迭代的时候一旦发现这个值变了，则认为hashmap的结构变了，则迭代失败报错。
++modCount;
// put一个元素后++size， threshold保存的是，hashmap实际可以保存的大小，threshold = table的lenght * 负载因子，如果满了，则扩容。所以说，扩容这个操作是put元素后进行的，而不是put前进行的
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容是一个很有意思的操作。
因为数组长度为2的n次方，所以（旧数组长度 - 1 & hash值）和（新数组长度 - 1 & hash值），要不不变，要不就结果多了一个高位1。
比如：2的n次方的二进制是这样的：100000，扩容两倍，也就是往左移动一位，变成了1000000。100000 - 1 = 011111， 1000000-1 = 01111111，再跟hash进行&操作，低位都是一样的，也就高位多了一个1。
当e.hash & oldCap的值不为0，因为0ldCap是2的n次方，也就是，只有最高为为1，其他都为0，比如：十进制16，二进制位10000，所以，e.hash & oldCap值不为0，则说明e.hash的第5位必定为1，e.hash & (newCap - 1)计算的结果和e.hash & (oldCap - 1)的结果区别就是，高位多了一个1，也就是位置 + oldCap（高位为1，其他都是0），很巧妙。
想一下：这样计算，还是计算的，感觉和直接(newCap - 1) & hash值计算位置，差不多啊。
答：如果直接（newCap -1 ) & hash，那么还需要，根据这个位置，找到那条链表，然后，从头往下遍历，找到链表的底端，然后添加到底部，这个遍历到底部的过程就是性能消耗的过程，而如果直接，通过高位是否是1来判定，然后扩容的时候，一个链表直接化成两个链表，这是一个连续的过程，不需要重复遍历，所以就没有从上往下找到链表底端插入元素的过程。
如果如果直接（newCap -1 ) & hash，然后根据这个位置，找到那条链表，然后直接插入到链表的头部，这样，虽然，没有了遍历链表的性能损耗，但是，扩容之后，链表顺序就反了，以前在尾部的元素，变成了链表的头部了。这应该是jdk7的扩容方法。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap为扩容前node数组的大小
if (oldCap > 0) {
// 如果扩容前node数组已经是int范围内最大的2的n次方了，则不进行扩容，只是把threshold改成最大整数
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 扩容两倍容量
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
// 第一个初始化扩容的时候，进入这里，数组长度为16，thread为16 * 0.75 = 12
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;
if (oldTab != null) {
// 需要把旧数组的元素放到新数组，这里很巧妙
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 旧数组指定位置赋值null，加速垃圾回收
oldTab[j] = null;
// 该位置不是链表，不是树，只是单纯一个元素
if (e.next == null)
// 直接hash取模得到新位置
newTab[e.hash & (newCap - 1)] = e;
// 如果这个位置是红黑树，则树操作，不细讲
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
// 如果hash值 & 旧数组长度为 0，则扩容后数组的index不变
//loHead和loTail指定的是扩容后位置不变的一条链表
// hiHead和hiTail 指定的是扩容后位置变化的链表
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;
}
// 扩容后位置变化的链表，放到的新数组位置为：旧数组位置 + 旧数组长度。
// 因为取模后高位加1，其他都没变，高位加1，也就是加上旧数组长度，10000这种。比如，原来取模后是1001，新取模后为：1001 + 10000 = 11001。
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结扩容方法：
1、扩容大小，扩容成两倍，也就是二进制的最高位往左移动了一位，这种方式对链表找位置很巧妙。
2、然后对数据进行重新hash找位置。没有链表的数据直接hash取模找位置，有链表的，直接和原数组长度&运算，判定高位是否是1，因为，2的n次方长度，扩容2倍，&运算取模的时候，变化只和高位有关，然后，是1，则位置+原数组长度，不是1，则还在原来位置。如此，一个链表变成了两个链表，并且，保证了链表的顺序。
树化的代码
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY 最小树化大小，默认是64
// 如果，hashmap容量小于64，则只会扩容，不会树化，因为容量太小，没有必要树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
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);
if ((tab[index] = hd) != null)
// 这里才是真正的树化
hd.treeify(tab);
}
}
// 这里不深究
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
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;
// 根据hash值，判定是树的左边还是右边
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
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;
}
}
}
}
moveRootToFront(tab, root);
}
问题：为什么hashmap默认长度是16。
答：
1、首先，长度必须是2的n次方，这样，不管是&运算就能取模，还是后面的直接判定高位是否是1进行扩容，都需要这个特性保证。
2、至于为什么是2的4次方，长度位16，则可以存储，16 * 0.75 = 12个元素。这个不大也不小，如果是2的3次方，就是8，可以存储 8 * 0.75 = 6个元素，很容易就会产生扩容。同理，如果是2的5次方，32 * 0.75 = 24个元素，有点浪费空间了。
2、hashmap为什么链表长度大于8就转成红黑树， 小于6则转成链表。
答：如果太大，比如设一个16，则遍历链表性能太差。
如果太小，比如设一个6，则，树化，和反树化太频繁，也不好。
3、为什么不支持全部用红黑树？
答: 红黑树的插入操作，需要对比hash值，并没有链表高。
4、为什么不使用平衡二叉树呢？
答：平衡二叉树虽然查找比红黑树块，但是，插入维护这个平衡比红黑树慢。
网友评论