Java进步（一）----HashMap
参阅博客
1，java提高篇（二三）-----HashMap
这一篇由chenssy发表于2014年1月，是根据JDK1.6的源码讲的。
2，Java类集框架之HashMap(JDK1.8)源码剖析
这一篇由push_pop发表于2015年5月，根据JDK1.8讲的。
HashMap在jdk1.2加入，没有考虑多线程同步，单线程性能上优于HashTable
Note：就算是同一个类HashMap，在不同的jdk版本中，会有差别，有的甚至非常大。所以在贴源码时，应该要附上对应的jdk版本。
先说1.6的HashMap
1.6的HashMap代码较少，写的比较容易看懂。
HashMap里存的对象是Entry，HashMap实际上是Entry数组。数组的大小是2的n次方，默认为16，对应属性是capacity。
HashMap有4个构造函数，但其实最终调用的都是HashMap(int initialCapacity,float loadFactor)这个。可以看到，构造HashMap需要两个参数 容量initialCapacity和负载因子loadFactor。
initialCapacity这个参数并不是说 HashMap能装多少组元素，而是HashMap里有多少个桶，也就是Entry数组的大小。它并不会总等于你设定的值，而是会取一个比initialCapacity大的2的n次方。
比如你设置initialCapacity=9，实际上桶的大小会是16。桶大小不是一成不变的，会根据HashMap中总元素的增加而扩容。扩容会增加一倍，比如现在capacity是16，下一次调整就到32，再增加就是64。
HashMap在构造时，会设置扩容的阈值shreshold=initialCapacity*loadFactor。
下面是常用的put方法。1.6源码
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; 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++;
addEntry(hash, key, value, i);
return null;
}
首先根据key是否为null，会走不同的分支，key==null的，会单独走一个方法putForNullKey(). null这个key会固定放到table[0]
hash值，等于key.hashCode再进入hash函数算出来的值，这个hash()函数做了几次移位和取或运算。
indexFor() 等于用hash值对table的长度取模，来得到将来放到数组的哪个位置。这里用按位与，速度比%要快多。
put方法是有返回值的。
put时会有三种情况
情况1，i位置上没有元素，那么for循环不会进去，直接新建一个Entry节点，放在i位置上，返回null。
情况2，i位置上已经有元素了，而且是一列元素，链表存储方式，但是遍历后并没有相同的key，那么，就新建一个Entry节点，放在i的位置，之前这里的链表挂在新建的节点后面，或者说，新建的节点指向以前挂在这里的链表，返回null
这里有2点注意，
1，新建的节点，是挂在原来列表的头上，而不是末尾。这样就省得遍历到末尾了。
2，如何判断key相同呢？
e.hash == hash && ((k = e.key) == key || key.equals(k))
key的hash值相等，且key的equals方法相等，或者根本就是一个key（引用相同），这也是为什么一个对象要做Key必须要重载hashCode()和equals()方法的原因吧。
情况3，其实前面两种情况都是一个新key加入，只不过1是没有发生hash碰撞，2是发生碰撞了。 情况3是对一个已经存在key，再次put新值会怎么样。首先新值覆盖旧值，然后返回旧值。
所以通过put返回值，可以判断put的是一个新key，还是旧key。
get方法
1.6源码
public V get(Object key) {
//如果key==null会单独走一个方法。
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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.equals(k)))
return e.value;
}
return null;
}
如果key==null会单独走一个方法。
其他的 先算出hash值，找到对应的桶，遍历。
如果有相同的key就返回对应的value ，否则返回null。
size属性，记录HashMap中有多少元素（Entry）。每次添加Entry时，size都会自增1，同时会和阈值shreshold比较，当size>=shreshold时，就是调用resize方法 扩容
jdk1.6中增加节点的方法
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
jdk1.6 resize方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//再通过transfer方法把之前的元素都重新hash到新的数组中，
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
每次容量扩成之前的2倍
先new一个新数组，
再通过transfer方法把之前的元素都重新hash到新的数组中，
阈值按照新的容量重新计算。
remove()
还有删除的方法，删除也有返回值，如果返回null，说明要删除的key不存在，如果不是null，就是删除元素的value。
总结
1.6的HashMap采用的是数组+链表的形式，哈希值取模后就是数组的索引，所以在不冲突时，时间复杂度为1，当冲突时，多个节点一个接一个形成一个链结构，后来者插入到链表头。
======jdk版本分割线===========================
上面是jdk1.6的HashMap源代码
下面聊聊jdk1.8的HashMap，这个版本的HashMap变化还是比较大的，整个源文件大小从1000行增加到了2300行（包含所有注释空行）。
第一个改变是把以前的Entry类 改名字 成了Node。（jdk1.8中许多内部类都从Entry改名成了Node）
Entry和Node都实现了Map.Entry接口。 这个接口有4个static的方法，不需要实现。
Note：在Java8中，接口中支持了静态方法，这个静态方法需要有body，类在实现接口的方法时，不需要实现静态方法。
1.8对HashMap的另一个改变是将原来的链表结构，当长度超过8时，转化为红黑树结构。
所以1.8的HashMap是数组+链表+红黑树
HashMap还是有4个构造函数，最主要的是HashMap(int,float) , 1.8中，不会在构造时就new table数组，而是会延迟到第一次put数据时。构造函数只设定了loadFactor和threshold参数，threshold的计算方法和之前不同，它调用了一个tableSizeFor的方法，这个方法返回大于initialCapacity的2的n次幂
jdk1.8 tableSizeFor
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
hash值，依然是对 key的hashCode进行再hash， 不过hash函数和1.6的又有不同。
put方法
1.8的put实际上是调用putVal方法，这个方法多了一个onlyIfAbsent参数，貌似考虑在将来在put的时候，如果该key已经存在，就不覆盖了。目前这个参数还是false，每次put时如果key存在，会用新值替换旧值。
1.8源码，put 和 putVal
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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); //情况1
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //情况2
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //情况3
else { //情况4
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;
}
}
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;
}
1.8的代码比1.6的看起来写的更紧凑，不容易看懂，一些变量赋值，方法调用和比较都在一个语句中写着。可能是为了执行效率吧，阅读起来体验下降。
新版的resize方法是一个自适应的方法，不需要参数，这个resize比以前复杂，有初始化table的任务。
没有对key=null走特殊函数处理。put有几种情况
情况1，如果table在该位上没有节点，new一个新节点挂上即可，返回null。
情况2，table[i]为上有节点，且第一个节点的key就是本次要put的key，那么用新值覆盖旧值，返回旧值。
再往后判断就是要遍历这个位置上的挂接节点了。1.8的这些节点有两种组织方式 ，对于不足8个的，还是链表的结构。对于8个以上的，会转化成红黑树的结构来存储。
情况3，后面节点是树的结构。那么就调用TreeNode的put方法，存在key，就替换，返回旧值，不存在就新建节点，返回null。
情况4，后面节点是链表的结构。遍历这些节点，存在相同的key，那么新值覆盖旧值，返回旧值。如果遍历完，没有存在key，就新建节点，这个节点是挂在链表尾，返回null。还记得1.6是挂在链表头。
然后，如果链表长度大于阈值8，那么需要将这个链表结构，转化成树的结构。
1.8的HashMap新增一个内部类TreeNode,是继承LinkHashMap.Entry而来。当一个桶内的元素数量大于阈值（TREEIFY_THRESHOLD=8），会转化为树形，小于阈值（
UNTREEIFY_THRESHOLD=6）又会转换成链表结构。 这对于大量hash碰撞的情况，查找有优化，对于hash碰撞较小时，则不会用到TreeNode结构。
get()方法
1.8源码
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
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);
}
}
return null;
}
get方法，如果找到了key，则返回value，否则，返回null。
会根据节点结构是红黑树，还是链表用不用的方式去遍历。
Note: put的函数名是putVal，而get的函数名是getNode，这里不统一，有点奇怪。
remove()
删除方法，如果找到了key，返回删除的value，否则返回null。
根据node的结构，选择在树中遍历，还是以链表的方式遍历。
1.8中增加的代码主要都是因为引入了红黑树而引起的。导致许多地方都要考虑两种情况。
HashMap碰撞有没有那么频繁呢？如果碰撞真的这么厉害，这也算是一种优化吧。
