JDK1.8 HashMap源码分析

JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

下图中代表jdk1.8之前的hashmap结构,左边部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。(此图借用网上的图)

JDK1.8 HashMap源码分析

图一、jdk1.8之前hashmap结构图

jdk1.8之前的hashmap都采用上图的结构,都是基于一个数组和多个单链表,hash值冲突的时候,就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时,将会花费O(n)的查找时间,会有很大的性能损失。到了jdk1.8,当同一个hash值的节点数不小于8时,不再采用单链表形式存储,而是采用红黑树,如下图所示(此图是借用的图)

JDK1.8 HashMap源码分析

图二、jdk1.8 hashmap结构图

二、重要的field

//table就是存储Node类的数组,就是对应上图中左边那一栏,
  /**
    * The table, initialized on first use, and resized as
    * necessary. When allocated, length is always a power of two.
    * (We also tolerate length zero in some operations to allow
    * bootstrapping mechanics that are currently not needed.)
  */
transient Node<K,V>[] table;
 
/**
    * The number of key-value mappings contained in this map.
*  记录hashmap中存储键-值对的数量
  */
transient int size;

/**
  * hashmap结构被改变的次数,fail-fast机制
  */
transient int modCount;

/**
    * The next size value at which to resize (capacity * load factor).
    * 扩容的门限值,当size大于这个值时,table数组进行扩容
    */
    int threshold;

/**
    * The load factor for the hash table.
    *
    */
 float loadFactor;
/**
    * The default initial capacity - MUST be a power of two.
* 默认初始化数组大小为16
    */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
    * 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;

/**
    * The load factor used when none specified in constructor.
* 默认装载因子,
    */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
    * The bin count threshold for using a tree rather than list for a
    * bin.  Bins are converted to trees when adding an element to a
    * bin with at least this many nodes. The value must be greater
    * than 2 and should be at least 8 to mesh with assumptions in
    * tree removal about conversion back to plain bins upon
    * shrinkage.
* 这是链表的最大长度,当大于这个长度时,链表转化为红黑树
    */
    static final int TREEIFY_THRESHOLD = 8;

/**
    * The bin count threshold for untreeifying a (split) bin during a
    * resize operation. Should be less than TREEIFY_THRESHOLD, and at
    * most 6 to mesh with shrinkage detection under removal.
    */
    static final int UNTREEIFY_THRESHOLD = 6;

/**
    * The smallest table capacity for which bins may be treeified.
    * (Otherwise the table is resized if too many nodes in a bin.)
    * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
    * between resizing and treeification thresholds.
    */
    static final int MIN_TREEIFY_CAPACITY = 64;

三、构造函数

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/8b4580a289de49b1e58363d4d9b1a626.html