HashMap 是基于哈希表的Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null 值和null 键(允许一个null键，HashTable不允许entry的键或者值为空)。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
JDK1.8 之前 HashMap 的数据结构是 数组+链表 。数组是 HashMap 的主体，单向链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）时，且tab.length>=64时，将链表转化为红黑树，以减少搜索时间。
注意，HashMap的底层数据结构中链表是单向链表，也就是只有next指针，没有prev指针。而LinkedHashMap维护了before、 after、head以及tail。
【1】底层数据结构分析
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash值 判断当前元素存放的位置（这里的 n 指的是数组的长度）。
如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖；不相同就通过拉链法解决冲突。
① hash(Object key)–扰动函数
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法造成的碰撞，换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。
static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^ ：按位异或--相同为0 不同为1 // >>>:无符号右移，符号位随着移动，空位都以0补齐 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //保留h的高16位，低16位变为原高16位与低16位异或结果 }
先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。
实质上是把一个数的低16位与他的高16位做异或运算，因为在 (n - 1) & hash 的计算中，hash变量只有末x位会参与到运算。使高16位也参与到hash的运算能减少冲突。
对比一下 JDK1.7(jdk1.7.0_17)的 HashMap 的 hash 方法源码。
final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。
实质上是把一个数的低16位与他的高16位做异或运算，因为在 (n - 1) & hash 的计算中，hash变量只有末x位会参与到运算。使高16位也参与到hash的运算能减少冲突。
对比一下 JDK1.7(jdk1.7.0_17)的 HashMap 的 hash 方法源码。
final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
hash(int h)方法根据key 的hashCode 重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash 冲突。
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。我们可以看到在HashMap 中要找到某个元素，需要根据key 的hash 值来求得对应数组中的位置。如何计算这个位置就是hash 算法。
② jdk1.7的拉链法
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
jdk1.7 HashMap数据结构：
从上图中可以看出，HashMap 底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap 的时候，就会初始化一个数组。
③ jdk1.8及以后
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度>=阈值（TREEIFY_THRESHOLD 默认为8）且tab.length>=64时，将链表转化为红黑树，以减少搜索时间。
【2】类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 序列号 private static final long serialVersionUID = 362498820763181265L; // 默认的初始容量是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 2^30 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的负载因子0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当桶(bucket)上的结点数大于等于这个值时会转成红黑树 static final int TREEIFY_THRESHOLD = 8; // 当桶(bucket)上的结点数小于这个值时树转链表 static final int UNTREEIFY_THRESHOLD = 6; // 桶中结构转化为红黑树对应的数组 table的最小length //即，如果根据TREEIFY_THRESHOLD 判断需要转成红黑树时，还要判断当前容量是否大于MIN_TREEIFY_CAPACITY //如果小于MIN_TREEIFY_CAPACITY ，则resize；否则转成红黑树 static final int MIN_TREEIFY_CAPACITY = 64; // 存储元素的数组，总是2的幂次倍 transient Node<k,v>[] table; // 存放具体元素的集 transient Set<map.entry<k,v>> entrySet; // 存放元素的个数，注意这个不等于数组的长度(table.length) //HashMap中所有键值对的个数 transient int size; // 每次扩容和更改map结构的计数器--快速失败机制有关 transient int modCount; //The next size value at which to resize (capacity * load factor). // 临界值， 当实际大小超过临界值(容量*填充因子)时，会进行扩容 //默认为16*0.75=12 int threshold; // 填充因子-负载因子 final float loadFactor; }
① loadFactor负载因子
负载因子loadFactor 定义为：hashmap.size() / tab.length。
CAPACITY也就是tab.length，默认是16。
threshold默认是CAPACITY*loadFactor =16*0.75=12。
扩容的前提是++size > threshold，size是HashMap中存放键值对的个数。
每一次put一个新的key，都会导致size+1
如下图所示，散列表的容量是64(数组没有画全)，size是14。这是一种比较极端的情况，数组还有很多空的位置，但是出现了红黑树。
当负载因子设置比较大的时候，扩容的门槛就被提高了，扩容发生的频率比较低，占用的空间会比较小，但此时发生 Hash 冲突的几率就会提升，因此需要更复杂的数据结构来存储元素，这样对元素的操作时间就会增加，运行效率也会因此降低；
而当负载因子值比较小的时候，扩容的门槛会比较低，因此会占用更多的空间，此时元素的存储就比较稀疏，发生哈希冲突的可能性就比较小，因此操作性能会比较高。
loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
② threshold
HashMap 的实现中，通过threshold 字段来确定是否需要扩容。
threshold = (int)(capacity * loadFactor);
结合负载因子的定义公式可知，threshold 就是在此loadFactor 和capacity 对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。
默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是旧容量的两倍。
给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当size(数量)达到了threshold-临界值- 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容。
③ HashMap 容量为什么总是为 2 的次幂
如果 n 永远是2的次幂，那么 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）
当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1
例如 00001111 & 10000011 = 00000011
这样做有如下好处：
- &运算速度快，至少比%取模运算块
- 能保证 索引值 肯定在 capacity 中，不会超出数组长度
- (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n
【3】为什么说(n-1)&hash 是速度上的优化？
初始化时HashMap 的容量总是2 的n 次方，即底层数组的长度总是为2的n 次方。当length 总是 2 的n 次方时，(n - 1) & hash运算等价于hash对length 取模，也就是hash%n，但是&比%具有更高的效率。
这看上去很简单，其实比较有玄机的，我们举个例子来说明。
假设数组长度分别为15 和16，优化后的hash 码分别为8 和9，那么&运算后的结果如下：
从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞。8 和9 会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8 或者9，这样就降低了查询的效率。
同时，我们也可以发现，当数组长度为15 的时候，hash 值会与15-1（1110）进行“与”，那么 最后一位永远是0。而0001(第二个位置)，0011(第四个位置)，0101(第六个位置)，0111(第8个位置)，1001(第10个位置)，1011(第12个位置)，1101(第14个位置) 这几个位置永远都不能存放元素了，空间浪费相当大。更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
而当数组长度为16 时，即为2 的n 次方时，2^n-1 得到的二进制数的每个位上的值都为1.这使得在低位上&时，得到的和原hash 的低位相同。则不存在空间浪费的情况，数组的所有位置都可以被索引到。
//jdk1.8 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
所以说，当数组长度为2 的n 次幂的时候，不同的key 算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小。相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
总结来讲就是：
采用&运算比%取模运算效率高
当数组长度为2的n次幂时，(n-1)&hash == hash%n
【4】链表与树的转化
① treeifyBin
在put方法过程中，如果链表结点个数大于等于TREEIFY_THRESHOLD=8且tab.length>=64(MIN_TREEIFY_CAPACITY)，那么就会触发链表转化为红黑树。
treeifyBin方法如下所示(不是一定转化为树哦，可能触发扩容)
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //index = (n - 1) & hash 即索引位置 //判断是否需要扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //do...将每一个结点转换为TreeNode并维护了两个结点之间的双向指向 do { // 将 e 转化为一个TreeNode TreeNode<K,V> p = replacementTreeNode(e, null); // 拿到头结点 if (tl == null) hd = p; else { // 将p与tl 组成双向链表 p.prev = tl; tl.next = p; } // 临时存放当前结点 tl = p; } while ((e = e.next) != null); // 把头结点放到索引位置 if ((tab[index] = hd) != null) hd.treeify(tab); } } //返回一个新的TreeNode TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }
这里首先进行了判断，是扩容还是链表转换为红黑树。然后获取到索引位置的结点进行遍历，将每一个结点都转换为TreeNode并维护了结点间的prev和next指向关系。最后触发hd.treeify(tab);尝试进行树化(因为不一定哦，可能会触发扩容)。
② treeify将链表转换为红黑树
这个方法很纯粹，将给定结点位置的链表转化为红黑树。
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; //this表示触发当前方法的结点，即索引位置的结点 for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; // 第一次循环将x赋予root，根节点一定是黑色 if (root == null) { x.parent = null; x.red = false;//标注黑色 root = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; //对树结点进行遍历，根据dir 更新p的值 for (TreeNode<K,V> p = root;;) { int dir, ph; K pk = p.key; // 将当前结点X 与root结点进行对比，必须要有大小 if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); //p表示当前循环判断节点，最开始是root，依次与X进行对比 // xp指向P表示的结点，下面P结点将会重新指向left或者right TreeNode<K,V> xp = p; // 如果p.left or p.right 为null，表示找到了位置放置X if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; // 平衡插入，获取新的root root = balanceInsertion(root, x); break; } } } } // 将root结点移动到索引位置 (n-1)&hash moveRootToFront(tab, root); }
方法逻辑总结如下：
- ① 遍历链表的每个结点，第一次将当前结点作为root，然后获取next；
- ② 第二次及以后则遍历root，找到合适位置放置x,然后进行平衡插入获取新的root
- ③ 如果②中没有中断循环则重复① ② 操作
- ④ 将root结点移动到索引位置
(n-1)&hash
③ 平衡插入获取新的root结点
参数中的root为当前root结点，x 为新插入的结点 。xpp 为xp的parent，xppl 为xpp的left，xppr 为 xpp的right ，xp是x.parent。这个过程会涉及到红黑树的左旋和右旋。
// root为当前root结点，x 为新插入的结点 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { //插入结点颜色首先默认是红色 x.red = true; //无限循环，直到return for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { // 如果parent为null，说明是根节点，直接返回x,颜色为黑色 if ((xp = x.parent) == null) { //这一步很关键，根节点强制调整为黑色 x.red = false; return x; } //如果xp颜色为黑色，或者xpp为null，则无需处理，返回root else if (!xp.red || (xpp = xp.parent) == null) return root; //左侧分支 if (xp == (xppl = xpp.left)) { //如果xppr.red 也就是祖父结点的右孩子，即叔叔结点为红色 //这种情况需要调整xp、xppr的颜色 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false;//调整为黑色 xp.red = false;//调整为黑色 xpp.red = true;//暂时调整为红色 x = xpp;//X指向XPP，进行下一次循环处理 } //xppr也就是叔叔结点不存在或者为黑色 else { //如果X是右孩子 if (x == xp.right) { //左旋 root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; //右旋 root = rotateRight(root, xpp); } } } } //if (xp == (xppl = xpp.left)) 的else-右侧分支 else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }
④ 将树的根结点移动到索引位置
如下则将root结点移动到(n - 1) & root.hash位置。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { // 获取索引位置 int index = (n - 1) & root.hash; // 获取索引位置结点，如果first==root则无需处理 TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; if (root != first) { Node<K,V> rn; tab[index] = root;//索引位置放上root TreeNode<K,V> rp = root.prev;//记录root的前结点 if ((rn = root.next) != null) // 把root.next.prev-->root.prev ,将root从中间摘出来 ((TreeNode<K,V>)rn).prev = rp; if (rp != null) // 如果rp不为null，则rp.next=rn形成双向指定 rp.next = rn; if (first != null) // first与root形成双向指定 first.prev = root; root.next = first; //这个很重要，索引位置结点的prev一定是null root.prev = null; } assert checkInvariants(root); } }
⑤ 扩容时红黑树的分割
扩容时会涉及到oldTab中结点向newTab中转移的过程。链表可能会被分割为两个，红黑树也可能会被分割为两个。其中在红黑树的分割过程中可能会触发向链表的转换。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //index就是结点位置，bit 是oldCap final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { // b=tab[index] TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order //位置不变的头和尾结点 TreeNode<K,V> loHead = null, loTail = null; //位置改变的头和尾结点，tab[index+bit] TreeNode<K,V> hiHead = null, hiTail = null; // lc记录位置不变的结点个数，hc记录位置改变的结点个数 int lc = 0, hc = 0; //从当前结点开始，一路next遍历下去。这个循环过程只维护了结点间的next关系 //所以拆分后，还需要对两个“对象”进行树化和链表化处理 for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; // 等同于 e.hash&oldCap==0 ,位置不变 if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; //临时存最后一个结点 loTail = e; //位置不变的结点数量+1 ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } //对位置不变的“对象”的处理 if (loHead != null) { //如果结点数量小于等于6 则转换为链表 if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; // hiHead 为null说明没有位置改变的，且lc >UNTREEIFY_THRESHOLD //那么本身就是一棵树，无需多余处理 if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } //对位置[index+oldCap]的“对象”的处理 if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) // 进行链表化 tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; // loHead为null则说明整体迁移到新的位置，无需多余处理了 if (loHead != null) hiHead.treeify(tab); } } }
这里通过遍历每个结点，对结点进行(e.hash & bit) == 0判断来拆分为两个“对象”。然后对两个对象尝试进行树化和链表化的处理。这里特别注意的是，仅可以认为循环遍历过程中维护了两个“对象”中结点间的next关系，“对象”是链表还是红黑树需要后续判断、处理。
⑥ untreeify转换为链表
这个过程比较简单，获取到当前结点q然后使用q.next遍历下去，把遍历到的每个结点追加到 hd 后面就形成了单向链表。
final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { Node<K,V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next); }
【5】Fail-Fast 机制
我们知道java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast 策略。
这一策略在源码中的实现是通过modCount 域，modCount 顾名思义就是结构修改次数，对HashMap 结构的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。
在迭代过程中，判断modCount 跟expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了Map。
在HashMap 的API 中指出，由所有HashMap 类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
HashMap的并发问题
hashmap在插入新的阶段的时候，多个线程同时插入，会把除了最后的那个线程的其它线程插入的结点丢失。
对于修改的时候，多个线程修改，会只保留最后的一个线程的修改结果。
扩容的时候，会只保留最后一个线程的扩容后的那个数组。
【6】jdk1.8下hash方法详解
源码基于jdk1.8:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
从上面的代码可以看到key的hash值的计算方法。key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）
为什么要这么干呢？ 这个与HashMap中table下标的计算有关。
n = table.length; index = （n-1） & hash;
因为，table的长度都是2的幂，因此index仅与hash值的低n位有关（此n非table.leng，而是2的幂指数），hash值的高位都被与操作置为0了。
假设table.length=2^4=16和某散列值做“与”操作如下，结果就是截取了最低的四位值。
10100101 11000100 00100101 & 00000000 00000000 00001111 ---------------------------------- 00000000 00000000 00000101 //高位全部归零，只保留末四位
但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就无比烦人。
时候“扰动函数”的价值就体现出来了，看下面这图：
右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
