HashMap源码解析 jdk1.8

HashMap继承AbstractMap,实现Map接口,Map接口定义了所有Map子类必须实现的方法。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
HashMap中定义的属性:
// 默认的初始化容量  1 << 4 位移运算 --->结果快捷计算为2n次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 树化阀值
static final int TREEIFY_THRESHOLD = 8; 

// 链表还原阀值(UNTREEIFY_THRESHOLD),表示红黑树转换为单链表结构
static final int UNTREEIFY_THRESHOLD = 6; 

// 最小树形化容量阈值
static final int MIN_TREEIFY_CAPACITY = 64;

  1、容量(capacity),代表该HashMap的数组大小。DEFAULT_INITIAL_CAPACITY表示数组的默认容量,值为16;MAXIMUM_CAPACITY表示容量最大值,值为2的30次方。

  2、加载因子(loadFactor),表示数组的使用率。loadFactor表示实际的加载因子;DEFAULT_LOAD_FACTOR表示默认加载因子,值为0.75。

  3、树化阀值(TREEIFY_THRESHOLD),表示桶的树化阀值,大小为8,即单链表转换成红黑树的阀值。当单链表长度大于该值8时才会转换。

  4、链表还原阀值(UNTREEIFY_THRESHOLD),表示红黑树转换为单链表结构。

  5、最小树形化容量阈值(MIN_TREEIFY_CAPACITY)。即当哈希表中的容量 > 该值时,才允许树形化链表 (即将链表转换成红黑树) ,否则,若桶内元素太多时,则直接扩容,而不是树形化 // 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD。转化红黑树的table容量最小容量64(JDK8定义的是64),至少是4*TREEIFY_THRESHOLD(单链表节点个数阀值,用以判断是否需要树形化)=32。用以避免 在扩容和树形结构化的阀值 可能产生的冲突。所以如果小于64必须要扩容。如果在创建HashMap实例时没有给定capacity、loadFactor则默认值分别是16和0.75。 
当好多bin被映射到同一个桶时,如果这个桶中bin的数量小于TREEIFY_THRESHOLD当然不会转化成树形结构存储;如果这个桶中bin的数量大于了 TREEIFY_THRESHOLD ,但是capacity小于MIN_TREEIFY_CAPACITY 则依然使用单链表结构进行存储,此时会对HashMap进行扩容;如果capacity大于了MIN_TREEIFY_CAPACITY ,则会进行树化。

HashMap源码解析 jdk1.8


HashMap的构造方法。
/**
* 根据给定的初始容量的装载因子创建一个空的HashMap
* 初始容量小于0或装载因子小于等于0将报异常
* 这里需要注意一个小问题,loadFactor才是初始容量,而不是initialCapacity,即如果执行new HashMap(9,0.75),那么HashMap的初始容量是16,而不是9。 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** *根据指定容量创建一个空的HashMap */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** *使用默认的容量及装载因子构造一个空的HashMap */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** *通过传入的map创建一个HashMap,容量为默认容量(16)和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者,装载因子为默认值 / public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

 

 

 

上一篇:Leetcode刷题java之872. 叶子相似的树


下一篇:JDK8:HashMap源码解析:TreeNode类的treeify方法