转载

HashMap源码分析

HashMap源码分析

分析HashMap源码,以put操作为例进行相关的分析。

  • 在HashMap中,会将插入的<Key, Value>键值对封装成一个个Node对象

  • 在put方法中会调用putVal方法。

  • 在putVal方法中会对传入的Key来计算其对应的hash值,这里调用hash(Object key)函数来实现计算逻辑。

  • putVal方法实现逻辑

    • 判断哈希表是否为空,如果为空,则调用resize( )方法进行初始化。

    • 在resize方法中对空表进行初始化。

    • 向哈希表中添加元素,此时将分为以下两步进行考虑:

      • 该元素对应在哈希表中的位置不包含元素,即未发生冲突

      • 如果包含元素,则说明发生了冲突,p对应着哈希表中对应位置的元素

        • 如果p对应的元素与插入的元素的key值相同并且hash值相同,则考虑值覆盖情形。

        • 不相同,则处理冲突,处理冲突时需要判断当前处理冲突的方法是否是基于红黑树的

        • 不是基于红黑树的,则按照链表进行处理

        • 判断是否需要进行覆盖操作,用变量e来进行标识,e不为空则说明存在一个节点与插入的元素具有相同的key值和hash值。

        • 最后判断是否需要进行扩容操作

  • 在扩容操作中,先对原始哈希表进行扩容,扩容后的哈希表的容量为原始哈希表大小的两倍。并且在扩容后需要对原始哈希表中的元素进行重新映射。包含以下两步:

    • 扩容哈希表

    • 元素重新映射,包含以下三种情况:

      • 原始哈希表中的元素不存在冲突,则直接映射即可。

      • 原始哈希表中的节点存在冲突并且是采用的红黑树,对于红黑树处理的冲突,采用分裂算法,即将红黑树进行分裂

      • 原始哈希表中的节点存在冲突并且是采用的链表,采用基于链表法时需要考虑,原始冲突链表中的元素位置是否会发生移动。

      • 扩容后元素不会发生移动。

      • 扩容后元素会发生移动。

      • 确定元素在新哈希表中的位置

    • Java 1.7 HashMap实现原理图:

    • Java 1.8 HashMap实现原理图:

正文到此结束
本文目录