面试之HashMap

HashMap考的太多

作为一种常用的数据结构,HashMap在面试过程中真可谓常常被考到,应届生开发考基础大概率要问这个。HashMap由数组和链表构成的一种数据结构,等同于字典,存取key-value这样子的实例,每个放入的实例被叫做Entry。(在Java8中叫Node)

拉链法和put

这样一种结构表明了放入其中的数据不一定是有序的,通过put方法向HashMap中放入数据,首先根据放入的key的hash值去计算得到一个index值,然后遍历数组找到下标index,放入数据。

那么如果存在两个不同的数据hash之后得到相同的index,放入同一个桶(数组格子)中,这个时候就需要利用链表,将后插入的输入以链表的方式存入。Java8之前插入的方式是头插法,也就是说新插入的数据在链表的头部,之后改用了尾插法

HashMap 允许插入键为 null 的键值对,但是null没法做hash,因此设定了特定的桶号来放入null。

扩容

在HashMap放入一定量的数据后,就会自动扩容。有以下两条因素:

  • 当前容量
  • 扩容因子
    1
    2
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap的默认初始大小为16,扩容因子为0.75f。扩容的过程如下:

  1. reSize:创建一个新的Entry空数组,长度是原数组的2倍。
  2. reHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。

hash计算方法

1
index = HashCode(Key) & (Length - 1)

因此,由于原大小发生变化,hash之后的位置也产生变化。

从JDK 1.8 开始,一个桶存储的链表长度大于等于 8 时会将链表转换为红黑树,巧妙的将原本O(n)的时间复杂度降低到了O(logn)。

为什么改用尾插法

在扩容中我们看到,reHash过程会打乱之前的所有Entry,但是每个Entry在扩容之前仍有链表部分,头插法打乱后极易形成循环链表造成查找的死循环。

参考链接

https://github.com/AobingJava/JavaFamily/blob/master/docs/basics/HashMap.md
https://cyc2018.github.io/CS-Notes/#/notes/Java%20%E5%AE%B9%E5%99%A8