参考：http://www.cnblogs.com/joemsu/p/7724623.html

数据结构

数组、链表/红黑树

参数

/默认初始化map的容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//map的最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的填充因子：0.75，能较好的平衡时间与空间的消耗
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//将链表(桶)转化成红黑树的临界值
static final int TREEIFY_THRESHOLD = 8;
//将红黑树转成链表(桶)的临界值
static final int UNTREEIFY_THRESHOLD = 6;
//转变成树的table的最小容量，小于该值则不会进行树化
static final int MIN_TREEIFY_CAPACITY = 64;
//上图所示的数组，长度总是2的幂次
transient Node<K,V>[] table;
//map中的键值对集合
transient Set<Map.Entry<K,V>> entrySet;
//map中键值对的数量
transient int size;
//用于统计map修改次数的计数器，用于fail-fast抛出ConcurrentModificationException
transient int modCount;
//大于该阈值，则重新进行扩容，threshold = capacity(table.length) * load factor
int threshold;
//填充因子
final float loadFactor;

重要方法

get

根据key的hashCode计算在数组里的下标，然后再判断该位置是否符合条件，否则根据链表/红黑树的方法继续找

计算下标的方法：
下标 = (n-1) & hash
hash = (h = key.hashCode()) & h>>>16

判断两个key是否相同：

 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

先判断hash，如果hash不同一定不同；如果hash相同，则利用equals判断是否相同

put

先检查容量（扩容resize）。
根据hashCode计算桶在数组里的位置，
插入该处的链表/树

resize

两倍容量。如果容量已达最大值，则设置容量为int_max。
扩容之后要重新计算index，每个桶里的节点都要重新计算位置，计算位置的方法是hash & (n-1)。
扩容之后由于newCap-1比oldCap-1多了一个高位（例如8-1=7=111，而4-1=3=11），因此节点的新位置取决于多出来的一个高位bit，如果该位是0，则还是原位置；否则应该是原位置+旧容量

扩容的过程对整个数组和桶进行了遍历，耗费性能，所以最好在创建HashMap的时候指定容量，否则在第一次put的时候会进行一次扩容（因为table==null）

参考：https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

HashMap

原文：https://www.cnblogs.com/darknessplus/p/10356235.html