HashMap在JDK1.7和1.8中有了很大的改变，空闲时间对HashMap做了一点点的研究。
HashMap是一种数组和链表结合的数据结构，我们每次new一个HashMap时，都会构造出一个长度为16的Entry数组，每一个Entry都是一个单向链表，
网上找的一张图，具体的hashMap的结构如下
Entry的数据结构如图所示
static class Entry<K, V> implements java.util.Map.Entry<K, V> {
final K key;
V value;
HashMap.Entry<K, V> next;
int hash; Entry(int arg0, K arg1, V arg2, HashMap.Entry<K, V> arg3) {
this.value = arg2;
this.next = arg3;
this.key = arg1;
this.hash = arg0;
}
首先先解读JDK1.7的Put方法
public V put(K key, V value) {
if (this.table == EMPTY_TABLE) {
this.inflateTable(this.threshold);
} if (key == null) {
return this.putForNullKey(value);
} else {
int hashParam = this.hash(key);
int index = indexFor(hashParam, this.table.length); for (HashMap.Entry entry = this.table[index]; entry != null; entry = entry.next) {
if (entry.hash == hashParam) {
Object object = entry.key;
if (entry.key == key || key.equals(object)) {
Object arg6 = entry.value;
entry.value = value;
entry.recordAccess(this);
return arg6;
}
}
} ++this.modCount;
this.addEntry(hashParam, key, value, index);
return null;
}
}
2-4行:如果table还未初始化，则先进行初始化
6-7行：如果key的值为空，则把把value值放到第一个位置，具体的代码如下
private V putForNullKey(V value) {
for (HashMap.Entry entry = this.table[0]; entry != null; entry = entry.next) {
if (entry.key == null) {
Object object = entry.value;
entry.value = value;
entry.recordAccess(this);
return object;
}
}
9行：根据重新计算的HashCode，对Entry数组的大小取模得到一个Entry数组的位置。注意HashMap构造函数中，如果你指定HashMap初始数组的大小initialCapacity，如果initialCapacity不是2的N次幂，HashMap会算出大于initialCapacity的最小2的N次幂的值，作为Entry数组的初始化大小
10行：根据上一步的hashcode值，以及数组的长度，确定出该key所处的下标值
12-19行：首先会判断这个数组里面所有的元素是的hash是否一样，如果hash一样，那么再去判断key值是否一样，如果key值也一样，则会覆盖原先key的value
24-26：如果都不一样，则会在当前的数组中，插入一个链表
移除元素
public V remove(Object oldKey) {
HashMap.Entry entry = this.removeEntryForKey(oldKey);
return entry == null ? null : entry.value;
} final HashMap.Entry<K, V> removeEntryForKey(Object oldKey) {
if (this.size == 0) {
return null;
} else {
int hashCode = oldKey == null ? 0 : this.hash(oldKey);
int index = indexFor(hashCode, this.table.length);
HashMap.Entry entry1 = this.table[index]; HashMap.Entry entry2;
HashMap.Entry entry3;
for (entry2 = entry1; entry2 != null; entry2 = entry3) {
entry3 = entry2.next;
if (entry2.hash == hashCode) {
Object arg6 = entry2.key;
if (entry2.key == oldKey || oldKey != null && oldKey.equals(arg6)) {
++this.modCount;
--this.size;
if (entry1 == entry2) {
this.table[index] = entry3;
} else {
entry1.next = entry3;
} entry2.recordRemoval(this);
return entry2;
}
} entry1 = entry2;
} return entry2;
}
}
移除元素的操作也很简单
7-8行判断元素是否为空,为空直接返回NULL
10-12行 的操作和put一样,获得key的hash值，然后根据hash值和table数组的大小取模，获得值便是key所处于这个数组的下标,当我们确定是哪个entry时，我们就可以进入到entry链表内部
16-27行 链表从头开始向后寻找，直到找到hashcode的值和key的值都一样的，把上一个链表的next指向下一个链表，这样就把当前的节点给剔除了
JDK8
//final修饰 方法内联
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为空，调用resize初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据hash获取下标i，如果tab[i]的node为空，调用newNode新建一个node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果tab[i]的node为不为空，即存在node链表
Node<K,V> e; K k;
//先判断第一个Node的key是否相同，是的话结束判断得到e,
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//调用btree的putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果以上条件都不满足，那就开始遍历链表
for (int binCount = 0; ; ++binCount) {
//多线程情况下，这里的判断会导致数据丢失
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//map的putval可以看成getAndSet
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
