简单介绍

HashMap是一种以 key-value 对的形式存储的数据结构，其中key一定是唯一的（可以为null，但 null 作为键只能有一个，null 作为值可以有多个），如果再次添加相同的key值，它会覆盖key值所对应的内容。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 “hash” 判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的元素的 “hash” 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

以下是 jdk1.8 “hash” 的实现

1
2
3
4
5
static final int hash(Object key) {
    int h;
    // >>>:无符号右移，忽略符号位，空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

扩容机制

JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap的数据结构组成为 数组+(链表或红黑树)

img1

HashMap 的扩容机制：HashMap 的默认容量是16，负载因子是0.75，当存储的数量达到容量乘上负载因子的时候就会触发扩容，也就是说 16×0.75=12 的时候出触发扩容。扩容的时候就是创建一个新的数组，容量是容量是之前的两倍，再把所有的元素的 Hash 值都重新计算也就是rehash的过程，最后放进新的 HashMap 里。

首先要进一步理解HashMap原理需要完全理解一下几个概念:

hashCode方法

hashCode 是 Object 类中自带的一个方法，返回的值是对象在内存中的地址经过hash函数（散列函数）计算出的某个值。

并不代表对象的地址（因为可能会产生hash冲突），但为了方便理解，我们在下面称其为“近似地址值”。

equals方法

equals()方法在object类中定义如下： 

1
2
3
public boolean equals(Object obj) {  
    return (this == obj);  
}

其中 == 比较的是两个对象的hashCode，所以equels方法默认比较的是“近似地址值”。

但一般在对一些对象进行比较时，我们往往更在意的是他们的内容的比较，而并非值的比较。比如在比较两个 Integer 是否相等时，我们肯定更在意他们的值，而并非对象的地址。

实际上 String、Math、Integer、Double 等这些封装类在使用 equals 方法时，已经重写了 Object 类的 equals 方法。如果对象的内容相等，equals 就会返回 true。

重写 equals 方法就必须重写 hashCode 方法

因为两个相等的对象的 hashCode 值必须是相等。也就是说如果 equals 方法判断两个对象是相等的，那这两个对象的 hashCode 值也要相等。

如果重写 equals() 时没有重写 hashCode() 方法的话就可能会导致 equals 方法判断是相等的两个对象，hashCode 值却不相等。

整理思路

当 HashMap 放入一个元素：

  • 第一步：

    • 如果是第一个元素（首次put时），先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；

    • 不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；

  • 第二步：

    • 首先判断 key 是否为 null，如果是 null，就单独调用 putForNullKey(value) 处理。

    • 先计算hashCode()，然后进行二次hash，调用 indexFor(hash, table.length)，找到Entry数组的索引i。

    • 如果对应位置已有元素（链表）存在：

      • 逐个判断，如果发现有节点的 hash，key（equals函数）都相同的节点时，就替换为新的value，然后返回旧的value。

    • 没有对应位置没有元素存在：

      • 在对应 table[i] 放入 Entry。

  • 第三步

    • 如果 HashMap 大小超过临界值，就要重新设置大小，扩容。
    • 当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树。