深入解析HashMap的特性以及源码

沉淀是不容易的，它需要沉下心，同时也是因为沉淀本身并没有效益，所以沉淀的意义是什么呢，有时候会突然发呆自己如果不做程序员，将来会做什么

HashMap，经典中的经典，重中之重，不多说了，留存很久了，再次梳理下吧

HashMap也是分1.7和1.8，JDK1.7用的是数组+链表，JDK1.8用的是数组+链表+红黑树，这里不多说1.7了，咱直接说1.8，如果还有人用1.7，对不起，你该升升级了

基本特性

1. 无序
2. 结构：数组+链表+红黑树
3. 默认初始容量16
4. 线程不安全
5. key和value可以存null
6. 初始容量(预计大小/负载因子0.75 + 1），每次扩容容量变为原来的2倍，所以HashMap 总是使用 2 的幂作为哈希表的大小

时间复杂度

存数据的时间复杂度是O(1),因为只需要首先根据Key计算哈希值，其实就是数组的下标，找到存放的位置，然后把key-value链表节点链接上去就OK了。

取数据的时间复杂度最好是O(1)，最差是O(n)，如果是红黑树节点就是O(logN)

为什么呢？因为如果根据key首先得到哈希地址，发现该下标处位置已经被占用，那么我们要找的节点到底在链表的哪个位置，如果该位置就只有一个节点或者要找的节点就在表头，那么就不用再往后遍历链表了，所以最好情况下时间复杂度是O(1)；如果要找到的节点在链表表尾，那么就需要一个一个遍历链表，所以此时最差情况下为O(n)。但是如果我们的链表长度都很短，那么时间效率就会很高，其实即使是O（n）这个级别的复杂度正常也还是可以接受的

关于使用

initialCapacity=(需要存储的元素个数/负载因子0.75) + 1

负载因子是0.75，初始化容量时需要遵循这个公式，guava，hutool包都已经封装好了直接用就行Maps，MapUtil，大家可以自行查看API

源码分析

属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {// 序列号private static final long serialVersionUID = 362498820763181265L;    // 默认的初始容量是16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   // 最大容量static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的填充因子static final float DEFAULT_LOAD_FACTOR = 0.75f;// 当桶(bucket)上的结点数大于这个值时会转成红黑树static final int TREEIFY_THRESHOLD = 8; // 当桶(bucket)上的结点数小于这个值时树转链表static final int UNTREEIFY_THRESHOLD = 6;// 桶中结构转化为红黑树对应的table的最小大小static final int MIN_TREEIFY_CAPACITY = 64;// 存储元素的数组，总是2的幂次倍transient Node<k,v>[] table; // 存放具体元素的集transient Set<map.entry<k,v>> entrySet;// 存放元素的个数，注意这个不等于数组的长度。transient int size;// 每次扩容和更改map结构的计数器transient int modCount;   // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容int threshold;// 填充因子final float loadFactor;
}

哈希算法

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

（1）首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。更大程度上减少了碰撞率

（2）在putVal源码中，我们通过(n-1)&hash获取该对象的键在hashmap中的位置。（其中hash的值就是（1）中获得的值）其中n表示的是hash桶数组的长度，并且该长度为2的n次方，这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算

put

以下是具体的put过程（JDK1.8版）

1、对Key求Hash值，然后再计算下标

2、如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）

3、如果碰撞了，以链表的方式链接到后面

4、如果链表长度超过阈值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表

5、如果结点已经存在就替换旧值

6、如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// 声明局部变量：节点数组tab，当前节点p，数组长度n，桶索引iNode<K,V>[] tab; Node<K,V> p; int n, i;// 检查table是否未初始化或为空，或长度为0，若是则调用resize()进行初始化或扩容，同时获取扩容后的数组长度if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 计算桶索引i，采用(n - 1) & hash的方式，确保索引非负且在数组范围内if ((p = tab[i = (n - 1) & hash]) == null) {// 如果桶位上没有节点，直接新建节点并放入该位置tab[i] = newNode(hash, key, value, null);} else {// 桶位上有节点，开始处理冲突Node<K,V> e; K k;// 检查首节点p是否就是要插入的键值对，如果是则更新节点值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果p是红黑树的节点，调用红黑树的插入方法处理else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 如果是链表，则遍历链表处理冲突else {// 遍历链表直到找到相同hash和key的节点，或找到null位置插入新节点for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {// 在链表尾部插入新节点p.next = newNode(hash, key, value, null);// 链表长度达到TREEIFY_THRESHOLD（默认8）- 1时，链表转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1是因为首次插入时就计数了treeifyBin(tab, hash);break;}// 如果找到了相同的键，则跳出循环，后面会处理，比如此时map中已经有key=a,value=x的数据了if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e; // 否则继续遍历下一个节点}}// e不为null表示存在相同的键，进行值替换或返回旧值if (e != null) { V oldValue = e.value;// 如果onlyIfAbsent为false或旧值为null，则更新值if (!onlyIfAbsent || oldValue == null)e.value = value;// 调用回调方法afterNodeAccessafterNodeAccess(e);return oldValue; // 返回旧值}}// 插入新节点后，修改modCount（结构修改次数）和size（元素数量）++modCount;if (++size > threshold) // 如果超过扩容阈值，则进行扩容resize();// 调用回调方法afterNodeInsertion，根据evict决定是否需要移除过期节点afterNodeInsertion(evict);return null; // 插入成功返回null
}

可以看到，HashMap的put会返回key上一次保存的书

get

final Node<K,V> getNode(int hash, Object key) {// 声明局部变量：节点数组tab，桶的第一个节点first，当前节点e，数组长度n，键kNode<K,V>[] tab; Node<K,V> first, e; int n; K k;// 检查table是否已初始化且长度大于0if ((tab = table) != null && (n = tab.length) > 0) {// 计算桶索引，并获取该桶的第一个节点firstNode<K,V> first = tab[(n - 1) & hash];// 检查桶中是否有节点if (first != null) {// 首先检查第一个节点是否匹配if (first.hash == hash && // 检查哈希值((k = first.key) == key || // 检查键是否相等（包括null）(key != null && key.equals(k)))) // 如果key不为null，使用equals比较return first; // 匹配成功，直接返回节点// 第一个节点不匹配，检查是否为红黑树节点if ((e = first.next) != null) {if (first instanceof TreeNode) // 是红黑树节点// 调用红黑树的getTreeNode方法查找return ((TreeNode<K,V>)first).getTreeNode(hash, key);else { // 链表结构// 遍历链表寻找匹配的节点do {if (e.hash == hash && // 检查哈希值((k = e.key) == key || // 检查键是否相等（包括null）(key != null && key.equals(k)))) // 使用equals比较return e; // 找到匹配节点，返回} while ((e = e.next) != null); // 继续遍历下一个节点}}}}// 未找到匹配的节点，返回nullreturn null;
}

扩容

final Node<K,V>[] resize() {// 保存旧的哈希桶数组引用Node<K,V>[] oldTab = table;// 获取旧容量int oldCap = (oldTab == null) ? 0 : oldTab.length;// 获取旧的扩容阈值int oldThr = threshold;// 新容量和新阈值初始化int newCap, newThr = 0;// 如果旧容量大于0if (oldCap > 0) {// 若旧容量已达最大值，设置阈值为最大整数值，直接返回，不进行扩容if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 若未达最大值，且旧容量翻倍后仍小于最大值且旧容量大于等于默认初始容量，// 则新容量为旧容量的两倍，新阈值也为旧阈值的两倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 如果旧容量为0，但阈值大于0，说明初始容量被直接设置在了阈值里else if (oldThr > 0) newCap = oldThr;// 如果旧容量和旧阈值均为0，使用默认初始容量和相应的默认阈值else {               newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果新阈值仍未初始化，根据新容量和加载因子计算新阈值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 设置新的扩容阈值threshold = newThr;// 创建新容量大小的桶数组，类型转换并强制类型转换警告抑制@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 将新桶数组引用赋值给tabletable = newTab;// 如果旧桶数组不为空，开始转移节点if (oldTab != null) {// 遍历旧桶数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e; // 当前桶中的头节点if ((e = oldTab[j]) != null) {// 将旧桶对应位置设为null，帮助垃圾回收oldTab[j] = null;// 如果当前桶只有一个节点，直接移动到新桶对应位置if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 如果是红黑树节点，执行树的拆分操作else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 链表节点的再散列与分配else { // preserve orderNode<K,V> loHead = null, loTail = null; // 低位链表头尾指针Node<K,V> hiHead = null, hiTail = null; // 高位链表头尾指针Node<K,V> next;do {next = e.next;//根据原哈希值判断节点应该分配到新数组的哪一半  将Node结点的next赋值给next if ((e.hash & oldCap) == 0) {//如果结点e的hash值与原hash桶数组的长度作与运算为0if (loTail == null)//如果loTail为nullloHead = e;//将e结点赋值给loHeadelseloTail.next = e;//否则将e赋值给loTail.nextloTail = e;//然后将e复制给loTail}else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0if (hiTail == null)//如果hiTail为nullhiHead = e;//将e赋值给hiHeadelsehiTail.next = e;//如果hiTail不为空，将e复制给hiTail.nexthiTail = e;//将e复制个hiTail}} while ((e = next) != null);//直到e为空if (loTail != null) {//如果loTail不为空 将拆分后的链表分别放入新桶数组对应位置loTail.next = null;//将loTail.next设置为空newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处}if (hiTail != null) {//如果hiTail不为空hiTail.next = null;//将hiTail.next赋值为空newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度]}}}}}return newTab;
}

相关问题

为什么线程不安全？

首先它没有锁，并且

• 死循环
• 数据丢失
• 数据覆盖

1.8尾插法已经解决了死循环和数据丢失，但是put仍然会覆盖

拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢

HashMap为什么要保证 capacity 是2的次幂呢？

1. 可以用index = hash & (capacity - 1); &是位运算性能远高于%取模运算
2. 提高hash分布均匀性

好了，今天的故事就讲到这里了，祝我们好运连连