HashMap介绍：
HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。
创建HashMap，并放入一个键值对儿
HashMap map = new HashMap();
map.put("key","value");
当构建的HashMap调用put的时候，源码如下
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
追踪putVal方法如何处理的数据
//这里用的final修饰方法，在权限上选用的是default
//返回值 V 任意类型
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/**在这里可以看到，HashMap在放入键值对儿的时候，方法中定义
*了Node变量，来构建键值对儿，而后一堆的if-else判断，来处
*理数据，这里先来看下Node是什么样的
**/
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
....省略代码
return null;
}
看看putVal中的Node<K,V>的结构
注： 这个在jdk1.7 并不叫Node，而是叫Entry，1.7是单链表，但由于处理多个碰撞是，链表过长，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，所以在1.8中进行了优化，超过8个后就会专版为红黑树，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。
//注意这里类和属性的权限，default仅同包和一个类中可用
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
//指向下一个node桶
Node<K,V> next;
//构造方法
//输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...略过
}
接下来继续回到putVal方法中
这里需要注意的是内部一直在调用的 resize()方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//声明桶的数组
Node<K,V>[] tab;
//当前操作的节点位置
Node<K,V> p;
//当前数组的长度 n ,当前操作的节点位置 i
int n, i;
//判断当前的map是否是空，如果是空，则进行resize()方法扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//判断put进的节点位置是否是空，如果是空，则把数据封装成
//Node节点放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//在上一步判断后，要插入的数据的位置有数据，这个时候如何
//处理put进的新数据？进入else块儿
else {
//声明一个节点对象 e, 同时声明一个K对象，即与放入数据的
//key相同的对象，这里仅仅是声明
Node<K,V> e; K k;
//判断：如果当前这个hash桶的数据和准备put进的数据的hash
//相等，并且key的hash值也相等或者key不是空同时key与新put
//进的数据的key相等，新的数据覆盖老的数据，e=p;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断：如果本身操作的数据类型是TreeNode[jdk8新增]
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//判断：当前操作的tab(Node数组)已经存在部分数据的情况下
//抛开以上的情况，则执行下边的else块儿
else {
//遍历整个链子，找到合适放数据合适的位置
for (int binCount = 0; ; ++binCount) {
//当前操作的节点的后边是空的
if ((e = p.next) == null) {
//则在该位置放入新增的数据
p.next = newNode(hash, key, value, null);
//放入数据后检查当前放入的数据是否已经超过单条链
//表负载，如果超过，则调整数据结构
//方法 ：treeifyBin() 后面会进行解析
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//调整数据结构，把容器里的元素变成树结构
treeifyBin(tab, hash);
break;
}
//如果插入数据的hash值和当前的Node的hash相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//在上述判断都否定的情况下执行p=e,把新put的数据放到
//当前位置
p = e;
}
}
// 新值放入，如果新put进的数据key已经存在，则覆盖并返回旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent 标记是否更改现有的值，false更改，这里传入的
//是true
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//数据新增后，桶的长度增加，并判断增加后的size是否大于初始
//化的容量
++modCount;
if (++size > threshold)
//扩容
resize();
afterNodeInsertion(evict);
//否则返回空
return null;
}
注： afterNodeInsertion(evict) 、 afterNodeAccess(e) 返回值都是void ，方法体是空的，在HashMap中
代码如下：
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
resize()方法：
//扩容后返回一个新的Node<K,V>[]
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 数组长度
int oldThr = threshold;// 临界值
int newCap, newThr = 0;
//针对扩容，处理扩容后的数组长度大小
//一系列的操作为初始化newCap、newThr
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 原数组长度大于最大容量(1073741824) 则将threshold设为
//Integer.MAX_VALUE=2147483647
//接近MAXIMUM_CAPACITY的两倍
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新数组长度 是原来的2倍
// 临界值也扩大为原来2倍 [ oldThr << 1 等同于： oldThr *2 ]
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//
// 如果新的容量 ==0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// loadFactor 哈希加载因子 默认0.75,可在初始化时传
//入,16*0.75=12 可以放12个键值对
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;
// 如果原来的table有数据，则将数据复制到新的table中
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;
}
至此，结合开头map.put(K,V) 操作完成。
