HashMap介绍
HashMap是一个散列表，存储的是键值对HashMap<key,value>，其中key和value都可以为null，HashMap位于java.util包下，它是非线程安全的，线程安全可以使用Concurrentmap。
HashMap的内存结构
HashMap通过计算散列值hashcode来决定value的存储位置。
如图所示，HashMap的内存结构是数组和链表组成，相同的hashcode值放在同一个链表中，即所谓的hash冲突，解决hash冲突的方法是将数据存入链表中，当链表的节点数量大于8且数组的长度大于64的时候则转为红黑数，当红黑树的节点小于6时再重新转为链表。
TreeNode
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;链表中节点的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}HashMap源码分析
在Idea中我们可以通过快捷键Alt+7打开HashMap的所有方法，如下所示：
相关属性
| 类型 | 说明 | 属性 | 其它 |
| 变量 | 加载因子 | final float loadFactor; | |
| 常量 | 默认加载因子值 0.75 | static final float DEFAULT_LOAD_FACTOR = 0.75f; | |
| 常量 | 链表转红黑树的条件 | static final int MIN_TREEIFY_CAPACITY = 64; static final int TREEIFY_THRESHOLD = 8; | 当链表的节点数量大于8且数组的长度大于64的时候则转为红黑数 |
| 常量 | 红黑树转链表的条件 | static final int UNTREEIFY_THRESHOLD = 6; | |
| 变量 | 临界值或者说阈值 | int threshold; | 初始值是16 用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子） |
| 常量 | 数组的最大容量 | static final int MAXIMUM_CAPACITY = 1 << 30; | 最大值 1073741824 |
| 常量 | 数组的最小容量或者初始容量 | static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 | 初始容量 16 |
| 变量 | 散列表数组 | transient Node<K,V>[] table; | |
| 变量 | 内部结构变化的次数 | transient int modCount; | |
| 变量 | map中键值对的个数 | transient int size; |
构造方法
/**
* 使用指定的初始值构造一个空的HashMap
* 容量和加载因子
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 使用指定的初始值构造一个空的HashMap
* 容量和默认的加载因子(0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 使用默认初始容量构造一个空的HashMap
* 初始容量(16) 和 默认的加载因子 (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}HashMap有4个构造方法，默认的加载因子是0.75，默认的初始容量是16。
扩容方法resize()
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table; // 旧数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap是旧数组的长度
int oldThr = threshold; // 旧的阈值
int newCap, newThr = 0; //定义两个新的数组长度和阈值
if (oldCap > 0) { // 正常扩容
if (oldCap >= MAXIMUM_CAPACITY) { //当旧数组长度超过 1 << 30 1073741824 不进行扩容，仅仅把阈值提高到Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 扩容操作，把数组和阈值都乘以2，扩大为原来的二倍
newThr = oldThr << 1; // 阈值也扩大两倍
}
else if (oldThr > 0) // 初始化，容量就是阈值，这种情况前面分析过，是指定容量的构造方法创建的实例，第一次添加数据的时候会走这里进行初始化数组
newCap = oldThr;
else { //真正的初始化， 由默认构造方法创建的实例，在第一次添加数据的时候会走这里进行初始化数组和阈值
newCap = DEFAULT_INITIAL_CAPACITY;//默认的容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值=加载因子*默认的容量 即 0.75*16，阈值的意思是当数组中的容量超过这个值就扩容。
}
if (newThr == 0) { // 包含上面 else if (oldThr > 0) 构造方法的参数是容量，还有其他情况不太清楚
float ft = (float)newCap * loadFactor; //计算阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //给阈值变量赋值
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap]; // 先创建扩容后长度的数组
table = newTab; // 给数组的变量赋值
if (oldTab != null) { //下面就是扩容后需要重新的把数据放到新的数组上
for (int j = 0; j < oldCap; ++j) { //循环遍历旧数组
HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; //这就是直接计算在新数组中的位置，e.hash & (newCap - 1) 上面已经说过为啥这样相当于取模了
else if (e instanceof HashMap.TreeNode) //如果是红黑树，上面已经分析过这个方法了，也是遍历一遍重新找位置，只不过有一个小技巧
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
do {
next = e.next; //控制循环的
//和TreeNode的split方法类似，e.hash & oldCap 就是计算oldCap二进制的最高位对应e.hash的那一位是0还是1，
// 因为扩容是*2也就是二进制比原来多一位，如果hash对应的多出的那一位是0那和原来未扩容时的值一样，
// 如果是hash对应的多出的那一位是1，那计算的值就不一样得另外找对应的位置
if ((e.hash & oldCap) == 0) { //通过循环遍历判断，分成了两条链
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { // 一条链还是原来的位置，这个位置就是j索引所在的位置
loTail.next = null;
newTab[j] = loHead;
}
// 另一条位置计算公式 e.hash & (oldCap * 2 - 1)，
// 上面分析了能到这条链说明e.hash对应的(oldCap * 2 - 1)的最高位是1，
// e.hash & (oldCap - 1) 和 e.hash & (oldCap * 2 - 1) 差距还是那个oldCap的二进制的最高位，而且确定是1了，所以正好是oldCap
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; //所以这里是 j + oldCap
}
}
}
}
}
return newTab; //最终返回扩容后的数组
}通过HashMap扩容的源码可以得出初始容量是16，默认的加载因子是0.75，每次扩容为左移一位的位移运算 newCap = oldCap << 1，即扩大为原来的2倍。
加载因子：加载因子的意思是HashMap数组的利用率，默认是0.75，即数组大小超过了容量的75%就会扩容。
加载因子为什么是0.75
因为HashMap扩容后需要对原有的值进行rehash操作，如果这个值设置的过低的话，比如0.5， 就会增大rehash操作的次数，即hash的次数变频繁了。
如果这个值设置的过高，比如1，那么会增加查询时间的成本，如图所示。
综上所述，负载因子不可设置过大或者过小。
添加元素put()方法
/**
* 将指定值与此映射中的指定键相关联
* 如果映射先前包含密钥的映射
* 值被替换
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 实现Map.put和相关方法。
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)//如果散列表是空的或者散列表是0则进行扩容
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)// 如果桶是空的，直接创建一个Node节点放到散列表上，hash值对应的元素数组的下标通过函数 hash & (n-1)得到
tab[i] = newNode(hash, key, value, null); //单个元素不是链表也不是红黑树直接添加， i=hash & (n-1) ，p是数组的hash元素
else {//桶不是空的，说明hash到的数组中已经有元素了，后面需要判断链表或者红黑树
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //判断key和插入的key是否相同
e = p;//存在赋值给变量e
else if (p instanceof TreeNode) //如果是树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果是链表
for (int binCount = 0; ; ++binCount) {//binCount用于后面是否转红黑树的判断
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);//没有相同的key，将数据添加到链表，那么此时e是空的
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 如果e不等于null说明存在相同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;
}key的hash值计算的源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}在HashMap的put方法中首先判断散列表是否初始化，没有初始化则初始化。然后判断hash到散列表数据中位置是否已经存在元素，不存在则直接添加，进行扩容判断，已经存在则进行链表红黑树判断，最后进行相应的数据存储操作。
红黑树
红黑树是一种不严格的二叉平横查找树，它允许局部不完全平衡，需要满足如下条件
- 只有红树和黑树
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据
- 任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
HashMap为什么选择红黑树
因为它允许局部不完全平衡，省去了一些平衡操作（左旋转和有旋转），这样在数据更新删除上更快。
不过因为近似平衡，存在部分数据的高度差，在查找上可能会相对于AVL树更耗时一点。