hashmap源码前前后后看了好几次，也和同事分享过好几次，每次都有新的收获。
分享也是一种提高！
本文最初借鉴于http://www.cnblogs.com/hzmark/archive/2012/12/24/hashmap.html，其基于jdk1.6，自己分析jdk1.8后，发现有很大的不同，遂记录于此。
java最基本的数据结构有数组和链表。数组的特点是空间连续（大小固定）、寻址迅速，但是插入和删除时需要移动元素，所以查询快，增加删除慢。链表恰好相反，可动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找，所以增加删除快，查找慢。有没有一种结构综合了数组和链表的优点呢？当然有，那就是哈希表（虽说是综合优点，但实际上查找肯定没有数组快，插入删除没有链表快，一种折中的方式吧）。一般采用拉链法实现哈希表。
jdk1.6中hashmap采用的是位桶+链表的方式，即我们常说的散列链表的方式；jdk1.8中采用的是位桶+链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。
1、hashmap的定义
1.1 所属包：package
java.util;
1.2 导入包：
import java.io.ioexception;
import java.io.invalidobjectexception;
import java.io.serializable;
import java.lang.reflect.parameterizedtype;
import java.lang.reflect.type;
import java.util.function.biconsumer;
import java.util.function.bifunction;
import java.util.function.consumer;
import java.util.function.function;
1.3定义：
public class hashmap<k,v> extends abstractmap<k,v> implements map<k,v>, cloneable, serializable {}
2、hashmap的部分属性
private static final long serialversionuid =
362498820763181265l;
//the default initial capacity - must
be a power of two.
static final int default_initial_capacity =
1 << 4; //jdk1.6直接写16，这效率更快？？
// the maximum capacity,must be a power of two <= 1<<30.
static final int maximum_capacity =
1 << 30; // 2的30次方
static final float default_load_factor =
0.75f; //填充比，装载因子
/**（jdk1.8新加）
* the bin count threshold for using a tree rather than list for a
* bin.当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树.
* 2< value<=8 时to mesh with assumptions in tree
removal about conversion back to plain bins upon shrinkage.
*链表转为树，bincount>=treeify_threshold-1，-1
for 1st。
*/ //当某个桶中的键值对数量大于8个【9个起】，且桶数量大于等于64，则将底层实现从链表转为红黑树
// 如果桶中的键值对达到该阀值，则检测桶数量
static final int treeify_threshold=
8; //jdk1.8新加
/**
* the bin count threshold for untreeifying a (split) bin during a
* resize operation. should be less than treeify_threshold, and at
* most 6 to mesh with shrinkage detection under removal.
* 仅用于treenode的final void split(hashmap<k,v> map,
node<k,v>[] tab, int index, int bit)
{
if (lc <= untreeify_threshold)
//太小则转为链表
tab[index] = lohead.untreeify(map);
}
*/
static final int untreeify_threshold =
6; //jdk1.8新加
* the smallest table capacity for which bins may be treeified.
* (otherwise the table is resized if too many nodes in a bin.)
* should be at least 4 * treeify_threshold to avoid conflicts
* between resizing and treeification thresholds.
*链表转树时，if (tab == null || (n = tab.length) < min_treeify_capacity)
resize(); // 即不转为树了
*/ //当桶数量到达64个的时候，才可能将链表转为红黑树
static final int min_treeify_capacity =
64; //jdk1.8新加
/* ---------------- fields -------------- */
// jdk1.6 为 transient
entry[] table;
transient node<k,v>[] table;
//存储元素(位桶)的数组,length power of two
transient set<map.entry<k,v>> entryset;
transient int size;
// key-value对，实际容量
transient int modcount;
//结构改变次数，fast-fail机制
int threshold;
// 新的扩容resize临界值,当实际大小(容量*填充比)大于临界值时，会进行2倍扩容
final float loadfactor;
// 新增的红黑树，继承linkedhashmap.entry<k,v>
static final int hash(object key)
{ // 计算key的hash值hash(key)
int h;
return (key == null)
? 0 : (h = key.hashcode())
^ (h >>> 16);
}
n = tab.length
table的下标【bucket的index】：(n -
1) & hash
由上可知：
key是有可能是null的，并且会在0桶位位置。
hashcode的计算也进行了改进，取得key的hashcode后，高16位与低16位异或运算重新计算hash值。
首先由key值通过hash(key)获取hash值h，再通过 hash &（length-1）得到所在数组位置。一般对于哈希表的散列常用的方法有直接定址法，除留余数法等，既要便于计算，又能减少冲突。
在hashtable中就是通过除留余数法散列分布的，具体如下： int index
= (hash & 0x7fffffff) % tab.length;
但是取模中的除法运算效率很低，hashmap则通过hash &（length-1）替代取模，得到所在数组位置，这样效率会高很多。
3、hashmap的4种构造方法
putmapentries
tablesizefor：
//
经程序测试：结果为>=cap的最小2的自然数幂（64-》64；65-》128）
static final int tablesizefor(int cap)
{ //计算下次需要调整大小的扩容resize临界值
int n = cap -
1;
n |= n >>>
1; // >>>“类似于”除以2，高位补0；|=(有1为1)
2; // int--4byte--32bit，共32位
4;
8;
16; // 至此后每位均为1，00001111
return (n <
0) ? 1 : (n >= maximum_capacity)
? maximum_capacity : n +
}
证明：
n=96=0110 0000（暂已8位为例，事实上32位）
n>>>1使1位为0，若n首位为1，则结果为1，若为0，则忽略；确保首位有值时结果为1；至此首位完毕
0110 0000 |=0011 0000》0111 0000》112
n>>>2使新的n前2位为0，0111
0000|=0011 1100》0111 1100》124
1+2+4+8+16=31
01100000
1
00110000
=
01110000 确保1、2位为1，所以接下来移2位
2
00011100
01111100 确保3、4位为1（此时1-4位均为1），所以接下来移4位
4
00000111(1)
01111111 以此类推
计算新的扩容临界值，不再是jdk1.6的while循环来保证哈希表的容量一直是2的整数倍数，用移位操作取代了1.6的while循环移位（不断乘2）。hashmap的构造函数中，都直接或间接的调用了tablesizefor函数。
在1.6中，int capacity = 1; while (capacity < initialcapacity) capacity
<<= 1。
其返回值是>=cap的最小2的自然数幂。（大于等于1，tablesizefor(-111)=1）
性能优化：
length为2的整数幂保证了length
- 1 最后一位（二进制表示）为1，从而保证了索引位置index即（ hash &length-1）的最后一位同时有为0和为1的可能性，保证了散列的均匀性。反过来讲，若length为奇数，length-1最后一位为0，这样与h按位与【同1为1】的最后一位肯定为0，即索引位置肯定是偶数，这样数组的奇数位置全部没有放置元素，浪费了大量空间。
简而言之：length为2的幂保证了按位与最后一位的有效性，使哈希表散列更均匀。
来看一下上面调用的resize（）方法，这也是hashmap中一个非常重要的方法。
与1.6相比，将舍去transfer(entry[] newtable)，直接写到resize中并优化copy逻辑，并舍去static方法indexfor(hash, table.length)，将其直接写到resize中。
node<k,v>[] resize()
这里详细解释一下【resize】时【链表】的变化：
元素位置在【原位置】或【原位置+oldcap】
①、由前面的知识可知，table的下标【bucket的index】由(n -
1) & hash计算
（n为table的length,hash即hash(key)计算方式为(key == null)
? 0 : (h = key.hashcode())
^ (h >>> 16)）；
②、假设我们length从16resize到32（以下仅写出8位，实际32位）,hash(key)是不变的。
n-1： 0000 1111-----》0001 1111【高位全0，&不影响】
hash1: 0000 0101-----》0000 0101
index1： 0000 0101-----》0000 0101【index不变】
hash2: 0001 0101-----》0001 0101
index2： 0000 0101-----》0001 0101【新index=5+16即原index+oldcap】
③、新bucket下标：(2n -
1) & hash(key)，由于是&操作，同1为1；hash(key)不变；2n-1在原来n-1的基础上仅最高位0变1；
④、so，hashmap在resize时，只需看(新)n-1最高位对应的hash(key)位是0还是1即可，0则位置不变，1则位置变为原位置+oldcap。
⑤、如何确认(新)n-1最高位对应的hash(key)位是0还是1呢？源码给出了很巧妙的方式（e.hash & oldcap）：e即node，由put和node构造函数相关源码可知，e.hash即为hash(key)；oldcap为0001
0000（仅最高位为1）；
相&为0说明e.hash最高位为0，否则为1.
总结：
1、无需重新计算hash，节省了时间；
2、由于所计算的hash(key)位是1是0可以认为是随机的，所以将一个冲突长链表又“均分”成了两个链表，减少碰撞。
4、hashmap的方法实现
1）put相关
public v put(k key,
v value) {
return putval(hash(key), key, value, false, true);
检测指定的key对应的value是否为null，如果为null，则用新value代替原来的null。
@override
public v putifabsent(k key,
v value) {
return putval(hash(key), key, value, true, true);
核心方法：v putval(hash,key,value,onlyifabsent,evict)
put(k key, v value)的逻辑：
判断键值对数组tab[]是否为空或为null，是则resize()；
根据键值key的hashcode()计算hash值得到当前node的索引i，如果tab[i]==null【没碰撞】，直接新建节点添加，否则【碰撞】转入3
判断当前数组中处理hash冲突的方式为红黑树还是链表(check第一个节点类型即可),分别处理。【①是红黑树则按红黑树逻辑插入；②是链表，则遍历链表，看是否有key相同的节点；③有则更新value值，没有则新建节点，此时若链表数量大于阀值8【9个】，则调用treeifybin方法（此方法先判断table是否为null或tab.length小于64，是则执行resize操作，否则才将链表改为红黑树）。】
如果size+1> threshold则resize。
public void putall(map<? extends k,
? extends v> m) {
putmapentries(m, true); //
详见构造方法，仅putall参数为true
note：
putall可以合并map，如果key重复，则用新值替换就值（相见study代码）。
2）remove、clear
tip：
a、 hashmap貌似不存在类似于arraylist的trimtosize()压缩空间的方法。
b、hashmap map= new hashmap(); hashmap map=null;有什么区别?
都实例化了map；
前者创建对象、分配地址，将该地址的引用赋值给对象
后者只是创建对象，地址为空（null），并且在赋值对象之前，进行任何操作都将报nullpointerexception。
3）迭代方式、迭代时如何正确remove
hashmap有自己的迭代器，
① 定义 abstract class hashiterator {}；
其remove方式实现如下：
final void remove()
② 定义迭代器 entryiterator、keyiterator 、keyiterator
③ final class entryset extends abstractset<map.entry<k,v>>
{……entryiterator……}
keyset、values类似。
迭代 具体实现：
remove正确调用方式：
发散：
1、如果是遍历过程中增加或修改数据呢？
增加或修改数据只能通过map的put方法实现，在遍历过程中修改数据可以，但如果增加新key就会在下次循环时抛异常，因为在添加新key时modcount也会自增。
2、有些集合类也有同样的遍历问题，如arraylist，通过iterator方式可正确遍历完成remove操作，直接调用list的remove方法就会抛异常。
3、jdk为什么允许通过iterator进行remove操作？
hashmap和keyset的remove方法都可以通过传递key参数删除任意的元素，而iterator只能删除当前元素(current)【movable为false】，一旦删除的元素是iterator对象中next所正在引用的，如果没有通过modcount、 expectedmodcount的比较实现快速失败抛出异常，下次循环该元素将成为current指向，此时iterator就遍历了一个已移除的过期数据。concurrentmodificationexception是runtimeexception，不要在客户端捕获它。如果发生此异常，说明程序代码的编写有问题，应该仔细检查代码而不是在catch中忽略它。
iterator自身的remove()方法会自动同步expectedmodcount和modcount的值（见上源码）。确保遍历可靠的原则是只在一个线程中使用这个集合，或者在多线程中对遍历代码进行同步。
4）get、contains相关
get相关的核心方法：
v get(object key)：
1、(n - 1) & hash计算bucket的index；【hash=hash(key)如下】
1、判断第一个节点hash、key是否相等，是则返回first【always check first node】；
2、若(e = first.next)
!= null，
若first为红黑树，gettreenode返回根节点，并调用其find方法，根据hash值判断进入左(右)子树，逐层查找；
若为链表，遍历链表，得到节点值，通过hash和equals(key)确认所查找元素。
3、没有该元素，返回null。
get、containskey都可以用来判断map中是否存在该元素吗？
当get()方法的返回值为null时，可能有两种情况，一种是在集合中没有该键对象，另一种是该键对象没有值本就为null。因此，在map集合中不应该利用get()方法来判断是否存在某个元素，而应该利用containskey()方法来判断。
5）replace相关
6）其他函数
tostring()： 返回格式如{null=1, 2=8, 3=7, 9=8}或{
}。
int size()：return size。
boolean isempty()：return size == 0。
equals() ：继承于abstractmap、object等。
3个afternode……空方法，仅内部使用：
// callbacks to allow linkedhashmap post-actions
void afternodeaccess(node<k,v> p)
{ }
void afternodeinsertion(booleanevict)
void afternoderemoval(node<k,v> p)
小结：
1、多了1300行代码(共2380)，static final class treenode<k,v> extends linkedhashmap.entry<k,v>
。get性能o(n)-->o(lgn)
2、尽量直接调用系统函数
node<k,v>中调用object的hashcode和equals
3、减少不必要的内部函数调用
resize中的transfer(entry[] newtable)【逻辑优化】和indexfor(hash, table.length)
4、储存方式
位桶存储；若产生hash碰撞，位桶中按链表存储；若链表达到阀值，链表转换为红黑树。
5、赋值巧妙
if ((p = tab[i =
(n -
1) & hash])
== null)判断赋值两不误。
6、通过bool或instance实现代码复用
putmapentries(map<?
extends k, ? extends v> m, boolean evict)
put、get的红黑树部分有待再次阅读分析。
部分源码注释翻译：
基于map接口；
key、value允许空（仅允许一个key为null）；
和hashtable类似，除了非同步和允许null；
无序，顺序可能变；
get、put效率o(1)，迭代器与number of buckets、size相关（所以initial很重要）；如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）；
capacity：buckets的大小，table被create时便实实在在的存在；
number of entries达到load factor*capacity便rehashed，approximately（大约）2倍buchets；
load factor (.75)是个时间和空间的折衷，higher-->减少空间开销，增加查询开销（包括get、put）；
非同步，若结构改变（add、delete，不包括修改value），必须在外部同步；考虑synchronizedmap，map m = collections.synchronizedmap(new hashmap(...))；
迭代时remove报异常concurrentmodificationexception，不能写一个依赖他正确性的程序；
链表转红黑树后，若树变短，会恢复为链表。
有任何问题，欢迎指正探讨。
本文作者：云海（花名）
相关文章：
<a target="_blank" href="http://www.cnblogs.com/tobeaprogrammer/p/4787761.html"></a>
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)