前言

jdk1.8中的hashmap有了诸多修改。包括扩容方式，链表结构等等。

成员变量

	static final int DEFAULT_INITIAL_CAPACITY = 16;static final int MAXIMUM_CAPACITY = 1073741824;static final float DEFAULT_LOAD_FACTOR = 0.75F;//如果单链表长度超过这个值，将单链表转换为红黑树static final int TREEIFY_THRESHOLD = 8;//如果红黑数节点被删，阈值小于该值，将退回到单链表static final int UNTREEIFY_THRESHOLD = 6;//单链表转换为红黑树的首要条件，table的长度 > 64static final int MIN_TREEIFY_CAPACITY = 64;transient Node table[];transient Set entrySet;transient int size;transient int modCount;int threshold;final float loadFactor;

成员内部类

final class EntryIterator extends HashIterator implements Iterator

final class EntrySet extends AbstractSet

static final class EntrySpliterator extends HashMapSpliteratorimplements Spliterator

abstract class HashIterator

static class HashMapSpliterator

final class KeyIterator extends HashIterator implements Iterator

final class KeySet extends AbstractSet

static final class KeySpliterator extends HashMapSpliteratorimplements Spliterator

static class Node implements Map.Entry

static final class TreeNode extends LinkedHashMap.Entry

final class ValueIterator extends HashIterator implements Iterator

static final class ValueSpliterator extends HashMapSpliteratorimplements Spliterator

final class Values extends AbstractCollection

重要的方法

hash

可以看出jdk1.8的hash方法的实现方式和1.7不一样

static final int hash(Object obj)
{int i;return obj != null ? (i = obj.hashCode()) ^ i >>> 16 : 0;
}

tableSizeFor

保持数组长度是2的n次幂

static final int tableSizeFor(int i){int j = i - 1;j |= j >>> 1;j |= j >>> 2;j |= j >>> 4;j |= j >>> 8;j |= j >>> 16;return j >= 0 ? j < 1073741824 ? j + 1 : 1073741824 : 1;}

get

public Object get(Object obj){Node node;return (node = getNode(hash(obj), obj)) != null ? node.value : null;}final Node getNode(int i, Object obj){Node anode[];Node node;int j;if((anode = table) != null && (j = anode.length) > 0 && (node = anode[j - 1 & i]) != null){Object obj1;if(node.hash == i && ((obj1 = node.key) == obj || obj != null && obj.equals(obj1)))return node;Node node1;if((node1 = node.next) != null){// 判断该节点位于  链表还是红黑树if(node instanceof TreeNode)return ((TreeNode)node).getTreeNode(i, obj);Object obj2;doif(node1.hash == i && ((obj2 = node1.key) == obj || obj != null && obj.equals(obj2)))return node1;while((node1 = node1.next) != null);}}return null;}

put

public Object put(Object obj, Object obj1){return putVal(hash(obj), obj, obj1, false, true);}final Object putVal(int i, Object obj, Object obj1, boolean flag, boolean flag1){Node anode[];int j;if((anode = table) == null || (j = anode.length) == 0)j = (anode = resize()).length;Object obj2;int k;if((obj2 = anode[k = j - 1 & i]) == null)//1.如果数组该索引位置没有任何节点，直接放在这里作为头部{anode[k] = newNode(i, obj, obj1, null);} else{Object obj3;Object obj4;//2.如果原来数组中索引位置的头部就是该节点，直接覆盖原来节点的valueif(((Node) (obj2)).hash == i && ((obj4 = ((Node) (obj2)).key) == obj || obj != null && obj.equals(obj4)))obj3 = obj2;else//3.数组该索引位置头部节点，是位于单向链表还是红黑树if(obj2 instanceof TreeNode){//3.1红黑树的情况obj3 = ((TreeNode)obj2).putTreeVal(this, anode, i, obj, obj1);} else{//3.2单向链表的情况int l = 0;do{// 如果以前数组中没有该节点，新建节点if((obj3 = ((Node) (obj2)).next) == null){obj2.next = newNode(i, obj, obj1, null);//加入新节点之后的链表长度如果超过8，将链表转换为红黑树if(l >= 7)treeifyBin(anode, i);break;}// 如果以前数组中就存在该节点，退出Object obj5;if(((Node) (obj3)).hash == i && ((obj5 = ((Node) (obj3)).key) == obj || obj != null && obj.equals(obj5)))break;//继续向下循环obj2 = obj3;l++;} while(true);}if(obj3 != null){Object obj6 = ((Node) (obj3)).value;if(!flag || obj6 == null)obj3.value = obj1;afterNodeAccess(((Node) (obj3)));return obj6;}}modCount++;//if(++size > threshold)resize();afterNodeInsertion(flag1);return null;}final void treeifyBin(Node anode[], int i){int j;int k;Node node;//如果原来的数组是空或者length < 64 优先扩容数组，不转换红黑树if(anode == null || (j = anode.length) < 64)resize();elseif((node = anode[k = j - 1 & i]) != null){TreeNode treenode = null;TreeNode treenode1 = null;do{TreeNode treenode2 = replacementTreeNode(node, null);if(treenode1 == null){treenode = treenode2;} else{treenode2.prev = treenode1;treenode1.next = treenode2;}treenode1 = treenode2;} while((node = node.next) != null);if((anode[k] = treenode) != null)treenode.treeify(anode);}}

resize

可以看出，rehash后得到的新数组，链表节点顺序相比较原来的数组，没有变化
这和1.7完全不同

final Node<K,V>[] resize() {// 原来的数组，数组长度，阈值Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;// 新的数组长度和阈值int newCap, newThr = 0;if (oldCap > 0) {// 超过最大容量  直接返回原来的数组if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//新的数组长度扩大两倍// 如果新的长度没有超过最大容量，且旧的长度超过默认值16//新的阈值也扩大两倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; //两倍旧的数据容量阀值}// 旧的table为空，新的长度=原来的阈值else if (oldThr > 0) newCap = oldThr; else {//第一次初始化table，则用默认容量值，和阀值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//阀值==0，计算容量*负载因子if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;//创建table数组，用新的容量值@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//1.将原来的数据从旧的数组迁移到新的数组中去if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {//旧值赋空oldTab[j] = null;//1.1.next节点为空，存放到新的table数组if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//1.2树节点，拆分到新的table数组上else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else {//1.3rehashNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;//1.3.1将该单链中的元素根据条件，拆分为两条单链do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//1.3.2将拆分后的两条单链放入新的数组if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}