上一篇文章介绍了HashMap的一部分的知识，算是为下面HashMap的进一步学习做准备吧。
然后写的时候一直在思考的一个问题是，这方面的知识网上的资料也是一抓一大把，即使是这样我为什么还要花费时间去写呢。后来我仔细想了一下，其实很简单，虽然大家解读的是同一份源码，但是如果只是看看别人写的文章，源码它真正的思想和魅力你都体会不到一半。所以还是决定自己写写，虽然和别人写的大同小异，但是写完真的能体会到更深层次的东西。再就是我的描述或许不准确甚至说是有错误。希望看到的人可以指出，这样对我也是一种帮助。
然后觉得有点扯远了，赶紧回到正题吧。
下面要说的就是HashMap的具体操作了。这里我主要说的是put方法和get方法，以及这两个方法中包含的其他方法。我讲到的地方算是我理解到的(有的可能不准确)。还有一些没有讲到，是因为个人能力有限，没有理解透彻，所以就不误导大家了。
首先我们先看put方法。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
调用put方法之后调用了hash(key)方法，我们先看一下这个hash()方法，这个hash方法就是定位一个hashmap的位置。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个过程的含义就是：
如果要put进table的Key值为null，返回0；如果Key值不为null，返回 key的hashCode值 和 key的hashCode无符号算术右移16位的值 按位异或的结果
算术右移的规则是给右移后高位补0
按位异或就是把两个数转化为按二进制，按位进行比较，每一位上的数相同就取0，不同就取1
按照算术右移的规则，正数在算术右移之后会变小；负数在算术右移后会变成正数
因此一个正数右移16位换句话说就是丢弃低16为位。那么对于任何小于2的16次方的数，右移16后结果都为0
例如：2的16次方为65536转化为二进制为：1 0000 0000 0000 0000，右移16为刚好为0
小于2的16次方的数，例如：2的10次方为1024转化为二进制位：10000000000，右移16为0
当一个数右移为0时，它和任何数 按位异或 结果都是这个数本身
所以这个hash()函数对于非null的key，仅在key的hashCode值大于等于2的16次方的时候才会重新调整其值。
其他时候hash函数返回值就是key的hashCode。
然后为什么设计成为这样呢？我们可以看到put方法里除了调用到了hash()方法外，调用到了putVal方法。putVal方法如下：
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);
......
}
在这里我们可以看到有这样的代码段
tab[i = (n - 1) & hash]
tab[i] = newNode(hash, key, value, null)
实际上就是先给 i 赋值为 (n - 1) & hash。n就是table的长度，假设默认为16,然后hash值的得出就是上面所讲的
然后给tab[i]装入一个新的Node。此处的关键就是i的取值
我们默认n为16，然后16-1=15，转化为二进制后为 1111
此时，假设hash的值不做 h = key.hashCode() ^ (h >>> 16) 这样的处理
而是直接调用 h = key.hashCode() 得到h，那么1111和h按位与或，i 结果就为0
那么传入的键值对放的位置就是tab[0]位置或者说是在挂tab[0]位置下面的链表的一个节点
这样的话大多数类似于 xxxx xxxx 0000这样的数 和 1111 按位与或结果都为0
那么tab[0]位置有可能会存储很多的值，即链表的长度会很长，这样查找时就会降低了性能。
现在我们看看hash值经过 h = key.hashCode() ^ (h >>> 16) 这样的处理后是怎样的结果
做一个简单的测试
public static void testHash(){
System.out.println(Integer.toBinaryString("aaaa".hashCode()) + "=>"+Integer.toBinaryString("aaaa".hashCode() ^ ("aaaa".hashCode() >>>16)));
System.out.println(Integer.toBinaryString("bbbb".hashCode()) + "=>"+Integer.toBinaryString("bbbb".hashCode() ^ ("bbbb".hashCode() >>>16)));
System.out.println(Integer.toBinaryString("aabb".hashCode()) + "=>"+Integer.toBinaryString("aabb".hashCode() ^ ("aabb".hashCode() >>>16)));
System.out.println(Integer.toBinaryString("cccc".hashCode()) + "=>"+Integer.toBinaryString("cccc".hashCode() ^ ("cccc".hashCode() >>>16)));
System.out.println(Integer.toBinaryString("dddd".hashCode()) + "=>"+Integer.toBinaryString("dddd".hashCode() ^ ("dddd".hashCode() >>>16)));
}
调用这个方法结果为下图
"=>"前面的是没经过 h = key.hashCode()) ^ (h >>> 16）处理之后得到的哈希码的二进制表示形式
"=>"后面的是经过了 h = key.hashCode()) ^ (h >>> 16）处理之后得到的哈希码的二进制表示形式
可以看到没经过处理直接拿到的值后面的四位都为0000，这样和 n-1 按位与或后结果都为0
这样把键值为aaaa,bbbb,cccc,dddd的对象放入Map中最终都放到了挂到了tab[0]的后面
而经过处理后拿到的值的二进制表示后面的四位都是不一样的，这样和 n-1 按位与或后结果就全为0，也就是在hashCode()的基础在做了散列
至于为什么要右移16位，看到大多数人的说法就是折中(因为容量定义为int类型，4个字节，32位,右移16算是折中做法)
接着我们继续说put方法，put方法的实现是通过调用putVal方法。
putVal完整的源码如下：
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为空或者table的长度为0，证明table尚未创建(第一次调用put时会发生这种情况)，此时创建table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
走到这一步说明table不为空。
判断下标为i的tab是否存在结点，没有则创建新节点
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
/*
走到这里说明tab[i]存在节点
就意味着发生了冲突，这时就要处理冲突
*/
Node<K,V> e; K k; /*
此时的 p = tab[i = (n - 1) & hash] ,是上一步if操作产生的结果
如果存在于tab中节点tab[i]与传入节点的key和value相等，则记录下当前存在于tab中的tab[i]节点
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/*
如果当前tab[i]节点类型为红黑树，则按照红黑树方法添加传入的元素
*/
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
/*
走到这一步说明当前首tab[i]结点类型为链表类型。
然后循环遍历链表
*/
for (int binCount = 0; ; ++binCount) {
// 如果遍历到末尾时，先在尾部追加该元素结点。
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//追加完成后，如果对应tab[i]下的节点大于8，则把tab[i]节点下的链表结构转化为红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
/*
判断所有遍历到的节点，如果key和value都和传入的key和value相等，则停止for循环遍历
此时该节点在上一个if操作中的e = p.next中已经记录了下来
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; //让p节点指向下一个节点.
p = e;
}
}
/*
如果e不为空，证明传入的key和value在哈希表中有相同元素的结点
则用传入的value替换e.value，并且返回e.value
*/ if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//一个没有任何实现的空方法
afterNodeAccess(e);
return oldValue;
}
}
/*
到此一个节点处理完毕，共做了三次判断
在总结一下：
①初次调用put方法，table为空，创建一个table,返回table的长度
②table不为空后，判断tab[i]是否存在节点，不存在创建节点并赋值给tab[i]；如果存在节点，走第三步
③解决冲突。分别三步。这里就不写了，可以回头看。
完成这三不步，一个节点处理完毕，tab发生一次修改，因此modCount++
*/
++modCount;
//如果存放元素的个数大于HashMap的阈值，则进行扩容
if (++size > threshold)
resize();
//一个没有任何实现的空实现
afterNodeInsertion(evict);
return null;
}
到此put方法结束。
但实际上还没有结束，因为put方法涉及到的扩容机制还没有讨论。
接着谈一下扩容机制的实现，也就是resize方法，
该方法可用来初始化HashMap大小，也可以重新调整HashMap大小变为原来2倍大小
完整的源码如下：
final Node<K,V>[] resize() {
/*
把table放到oldTab，table可能为空，可能不为空
为空就是对table进行初始化
不为空就是对table进行扩容
*/
Node<K,V>[] oldTab = table;
//如果旧的哈希表oldTable为空则旧的哈希表容量oldCap为0；不为空容量oldCap就为oldTab的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//给旧的填充因子oldThr赋值默认的填充因子0.75
/oldThr不会是0，因为有tableSizeFor()方法，threshold至少是1,这个在前面做过一个小测试。
int oldThr = threshold;
//定义将要初始化或者扩充的哈希表的容量和填充因子
int newCap, newThr = 0;
//满足这个if条件证明进行的是扩容操作
if (oldCap > 0) {
/*
如果将要进行扩容的tab的容量大于HashMap的最大的容量，表明不能在进行扩容了
此时进行的操作是把int能表示的最大值赋值给hashMap的阈值，然后返回之前本就存在的tab
*/
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/*
进入这里表明可以进行扩容
新的容量为之前容量的二倍。具体代码就是newCap = oldCap << 1
新的阈值为原来的二倍。 具体的代码 newThr = oldThr << 1
*/
newThr = oldThr << 1;
}
//oldCap=0 ,oldThr>0,tab为空，因此oldCap为0，而oldThr=threshold > 0
else if (oldThr > 0) //以 new HashMap(int initialCapacity) 方式或者 HashMap(int initialCapacity, float loadFactor) 创建的一个HashMap
//有初始容量，有阈值，有加载因子。但是依然是一个空的HashMap
//因此这样的两种创建方式调用put会到这个分支
//设置新的tab容量为之前的阈值
//然后在下面创建一个newCap大小的桶数组,即执行Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
newCap = oldThr;
else {
//以 new HashMap()方式创建一个HashMap，
//只有一个加载因子，HashMap为空，因此这种方式创建的HashMap对象在第一次调用put时会进入到这个分支
//oldCap=0,oldThr=0 ，进行table的初始化操作，即使用默认填充比和初始容量对table进行初始化
//设置新的hash的桶数组的长度newCap为默认值16
newCap = DEFAULT_INITIAL_CAPACITY;
//newThr = 0.75×16 = 12,当size值大于12时，进行扩容
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;
//这个新的HashMap newTab创建好之后，如果之前的HashMap不为空，就要把之前的oldTab导入到新的newTab,最后返回这个新的newTab
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
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;
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;
}
重要的put方法讲完了之后，接着说get方法。
get方法是根据键获取相应的值。
源码如下：
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;
//确保HashMap里维护的table不为空，且传入的键值转化为索引后，也就是定位到了table数组的下标，
//该下标对应的table节点不为空，进行后续操作；否则直接返回空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断找到的节点的hash和key是否和传入的hash和key相等，如果相等直接返回这个节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//走这一步说明该hash值在对应到了table数组，但是该位置所存储的节点的键值和传入的键值不等。
//说明hash值有冲突的，因此要向下遍历链表或者红黑树
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);
}
}
//如果从这一步返回说明没找到，返回null
return null;
}
到此我要讲的就完了
漏掉的部分有链表转红黑树，还有就是如何把之前的旧table导入到扩容之后的新table
其实主要难懂的操作就是红黑树，链表的操作大家应该很容易就看懂了
所以后面关于红黑树的知识还要再看看
如果看懂了我就会继续做出总结