HashMap底层原理

文章目录

- - 1.HashMap的概念
  - 2.底层数据结构
  - 2.JDK1.8之前存在的问题？
  - 3.问题：加载因子为什么默认值为0.75f ？
  - 4.问题：如果得到key的hash值（哈希码）
  - 5.问题：如何得到插入元素在数组中的下标
  - 6.问题：链表转换为红黑树的条件？
  - 7.HashMap如何实现序列化和反序列化？
  - 8.put源码
  - 9.get源码
  - 10.resize源码

1.HashMap的概念

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）HashMap不保证映射的顺序，特别是它不保证该顺序恒久不变。
在这里插入图片描述

HashMap和Hashtable的区别？添加链接描述

2.底层数据结构

HashMap底层采用哈希表结构（数组+链表、JDK1.8后为数组+链表+红黑树）实现，结合了数组和链表的优点：

数组优点： 通过数组下标可以快速实现对数组元素的访问，效率极高；

链表优点： 插入或删除数据不需要移动元素，只需修改节点引用，效率极高。

HashMap图示如下：
在这里插入图片描述

HashMap内部使用数组存储数据，数组中的每个元素类型为Node<K,V>：

//Node包含了四个字段：hash、key、value、next，其中next表示链表的下一个节点。
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 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;}
}

2.JDK1.8之前存在的问题？

JDK1.8之前，HashMap底层实现用的是数组+链表。（JDK1.8以后用数组+链表+红黑树）。

HashMap通过hash方法计算key的哈希码，然后通过（n-1）&hash 公式（n为数组长度,初始化数组默认长度为16），得到key在数组中存放的下标。

当两个key在数组中存在的下标一致时（哈希冲突，哈希碰撞），数据将以链表的方式存储。

在链表中查找数据必须从第一个元素开始一层一层往下找，直到找到为止，时间复杂度为O(N)，所以当链表长度越来越长时，HashMap的效率越来越低。

哈希码如何计算？添加链接描述

如何解决？
加入红黑树
当链表中的元素超过8个（TREEIFY_THRESHOLD）并且数组长度大于64（MIN_TREEIFY_CAPACITY）时，会将链表转换为红黑树，转换后数据查询时间复杂度从O(N)变为O(logN)。

红黑树的节点使用TreeNode表示：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 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;    TreeNode(int hash, K key, V val, Node<K,V> next) {        super(hash, key, val, next);   }   ...}

HashMap包含几个重要的变量：

// 数组默认的初始化长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 数组最大容量，2的30次幂，即1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认加载因子值
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表转换为红黑树的长度阈值
static final int TREEIFY_THRESHOLD = 8;// 红黑树转换为链表的长度阈值
static final int UNTREEIFY_THRESHOLD = 6;// 链表转换为红黑树时，数组容量必须大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;// HashMap里键值对个数
transient int size;// 扩容阈值，计算方法为 数组容量*加载因子
int threshold;// HashMap使用数组存放数据，数组元素类型为
Node<K,V>transient Node<K,V>[] table;// 加载因子
final float loadFactor;// 用于快速失败，由于HashMap非线程安全，
//在对HashMap进行迭代时，如果期间其他线程的参与
//导致HashMap的结构发生变化了（比如put，remove等操作），
//直接抛出ConcurrentModificationException异常
transient int modCount;

3.问题：加载因子为什么默认值为0.75f ？

加载因子也叫扩容因子，用于决定HashMap数组何时进行扩容。比如数组容量为16，加载因子为0.75，那么扩容阈值为数组容量加载因子，160.75=12，即HashMap数据量大于等于12时，数组就会进行扩容。

我们都知道，数组容量的大小在创建的时候就确定了，所谓的扩容指的是重新创建一个指定容量的数组，然后将旧值复制到新的数组里。扩容这个过程非常耗时，会影响程序性能。

所以加载因子是基于容量和性能之间平衡的结果：
当加载因子过大时，扩容阈值也变大，也就是说扩容的门槛提高了，这样容量的占用就会降低。但这时哈希碰撞的几率就会增加，效率下降；
当加载因子过小时，扩容阈值变小，扩容门槛降低，容量占用变大。这时候哈希碰撞的几率下降，效率提高。
可以看到容量占用和性能是此消彼长的关系，它们的平衡点由加载因子决定，0.75是一个即兼顾容量又兼顾性能的经验值。

4.问题：如果得到key的hash值（哈希码）

通过hash方法计算key的哈希码添加链接描述

5.问题：如何得到插入元素在数组中的下标

HashMap通过hash方法计算key的哈希码，然后通过（n-1）&hash 公式（n为数组长度，初始化数组默认长度为16），得到key在数组中存放的下标。

6.问题：链表转换为红黑树的条件？

长度阈值大于8，数组容量必须大于等于64

7.HashMap如何实现序列化和反序列化？

存储数据的table字段使用transient修饰，通过transient修饰的字段在序列化的时候将被排除在外，那么HashMap在序列化后进行反序列化时，是如何回复数据的呢？HashMap通过自定义的readObject/writeObject方法自定义序列化和反序列化操作。这样做出于以下两点考虑：

1)table一般不会存满，即容量大于实际键值对个数，序列化table未使用的部分不仅考虑时间也浪费空间；
2)key对应的类型如果没有重写hashCode方法，那么它将调用 Object的hashCode方法，该方法为native方法，在不同的JVM下实现可能不同；换句话讲，同一个键值在不同的JVM环境下，在table中存储的位置可能不同，那么在反序列化table操作时可能会出错。
所以在HashXXX类中（），我们可以看到，这些类用于存储数据的字段都用transient修饰，并且都自定义了readObject/writeObject方法。

8.put源码

put操作过程总结：

判断HashMap数组是否为空，是的话初始化数组（由此可见，在创建HashMap对象的时候并不会
直接初始化数组）；
通过 (n-1) & hash 计算key在数组中的存放索引；
目标索引位置为空的话，直接创建Node存储；
目标索引位置不为空的话，分下面三种情况：
4.1. key相同，覆盖旧值；
4.2. 该节点类型是红黑树的话，执行红黑树插入操作；
4.3. 该节点类型是链表的话，遍历到最后一个元素尾插入，如果期间有遇到key相同的，则直接覆
盖。如果链表长度大于等于TREEIFY_THRESHOLD(8)，并且数组容量大于等于
MIN_TREEIFY_CAPACITY(64)，则将链表转换为红黑树结构；
判断HashMap元素个数是否大于等于threshold（扩容阀值 0.75*数组初始化长度16），是的话，进行扩容操作。（扩容为原来的两倍）
put方法源码如下：

public V put(K key, V value) {    r
eturn putVal(hash(key), key, value, false, true);
}

put方法通过hash函数计算key对应的哈希值，hash函数源码如下：

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

对于 32 位的处理器，会分成高（左边的） 16 位和低（右边的） 16 位int类型的数值是4个字节的，右移16位异或可以同时保留高16位于低16位的特征

如果key为null，返回0，不为null，则通过(h = key.hashCode()) ^ (h >>> 16)公式计算得到哈希值。该公式通过hashCode的高16位异或低16位得到哈希值，主要从性能、哈希碰撞角度考虑，减少系统开销，不会造成因为高位没有参与下标计算从而引起的碰撞。得到key对应的哈希值后，再调用putVal(hash(key), key, value, false, true)方法插入元素：

//put方法首先调用一个hash方法，计算出k的hash值//将k的hash值,key,value传进来public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入falsefinal V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//判断table是否为空，如果空的话，会先调用resize扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，//若没有，则把key、value包装成Node节点，直接添加到此位置。//[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;//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，//则把p赋值给e，后续需要做值的覆盖处理if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//2.如果当前是红黑树结构，则把它加入到红黑树 else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//3.此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部else {for (int binCount = 0; ; ++binCount) {//如果头结点的下一个节点为空，则插入新节点if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//如果在插入的过程中，链表长度超过了8，则转化为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//插入成功之后，跳出循环到nextbreak;}//若在链表中找到了相同key的话，直接退出循环，跳转到nextif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// next// 此时新值要覆盖旧值if (e != null) { V oldValue = e.value;//用新值替换旧值，并返回旧值。if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//如果当前数组中的元素个数超过阈值，则扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

9.get源码

下面是get操作源码：

 public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 判断数组是否为空，数组长度是否大于0，目标索引位置下元素是否为空，是的话直接返回nullif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 如果目标索引位置元素就是要找的元素，则直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 如果目标索引位置元素的下一个节点不为空if ((e = first.next) != null) {// 如果类型是红黑树，则从红黑树中查找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {// 否则就是链表，遍历链表查找目标元素if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

10.resize源码

通过put源码分析我们知道，数组的初始化和扩容都是通过调用resize方法完成的：

final Node<K,V>[] resize() {// 扩容前的数组Node<K,V>[] oldTab = table;// 扩容前的数组的大小和阈值int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;// 预定义新数组的大小和阈值int newCap, newThr = 0;if (oldCap > 0) {// 超过最大值就不再扩容了if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 扩大容量为当前容量的两倍，但不能超过 MAXIMUM_CAPACITYelse if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 当前数组没有数据，使用初始化的值else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults// 如果初始化的值为 0，则使用默认的初始化容量，默认值为16newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 如果新的容量等于 0if (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;// 原数据不为空，将原数据复制到新 table 中if (oldTab != null) {// 根据容量循环数组，复制非空元素到新 tablefor (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != 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 order// 链表复制，JDK 1.8 扩容优化部分Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 原索引if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 原索引 + oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 将原索引放到哈希桶中if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 将原索引 + oldCap 放到哈希桶中if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}

JDK1.8在扩容时通过高位运算 e.hash & oldCap 结果是否为0来确定元素是否需要移动，主要有如下两
种情况：
情况一：
扩容前oldCap=16，hash=5， (n-1)&hash=15&5=5 ， hash&oldCap=5&16=0 ；
扩容后newCap=32，hash=5， (n-1)&hash=31&5=5 ， hash&oldCap=5&16=0 。
这种情况下，扩容后元素索引位置不变，并且hash&oldCap==0。
情况二：
扩容前oldCap=16，hash=18， (n-1)&hash=15&18=2 ， hash&oldCap=18&16=16 ；
扩容后newCap=32，hash=18， (n-1)&hash=31&18=18 ， hash&oldCap=18&16=16 。
这种情况下，扩容后元素索引位置为18，即旧索引2加16(oldCap)，并且hash&oldCap!=0。