面试级解析HashMap

印度阿三17 2020-12-16

展开全文

------------恢复内容开始------------

在介绍HashMap之前，有必要先给大家介绍一些参数的概念

HashMap的最大容量，capacity译为容量，capacity就是指HashMap中bucket(桶)的数量。官方给的注解必须为2的幂。默认为1<<4(ps:这里的<<是位移运算符),每次扩容都会扩容为原来的2倍。总之，容量都是2的幂。

1/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

ps：位移运算符： <<左移运算符，>>右移运算符，还有不带符号的位移运算

计算过程以1<<4为例,首先把1转为二进制数字0000 0001

然后将上面的二进制数字向左移动30位后面补0得到0001 0000

最后将得到的二进制数字转回对应类型的十进制,运行结果为:16

HashMap的最大容量，默认值为1<<30, 即1073741824

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

public static void main(String[] args) {
    int i =1;
    System.out.println(i << 30);
}

loadFactor译为装载因子，装载因子用来衡量HashMap的拥挤程度。loadFactor的默认值为0.75f。当HashMap里面容纳的元素已经达到HashMap容量的75%时，表示HashMap太挤了，需要扩容，在HashMap的构造器中可以定制loadFactor。

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

树化参数

/**
 * 树化阀值，默认值为8
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 树退化阀值，默认为6
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 最小树化HashMap的capacity(容量),默认为64
 */
static final int MIN_TREEIFY_CAPACITY = 64;

size

HashMap中实际存在的键值对的数量（为链表和树中的KV的总和）

/**
 * The number of key-value mappings contained in this map.
 */
transient int size;

threshold（扩容阀值）

threshold表示当HashMap的size大于threshold时会执行resize操作。
threshold=capacity*loadFactor

/**
 * The next size value at which to resize (capacity * load factor).
 * @serial
 */
int threshold;

接下来，我们通过一场小型面试来探究下HashMap的相关知识:

面试小会场：

面试官：你能跟我聊聊HashMap吗？

小明：HashMap存储键值对实现快速存取，允许为null，key值不可重复，若key值重复则覆盖；非同步，线程不安全；底层是hash表，不保证有序(比如插入的顺序)

面试官：那你能跟我聊聊它的结构和底层原理吗？

小明：HashMap是我们平时常用的数据结构，jdk1.7之前由数组和链表组合构成的数据结构。现在是由数组、链表加红黑树构成的数据结构。数组里面每个地方都存了Key-Value这样的实例，hashMap在put插入数据的时候会根据key去hash计算index的值，如果散列表为空时，调用resize()初始化散列表，如果没有发生hash碰撞，直接添加元素到散列表中去

如图：我们通过哈希函数计算出插入（"name","张三"）的位置， index = HashCode（Key） & （Length - 1)计算出来的index为2

在这里插入图片描述

在有限的数组中，我们使用hash会有一定的概率hash到一个值上

**如果发生了碰撞(hashCode值相同)，进行三种判断 **

1.1:若key地址相同或者equals后内容相同，则替换旧值

1.2:如果是红黑树结构，就调用树的插入方法

1.3：链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的树化阙值 8 ；也可以遍历到有节点与插入元素的哈希值和内容相同，进行覆盖。

在这里插入图片描述

所以在HashMap中只能使用引用类型（如Integer、String）来作为key，因为这些类已经很规范的覆写了hashCode()以及equals()方法。当我们去get时，对key的hashCode进行hashing，与运算计算下标获取bucket(桶)位置，如果在bucket桶的首位上就可以找到就直接返回，否则在树中找或者链表中遍历找，如果有hashCode相同，则利用equals方法去遍历链表查找节点

面试官：那你能说一下为什么要引入红黑树吗？

小明：JDK 1.8 以前 HashMap 的实现是数组链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。

面试官：那你最后在说一下HashMap是如何扩容的吧

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wGAE63eL-1608046882131)(d:\images\c.png)]$

小明：如图，假设此时有一个容量为64的HashMap。1号桶内加上挂载的红黑树一共是46个KV，2号桶内加上链表上一共是3个KV，所以该hashmap实例的size = 46 3 =49。此hashaMap的threshold（扩容阈值）=capacity(当前容量64) * loadfactory(负载因子 0.75) = 48 。由公式 size> load factor * capacity可知此时49>48，所以会扩容。
扩容分为两步