如何存储数据 （put、get）
put数据
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key);
//根据hash和数组的长度计算索引，即数组存放的位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table; e != null; e = e.next) {
Object k;
//如果值存在，则新值替换老值，并返回老值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//将算出的key的hash值，key，value ，以及索引存放在entry对象中，并加入table数组中
addEntry(hash, key, value, i);
return null;
}get数据
public V get(Object key) {
//如果key为null，则返回null对于的value
if (key == null)
return getForNullKey();
//根据key获取entry
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//计算出key的hash值
int hash = (key == null) ? 0 : hash(key);
//根据hash值获取索引，遍历索引下的所有的entry值
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//如果hash值相同并且key也相同则返回value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}默认容量为什么是16
//1前移4位 二进制1是 01 ，前移4位 则是 10000，即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
我们先看一下源码如何获取index的值
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
//hash 值与 数组的长度-1进行位运算，长度必须是2的幂。
return h & (length-1);
}index的值是通过key的hash值与数组长度-1进行位运算来的。举个例子，
计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001；
HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111
把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9
可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。
==长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。==
负载因子为什么是0.75f
加载因子需要在时间和空间成本上寻求一种折衷。
加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本
加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。
hash冲突的产生与解决
产生
例如我们现在要加入一个key=A，value=a，先需要计算A的index，假如是2。那么结果如下：
图1
再加入一个key=A', value=a',此时刚好计算A'的index也是2，这时候就会产生冲突。
解决hash冲突
这个时候我们需要使用链表来解决hash冲突，当产生相同的index是，则通过Next指向同一个index的下一个节点，如图：
(
图二
)
注意：新来的Entry节点插入链表时，使用的是“头插法”。至于为什么不插入链表尾部，因为HashMap的作者发现后插入的Entry被查找的可能性更大
什么时候会出现死锁
当扩容时，需要将老的table的数据转移到新的table上，调用transfer发放进行转移。
我们先看下transfer方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//循环遍历老的table
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
//判断是否需要重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable;
newTable = e;
e = next;
}
}
}正常情况下，转移前链表顺序是1->2->3，逆序转移后新的t顺序变成 3->2->1，但是在多线程环境中，使用HashMap进行put操作时会引起死循环，导致死循环的原因是在多线程的情况下，会形成环形链表，这时是没有问题的，我们再看看get()方法中的获取Entry的方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}加入我们执行get方法找一个不存在的值的时候，for循环将会死循环，即会形成死锁