HashMap深入理解

初始容量负(加)载因子扩容增量
ArrayList1010.5倍
Vector1011 倍
HashSet160.751 倍
HashMap160.751 倍

简介

​ HashMap基于哈希表的Map接口实现，是以key-value存储显示存在，即主要用来存放键值对。HashMap实现不是同步的，这意味着它不是线程安全的，它的key，value都可以为null。此外，HashMap中的映射不是有序的

​ jdk1.8之前HashMap由数组+链表组成，数组是HashMap的主题，链表则是为了解决Hash冲突（俩个对象调用的HashCode方法计算的哈希码值一致导致计算的数组索引值相同）而存在的（“拉链发解决冲突”）

jdk1.8优化在解决hash冲突时，有了较大的编号，当链表长度大于阀值，（或红黑树的边界值，默认为8）并且数组的长度大于64时，此时索引位置上的所有数据改为使用红黑树存储。

补充：将链表转换成红黑树前会先判断，即阀值大于8，但是数组长度小于64，此时并不会将李娜表转变为红黑树，而是选择进行数组的扩容。

​ 这样做的目的是因为数组比较小，精良避开红黑树的结构，这种情况下变为红黑树结构反而会降低效率

特点

存取无序

键和值是唯一的，底层的数据结构控制键的

jdk1.8前数据结构是：链表+数组 1.8之后是链表+数组+红黑树

阀值》8并且数组长度大于64，才将链表转为红黑树，目的是为了提高查询效率

HashMap底层的数据结构

HashMap<String,Integer> hashMap = new HashMap<>();

​ 当创建HashMap集合对象的时候，在jdk8之前，构造方法中创建一个长度是16的Entry[]table 用来存储键值对数据的。在jdk1.8以后，不是在HashMap的构造底层创建数组了，是在第一次调用put方法的时创建的数组。Node[]table用来存储键值对数据的。

​ 向Hash表中各存储数据的时候，会掉用key中的HashCode算法，计算出值，任何结合数组长度采用某种算法计算出向Node数组中存储数据的空间的索引值。如果计算出的索引空间没有数据，则直接将key对应value存储到数组中。

​ 底层采用的是key的HAshCode方法的值，结合数组长度进行无符号右移（>>>），按位异或(^)，按位与(&)计算索引对应的Hash值

​ 还可以采用取中法，去余数，伪随机数法，但这些效率都没有HashMap效率来得高。（位运算的效率高）

以下是HashMap中的源码

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

调用了java.util.objets中的

不为空就调用Object类中的方法

public static int hashCode(Object o) {
    return o != null ? o.hashCode() : 0;
}

在其中又调用了Object类中原生方法

public native int hashCode();

向哈希表中存新数据时，假设新数据值计算出的hashCode方法和之前的值重复了，那么此时数组空间不是null，次数底层会比较新值和旧值的hash值是否一致，不一致的话，花痴一个新节点来存储键值对，这种方式称为拉链法

不同的值经过hashcode（）计算有可能是一样的

假设向哈希表中存储数据，先根据新值，调用hashCode()方法结合数组长度计算。此时比较是否有数据和以及存在的数据的hash值是否相等，如果hash值相等，此时发生哈希碰撞，那么底层会调用所属类当中的equals方法比较俩个内容是否相等，如果：

相等：则将后添加数据的value覆盖之前数据的value

不相等：那么继续向下，和其他数据的key调用equals进行比较，如果都不相等，则划出一个节点存储数据

这也就是为什么,想要自定义对象作为key的时候,只要覆盖对象的hashcode和equals方法,就能完成自定义去重

如果节点长度即链表长度大于阀值8并且数组长度大于64则进行将链表变为红黑树

jdk8之前用链表解决哈希碰撞，8之后用链表+红黑树解决哈希碰撞

size表示HashMap中的k-v的实时数量，而不是数组的长度

threshold(临界值)=capacity(容量)*loadFactor(加载因子).这个值是当前已占用数组长度的最大值.size超过这个临界值就重新resize(扩容),扩容后的HashMap容量是之前俩倍

如果负载因子是默认的0.75，HashMap(16)的时候，占16个内存空间，实际上只用到了12个，超过12个就扩容。
如果负载因子是1的话，HashMap(16)的时候，占16个内存空间，实际上会填满16个以后才会扩容。

但是，用到的空间越多，hashcode重复的可能性就越大，同一个空间里面的元素数目就可能会增加，会增加哈希碰撞的可能.

扩容

分为两步

  • 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
  • ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么要ReHash因为长度扩大之后,Hash的规则也随之改变

Hash的公式---> index = HashCode（Key） & （Length - 1）

原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。

扩容前：

继承关系

Serializable

继承了该接口,表示HashMap是可以完成序列化和反序列化的

Cloneble

表示HashMap可以完成克隆

AbstractMap

父类提供了Map实现接口.以最大的限度地减少实现此接口的工作

成员变量

序列化的版本号

private static final long serialVersionUID = 362498820763181265L;

集合的初始化容量(必须是2的n此幂)

//左移4位,相当于1*2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

根据上述我们已经知道,当向HashMap中添加一个元素的时候,需要根据key的hash值,去确定其在数组中的具体位置.hashMap为了存取高效,要尽量减少碰撞,就是要精良把数据均匀分配,每个链表的长度大致相同,这个实现就在把数据存到哪个链表中的算法.这个算法就是取模

如果传入的参数不是2的n次幂,他底层会找相近于传入参数的2的n次幂,以下为源码

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

集合最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;//2的30此幂

加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

当值大于8会转成红黑树

static final int TREEIFY_THRESHOLD = 8;

为什么是8

红黑树的节点,在内存空间中是链表大小的俩倍,所以我们只在限制包含足够的节点时候才使用树节点.大于8转为红黑树,小于6转为链表,综合是为了空间和时间的权衡.

根据泊松分布,达到8的概率是0.00000006,打不到8依旧用数组+链表

static final int UNTREEIFY_THRESHOLD = 6;

如果数组小于64，那么不转换成红黑树，而是扩容（一定要数组长度8和链表节点64同时满足）

static final int MIN_TREEIFY_CAPACITY = 64;

table用来初始化,存储元素的数组

transient Node<K,V>[] table;

table在jdk1.8中，HashMap是数组加链表加红黑树来组成的结构，其中table就是HashMap中的数组，jdk1.8之前数组类型是entry<K，V>类型。从jdk1.8之后是Node<K,V>类型。只是换了个名字，都实现了一样的接口:Map.Entry<K,V>。

用来存放缓存

transient Set<Map.Entry<K,V>> entrySet;

size是元素存放的个数，不等于数组长度

transient int size;

modCount记录了每次扩容和更改Map结构的计数器

transient int modCount;

边界值，当实际大小（容量*负载因子）超过临界值时 会进行扩容美国

int threshold;

加载因子（）

final float loadFactor;

加载因子，是迎来衡量HAshMap满的程度，印象hash操作到同一个数组位置的概率1，计算的方法为size/capacity

loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好用的临界值。

当HashMap里面容纳的元素，以及达到HashMap数组的长度百分之我=75时，表示HAshMap太拥挤了，需要扩容，而扩容这个过程涉及到rehash，赋值数据等操作，非常的小号性能。所以开发中尽量减少扩容的次数，可以通过创建1指定HashMap集合兑现时指定初始容量来尽量避免

如果数组太满，会出现有链表之下的数据长度很长，导致节点超过8的概率变大，并且转换红黑树的效率也会降低

构造方法

构造一个空的HashMap，默认初始容量16，和默认负载因子0.75

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

2.构造一个具有指定初始容量和1默认负载因子（0.75）HashMap

//指定容量大小的构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

3构造一个具有指定的初始容量和负载因子的HashMap

//指定容量大小和加载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
    //判断初始容量initialCapacity是否小于0
    if (initialCapacity < 0)
        //小于0抛出非法的参数异常IllegalArgumentException
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY的最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //返回比指定初始化容量大的最小n此幂
    this.threshold = tableSizeFor(initialCapacity);
}

包含另一个Map的构造函数

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

成员方法

增加方法

put方法比较复杂，实现步骤大概如下

1.通过hash值计算出key映射到哪个桶;

2.如果桶上没冲突,直接插入

3.如果桶上出现碰撞了,则需要处理冲突

a:如果该桶的使用红黑树处理冲突,则调用红黑树的方法插入数据;

b:否在采用传统的链式方法去插入.如果1链的长度达到临界值,则把链转变为红黑树

4如果桶中存在重复的键,则该键替换为新值value

5如果size大于阈值threshold则进行扩容

删除

首先找到元素的位置,如果是链表就遍历链表找到元素之后删除.如果是红黑树就遍历树,如何找到之后做删除我,树小于6的时候要转链表

get

1.通过hash值获取key,映射到桶

2.桶上的key就是要查找的key,则直接找到并返回

3.同上的key不是要找的key,则查询后续的节点

  • 如果后续节点是红黑树节点,通过调用红黑树的方法根据key获取value
  • 如果后续节点是链表节点,则通过循环遍历链表根据key获取value

1.8之后的改变

1.8之后hashMap的插入由头插法改成了尾插法

就是说原本是A->B，在扩容后那个链表还是A->B

Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

HashTable

​ Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

​ Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。

​ Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。

区别

继承父类不同

HashTable继承自Dictionary类,而HashMap继承自ABstractMap类,但二者都实现了Map接口

线程安全性不同

javadoc中关于hashmap的一段描述如下：此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

Hashtable 中的方法是Synchronize的，而HashMap中的方法在缺省情况下是非Synchronize的。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步，但使用HashMap时就必须要自己增加同步处理。

效率

因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；

底层结构

JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

Last modification：October 24, 2022
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏