HashMap原理

发表于 | 分类于 |
字数统计: 2.6k | 阅读时长 ≈ 9

HashMap实现原理

概述

HashMap是基于哈希表的Map接口的非同步实现。元素以键值对的形式存放，并且允许null键和null值，因为key值唯一（不能重复），因此，null键只有一个。另外，hashmap不保证元素存储的顺序，是一种无序的，和放入的顺序并不相同（此类不保证映射的顺序，特别是它不保证该顺序恒久不变）。HashMap是线程不安全的。

继承关系

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

其中相关的属性：（JDK1.8）

1
2
3
4
5
6
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  默认的初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载因子
static final int TREEIFY_THRESHOLD = 8; //链表长度的阈值，当超过8时，会进行树化（不绝对，如下面源码分析）
static final int UNTREEIFY_THRESHOLD = 6; //当树中只有6个或以下，转化为链表
transient int size; //HashMap的大小
int threshold; //判断是否扩容的阈值

Note：HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap

从下图中看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

在这里插入图片描述

HashMap的数据存储结构

HashMap由数组+链表+红黑树进行数据的存储

HashMap采用table数组存储Key-Value的，每一个键值对组成了一个Node节点（JDK1.7为Entry实体，因为jdk1.8加入了红黑树，所以改为Node）。Node节点实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Node节点，以此来解决Hash冲突的问题。

1
2
3
4
5
6
7
transient Node<K,V>[] table; //默认数组

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

从源码，Node就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

HashMap实现存储和读取

put操作

put操作所对应的实现流程如下图所示：

在这里插入图片描述

由上面的源码可知,，当添加一个Key-Value时，我们通过hash()计算出Key所对应的hash值，然后去调用putVal（）真正的执行put操作。

  1. 首先判断数组是否为空，如果是，则进行初始化。
  2. 其次，根据 (n - 1) & hash 求出要添加对象所在的索引位置，判断此索引的内容是否为空，如果是，则直接存储，
  3. 如果不是，则判断索引位置的对象和要存储的对象是否相同，首先判断hash值知否相等，再判断key是否相等。（1.两个对象的hash值不同，一定不是同一个对象。2.hash值相同，两个对象也不一定相等）。如果是同一个对象，则直接进行覆盖，返回原值。
  4. 如果不是，则判断是否为树节点对象，如果是，直接添加
  5. 当既不是相同对象，又不是树节点，直接将其插入到链表的尾部。在进行判断是否需要进行树化。
  6. 最后，判断hashmap的size是否达到阈值，进行扩容resize()处理。

resize（）扩容操作

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高效率，就要对hashmap的数组进行扩容，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能

初始化和扩容的具体流程如下：

在这里插入图片描述

treeifyBin操作

树化的基本操作流程如下：（不涉及左旋和右旋操作，因为不会呀）

在这里插入图片描述

HashMap的面试相关

HashMap和Hashtable的区别

HashMap和Hashtable都实现了Map接口，。主要的区别有：

  1. 对Null key 和Null value的支持：HashMap可以接受为null的键值(key)和值(value)，Hashtable不能接受null值，会产生空指针异常。
  2. 线程是否安全： HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的
  3. 效率： 由于Hashtable是线程安全的，所以在单线程环境下比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
  4. 初始容量大小和每次扩充容量大小的不同：HashMap初始大小为16，扩容为2的幂次方；HashTable初始为11，扩容为2n+1
  5. 底层结构：HashMap会将链表长度大于阈值是转化为红黑树（会先判断当前数组的长度是否小于 64，是则扩容，而不转化），将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet区别

HashSet 底层就是基于 HashMap 实现的。（HashSet的对象相当于存储在HashMap的Key上，所以保证了唯一性）

在这里插入图片描述

HashSet如何检查重复

当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

hashCode()与equals()的相关规定： 如果两个对象相等，则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true

两个对象有相同的hashcode值，它们也不一定是相等的 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与equals的区别： ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较 ==指引用是否相同 equals()指的是值是否相同

HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。因此，我们首先用hash对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标 hash%tab.length。但是，当数组的长度为2的幂次方时，hash%tab.length等价于hash&(tab.lenngth-1)。（取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作）。并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

HashMap 多线程操作导致死循环问题

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

hashmap为什么在链表长度大于8，且数组长度大于64时将链表转换为红黑树

这个问题分两步分析：

为什么是链表长度大于8时

看一下源码解释

img

就是官方做过很多测试，发现链表长度在大于8以后再出现hash碰撞的可能性几乎为0，虽然转化为红黑树后，查找的效率会比链表高，但是转化红黑树这个过程是耗时的，而且在扩容时还要对红黑树重新的左旋右旋保持平衡，相对耗时，所以，阈值设置为8就是为了尽量减少hashmap中出现红黑树（hashmap中链表才是常态）

为什么数组长度大于64时

同样，先看一下源码怎么解释的

img

其实这个源码中解释的不清不楚，里边说最小应该为4*8的倍数（TREEIFY_THRESHOLD=8）以减少碰撞，那这个也可以是32呀。

可能没有什么实际根据，不像上边的阈值8一样，是经过实际测试过的。这里只是猜测，也有可能是根据操作系统有关：64位的操作系统的最大内存寻址空间为2的64次方，数组长度小于64时，64位的操作系统也完全能够应对，这时候进行扩容要比转化红黑树效率高的多；相反，如果数组过长，进行一次扩容要迁移的数据更多，会比转化红黑树效率低。（这里只是猜测，后续如有新的证明会及时更新）