综述

HashMap是一个存储键值对(Key-value)的集合，每一组键值对也叫做Entry，HashMap数组的初始化都是null。

1、成员变量

//初始化容量为16，这个必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//大于这个阈值会将链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
//小于这个阈值会将红黑树转化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//链表转红黑树时数组长度必须大于这个值，否则认为链表长度太长是因为数组长度不够导致哈希冲突太多
static final int MIN_TREEIFY_CAPACITY = 64;

2、HashMap设计相关原理

①、初始化容量为2的幂以及每次扩容后长度必须为2的幂的原因
HashMap中的hash函数如下：

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

将得到的hash值的高16位与低16位进行异或运算作为低16位值高16位不变的新的hash值作为最终的hash值。
hash的目的在于构建一个分布均匀的hash函数，直接通过index = hashCode(key) % length 固然简单，但是此种情况冲突很多效率很低，因此HashMap中对获取index做了优化，在putVal()方法中有这么一句：

if ((p = tab[i = (n - 1) & hash]) == null)

也就是index = (length - 1) & hash，此时如果数组长度是2的幂，则length - 1的二进制位 ”全为1“，通过index = (length - 1) & hash得到的index只与得到的hash值对应的最后几位有关，比如下面的例子：
假设hash值为：101110001110101110 1001
数组长度为16，length - 1对应二进制为：1111
&运算之后，index为1001即为9，此时保证了只要的得到的hash值分布均匀，index就会分布的均匀，这种操作等价于取余运算。

②、如何保证hash函数取到的hash值分布均匀
HashMap中的hash函数获取到的hash值会数组长度length - 1进行&运算，结果只与hash值的后n位有关，此时hash值的前16位特征将会丢失，比较容易产生哈希冲突，采用将高16位与低16位进行异或运算后作为低16位的值既保证了高16位的特征也保留了低16位的特征，而且大大减少了冲突。

③、负载因子的作用以及为什么是0.75
负载因子的作用是为了解决HashMap的数据密度问题，当数组使用的长度大于了当前容量*负载因子时就会发生resize()操作，设置合适的负载因子可以提高空间利用率和减少查询时间成本。0.75是一个折中，如果设置为1，则空间利用率提高，但是查询成本加大；如果设置为0.5，查询成本虽然降低，但空间利用率变小，所以选择0.75完全是时间和空间上的一种折中。

HashMap中有这么一段注释：

Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution(泊松分布)
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

也就是在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素个数和概率的对照表。
从上面的表中可以看到当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。

④、HashMap是如何保证容量是比设置的大的最小的2的幂
比如初始化容量设置为20，则实际初始化长度为32，完成这一转换的是HashMap中的tableSizeFor函数，如下：

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;
}

对此算法进行简单理解：

• 首先cap-1是为了防止cap已经是2的幂，如果cap已经为2的幂且不进行cap - 1操作，则会返回cap的2倍；
• 如果cap为1，则n为0，最终结果返回1；
• 如果cap - 1 不为0，则n的二进制中一定存在1，考虑最高位的1；
• n |= n >>> 1;经过这步操作，n的最高位和右边相邻位均为1；
• n |= n >>> 2;同上一步一致，会有四个连续的1；
• n |= n >>> 4; 产生8个相邻的1；
• n |= n >>> 8; 产生16个相邻的1；
• n |= n >>> 16; 产生32个相邻的1
  最大也就是30个1，32个1是负数。

⑤、put()函数
put函数调用putVal()函数实现存键值对，putVal函数处理流程如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//如果尚未初始化，则先进行resize()函数初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//哈希到的位置是否为null，如果为null表示此位置尚未被使用可以直接插入if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//否则插入位置已存在值else {Node<K,V> e; K k;//如果key值相等，会进行更新value操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//如果是红黑树，则进行红黑树的插入，调用putTreeVal函数完成红黑树插入else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//遍历链表，找到key值相等的，则更新value，否则插入链表尾部，插入后在检查是否需要转化为红黑树，如果需要调用treeifyBin函数树形化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 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//更新valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//新插入之后检查是否需要扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

红黑树插入流程如下：

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {Class<?> kc = null;boolean searched = false;TreeNode<K,V> root = (parent != null) ? root() : this;//从红黑树的根节点便历对比hash值for (TreeNode<K,V> p = root;;) {int dir, ph; K pk;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;//如果哈希值和键值相等，则直接返回此节点，并在putVal中更新valueelse if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) {//如果当前节点和要添加的节点的key哈希值相等，但key不是同一个类，则按个对比左右孩子if (!searched) {TreeNode<K,V> q, ch;searched = true;if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null))//如果在子树中可以找到要添加的节点，则直接返回return q;}//哈希值相等但键值无法比较，调用此方法完成特殊处理给个结果dir = tieBreakOrder(k, pk);}//上述操作得到了当前节点和要插入节点的大小关系TreeNode<K,V> xp = p;//判断当前节点有没有左右孩子，没有左右孩子就直接插入，否则进入下一轮循环if ((p = (dir <= 0) ? p.left : p.right) == null) {Node<K,V> xpn = xp.next;TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);if (dir <= 0)xp.left = x;elsexp.right = x;xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;//插入之后红黑树的自平衡操作moveRootToFront(tab, balanceInsertion(root, x));return null;}}
}

树形化函数：

final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//如果数组长度小于64，则认为哈希冲突太多的原因是数组长度太短，会及进行resize()操作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<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);//上述操作将单链表转换成了双向链表，并将节点转换为了红黑树的节点，下面的treeify()函数才是建立红黑树的关键if ((tab[index] = hd) != null)hd.treeify(tab);}
}

treeify函数

final void treeify(Node<K,V>[] tab) {TreeNode<K,V> root = null;for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;x.left = x.right = null;//设置根节点if (root == null) {x.parent = null;x.red = false;root = x;}else {K k = x.key;int h = x.hash;Class<?> kc = null;//通过比较获取当前节点的插入位置for (TreeNode<K,V> p = root;;) {int dir, ph;K pk = p.key;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);TreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;//插入之后平衡红黑树root = balanceInsertion(root, x);break;}}}}moveRootToFront(tab, root);
}

⑥、resize()扩容函数
当数组使用量大于等于数组长度*负载因子时就会发生resize将数组长度扩充为原来的两倍，resize之后元素会被rehash，但不需要再次计算hash值，如下图例子，当为1时索引位置就变为 元索引+原来数组长度，位0则不变
2对应二进制位 0010，16 = 2^4，不需要改变索引位置；
10对应二进制位1010 ，为1，索引位置为2 + 8 = 10，同理26也是如此。
因为resize()操作开销很大，索引在创建HashMap的时候要设置合适的大小，比如要存入1000个数据，这是要设置容量为大于1000/.75f的2的幂，也就是2048。