HashMap底层实现原理及扩容机制

HashMap的数据结构:数组+链表+红黑树;Java7中的HashMap只由数组+链表构成;Java8引入了红黑树,提高了HashMap的性能;借鉴一张图来说明,原文:https://www.jianshu.com/p/8324a34577a0

        HashMap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。它的key、value都可以为null,映射不是有序的。
Hashmap不是同步的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

奥门永利误乐域 1

        HashMap中有两个重要的参数:初识容量、加载因子。

下面简单说一下存储过程:

        容量:哈希表中bucket数量,初识容量是哈希表在创建时的容量

1.接受传入的参数,通过key计算hash值,得到数组下标位置;未发生hash碰撞,直接插入结束;发生hash碰撞,走第2步;

       
加载因子:是哈希表在容量自动增加前可达到多满的一种尺度。当哈希表中的条目数量超出了加载因子与当前容量的乘积时,就要对该哈希表进行rehash操作(重建内部结构,bucket*2)。加载因子大,填满的元素就越多,空间利用率高,冲突的机会加大;否则相反。

2.判断当前数据节点是红黑树还是链表,如果是链表,将数据放入链表头节点,原数据往后移;如果是红黑树,走第3步;

        在读HashMap 源码前,里面的一些关键成员变量以及知识点,先捋一遍。

3.直接在红黑树插入数据结束;

        1、initialCapacity:初始容量。指的是 HashMap
集合初始化的时候自身的容量。可以在构造方法中指定;如果不指定的话,总容量默认值是
16 。需要注意的是初始容量必须是 2 的幂次方(为什么是2的幂次方请看)

HashMap数组元素和链表使用Node类实现,同Java7中使用Entry类实现是一样的,只是换了名字而已;Node是HashMap静态内部类,实现了Map.Entry接口;同样有以下4个重要属性:

        2、size:当前 HashMap
中已经存储着的键值对数量,即 HashMap.size() 

        final int hash; // 哈希值,HashMap根据该值确定记录的位置
        final K key; // key
        V value; // value
        Node<K,V> next;// 链表下一个节点

        3、loadFactor:加载因子。所谓的加载因子就是 HashMap
(当前的容量/总容量) 到达一定值的时候,HashMap
会实施扩容。加载因子也可以通过构造方法中指定,默认的值是 0.75
。举个例子,假设有一个 HashMap 的初始容量为 16 ,那么扩容的阀值就是 0.75
* 16 = 12 。也就是说,在你打算存入第 13 个值的时候,HashMap
会先执行扩容。

红黑树采用的是TreeNode类实现,它继承了LinkedHashMap.Entry类

        4、threshold:扩容阀值。扩容阀值 = HashMap 总容量 *
加载因子。当前 HashMap
的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap
总容量的两倍。比如,当前 HashMap 的总容量为 16 ,那么扩容之后为 32。

下面是HasMap的一些重要参数:

        5、table:Entry 数组。我们都知道 HashMap 内部存储 key/value
是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。

/** 
   * 主要参数 同  JDK 1.7 
   * 即:容量、加载因子、扩容阈值(要求、范围均相同)
   */

  // 1. 容量(capacity): 必须是2的幂 & <最大容量(2的30次方)
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
  static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 =  2的30次方(若传入的容量过大,将被最大值替换)

  // 2. 加载因子(Load factor):HashMap在其容量自动增加前可达到多满的一种尺度 
  final float loadFactor; // 实际加载因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75

  // 3. 扩容阈值(threshold):当哈希表的大小 ≥ 扩容阈值时,就会扩容哈希表(即扩充HashMap的容量) 
  // a. 扩容 = 对哈希表进行resize操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数
  // b. 扩容阈值 = 容量 x 加载因子
  int threshold;

  // 4. 其他
  transient Node<K,V>[] table;  // 存储数据的Node类型 数组,长度 = 2的幂;数组的每个元素 = 1个单链表
  transient int size;// HashMap的大小,即 HashMap中存储的键值对的数量


  /** 
   * 与红黑树相关的参数
   */
   // 1. 桶的树化阈值:即 链表转成红黑树的阈值,在存储数据时,当链表长度 > 该值时,则将链表转换成红黑树
   static final int TREEIFY_THRESHOLD = 8; 
   // 2. 桶的链表还原阈值:即 红黑树转为链表的阈值,当在扩容(resize())时(此时HashMap的数据存储位置会重新计算),在重新计算存储位置后,当原有的红黑树内数量 < 6时,则将 红黑树转换成链表
   static final int UNTREEIFY_THRESHOLD = 6;
   // 3. 最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树)
   // 否则,若桶内元素太多时,则直接扩容,而不是树形化
   // 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
   static final int MIN_TREEIFY_CAPACITY = 64;

作者:Carson_Ho
链接:https://www.jianshu.com/p/8324a34577a0
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

        6、在 Java 1.7 中,HashMap 的实现方法是数组 + 链表的形式。上面的
table 就是数组,而数组中的每个元素,都是链表的第一个结点。即如下图所示:

HashMap的加载因子:

奥门永利误乐域 2

加载因子越大:空间利用越高,扩容前填充的元素越多,put操作较快;但是链表容易过长,hash碰撞几率较大,get操作较慢;

源码分析

加载因子越小:get操作较快,链表短,hash碰撞几率低;但是空间利用率低,put元素过多会导致频繁扩容,影响性能;

构造函数:HashMap 的所有构造方法最后都会去调用 HashMap(int
initialCapacity, float
loadFactor) 。在其内部去设置初始容量和加载因子。而最后的 init() 是空方法。如下图:

个人觉得我们在使用HashMap的时候,如果预先知道大概要操作的元素数量,最好给一个初始化值,首先尽量避免扩容,其次根据业务场景结合重要参数来设定一些值来提高使用效率;

奥门永利误乐域 3

HashMap的扩容原理:我们都知道Java中数组是无法自动扩容的,HashMap的方法是使用一个新的数组代替原有的数组,对原数组的所有数据进行重新计算插入新数组,之后指向新数组;如果扩容前数组已经达到最大了,那么将直接将阈值设置成最大整形return;

put 方法

奥门永利误乐域,HashMap每次扩容增长一倍,例如HashMap初始容量为16,加载因子0.75,当容量达到12的时候进行扩容,扩容到2的5次幂;

奥门永利误乐域 4

 

根据以上源码,我们知道

        1、如果 table 数组为空时先创建数组,并且设置扩容阀值;

        2、如果 key 为空时,调用 putForNullKey 方法特殊处理;

        3、计算 key 的哈希值;

        4、根据第三步计算出来的哈希值和当前数组的长度来计算得到该 key
在数组中的索引,其实索引最后的值就等于 hash%table.length ;

        5、遍历该数组索引下的整条链表,如果之前已经有一样的 key
,那么直接覆盖 value ;

发表评论

电子邮件地址不会被公开。 必填项已用*标注