在上篇博客中分析了 hashmap 的用法, 详情查看 java 并发之 hashmap
本篇博客重点分析下 hashmap 的源码(基于 JDK1.8)
一, 成员变量
HashMap 有以下主要的成员变量
- /**
- * The default initial capacity - MUST be a power of two.
- 默认初始容量
- */
- 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.
- JDK1.8 在哈希冲突后, 使用链表的方式存储数据, 当链表中元素个数超过 8 个, 则转化为红黑树的格式
- */
- 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.
- 当红黑树的节点数少于 6 个, 则转化为链表
- */
- static final int UNTREEIFY_THRESHOLD = 6;
- /**
- * 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;
- /**
- * Holds cached entrySet(). Note that AbstractMap fields are used
- * for keySet() and values().
- */
- transient Set<Map.Entry<K,V>> entrySet;
- /**
- * The number of key-value mappings contained in this map.
- key-value 的个数
- */
- transient int size;
上面对 HashMap 中的主要成员变量做了注释, 重点关注以下几个,
transient Node<K,V>[] table 这个成员变量是 HashMap 存储键值对的载体, Node 类型的数组, 可以联想到把键值对封装成了 Node 对象, 然后使用数组存储一个一个的 Node, 体现了 Java 三大特性中的封装.
static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; HashMap 的默认容量, 即 table 数据组的默认长度, 在构建 table 数组时使用.
static final int MAXIMUM_CAPACITY = 1 << 30 HashMap 的最大容量, 即 table 数据的最大长度.
static final float DEFAULT_LOAD_FACTOR = 0.75f 默认的加载因子, 这个变量很重要, 关系到 HashMap 扩容以及数组的饱和程度等
final float loadFactor 加载因子
int threshold 代表 HashMap 的阈值,=table 数组的长度 * loadFactor, 当 HashMap 中键值对的数量大于 threshold 的时候便需要扩容, 即把数据的长度扩大一倍
二, 构造函数
HashMap 提供了以下 4 个构造函数,
1,HashMap()
这个是默认的构造函数, 其实现如下
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
- }
从其实现来看, 仅指定了默认的负载因子, 其他的均为默认值, 默认的负载因子为 0.75, 这个值是经过经验得出的, 是空间和时间上的一个均衡.
2,HashMap(int initialCapacity)
这个可以指定 HashMap 的初始容量, 但此容量并非要创建的 Node 类型的 table 的长度, HashMap 使用了 tableSizeFor(int cap)方法对其处理, 此方法下面会说到. 构造方法的实现如下,
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
实现即调用了另一个构造方法
3,HashMap(int initialCapacity, float loadFactor)
这个构造方法可以指定两个参数, 一个是初始容量, 另一个是负载因子, 前面说到容量 * 负载因子 = 阀值 (threshold), 当键值对的数量(size) 大于阀值时便要扩容. 构造方法实现如下,
- 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);
- }
对给定的初始容量做了判断, 最后通过 tableSizeFor 函数计算出的值给了 threshold.
4,HashMap(Map<? extends K, ? extends V> m)
使用一个 Map 类型的变量构造 HashMap, 其实现如下
- public HashMap(Map<? extends K, ? extends V> m) {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- putMapEntries(m, false);
- }
指定了负载因子, 看起来负载因子很重要.
- final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
- int s = m.size();
- if (s> 0) {
- if (table == null) { // pre-size
- float ft = ((float)s / loadFactor) + 1.0F;
- int t = ((ft <(float)MAXIMUM_CAPACITY) ?
- (int)ft : MAXIMUM_CAPACITY);
- if (t> threshold)
- threshold = tableSizeFor(t);
- }
- else if (s> threshold)
- resize();
- for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
- K key = e.getKey();
- V value = e.getValue();
- putVal(hash(key), key, value, false, evict);
- }
- }
- }
从 4 个构造方法中, 可以看出都并未初始话 table 变量, 即存储数据的数组, 那么 table 变量在什么时候初始化那, 是在 put 方法中. 为什么要放在 put 方法中, 那是因为如果我就调用了构造方法, 然后初始化了 table 数组, 分配了内存, 然而我不向 HashMap 中放数据, 即不调用 put 方法, 那么肯定会造成内存的浪费, 所以只有在真正调用 put 的时候才初始化 table, 考虑周全呀.
二, 工具函数
这里重点分析两个工具函数, hash 和 tableSizeFor.
1,hash(Object key)
此函数的作用是传递一个 key 参数, 返回一个 int 数值,
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
如果 key 为 null, 则返回 0, 否则, 取 key 的 hashCode 值 h 和 h 无符号右移 16 位的异或值. 为什么要这样做我们放在后边分析. 这个函数决定了每个键值对在 table 数组中的位置.
2,tableForInt(int cap)
此函数是为了计算大于或等于给定参数的最小的 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;
- }
举个例子, 现在给一个数 19, 调用此函数后返回 32; 给一个数 16, 调用此函数后返回 16, 给一个数 15, 调用此函数后返回 16.
三, put/get 操作
put 和 get 操作是 HashMap 中常用的操作, 使用频率很高, 了解其实现对编写代码很有提升.
- 1,put(K key, V value)
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
从上面的代码中可以看出调用了 putVal 方法, 使用 hash 函数对 key 进行了哈希. putVal 的定义如下,
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- // 如果 HashMap 底层的数组 table 为空, 或者其长度位 0
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;// 调用扩容方法进行扩容, 并返回扩容后的长度
- // 如果要存储的 key 在 table 中的索引处元素 p 为 null, 则说明此 key 所在索引处未产生 hash 冲突
- if ((p = tab[i = (n - 1) & hash]) == null)
- // 生成一个 Node 节点, 放在此 key 的索引处
- tab[i] = newNode(hash, key, value, null);
- else {// 如果此 key 所在的索引处的元素 p 不为 null, 说明已经有其他的 key 的 hash 值和现在 key 的 hash 相同, 产生了 hash 冲突, 两个元素在 table 中的索引一致
- Node<K,V> e; K k;
- // 如果要插入的 key value 和 p 的全部相同, 把 p 赋给 e
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- // 如果不相等, 判断 p 的节点类型, 如果是 TreeNode 类型, 则证明是红黑树的结构, 调用 putTreeVal 进行元素插入
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {// 如果不是 TreeNode 类型, 则说明是链表的结构, 使用链表的方式插入, 找到链表的尾部, 进行插入
- for (int binCount = 0; ; ++binCount) {
- if ((e = p.next) == null) {
- // 在 p 后插入元素
- p.next = newNode(hash, key, value, null);
- // 判断链表的元素数量, 如果大于 8, 则调用 treeifyBin 方法转化为红黑树
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- //e 不为 null, 说明存在一个相同的 key, 则需要进行 value 的替换, 并返回旧值
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- // 如果插入元素后, 元素个数大于 threshold(阀值 = 数组容量 * 负载因子), 进行扩容
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
在上面的代码中做了详细的注释, 下面把过程概括如下
1, 判断 HashMap 底层存储数据的数组 table 是否为 null 或者长度为 0(这里在进行 table 的初始化), 如果是则进行扩容(第一次叫初始化);
2, 如果不是, 取出要插入 key 在数组中索引位置的元素 p, 判断 p 是否为 null, 如果为 null, 则直接插入;
3, 如果 p 不为 null, 判断判断 p 和待插入数据是否相等, 如果相等使用 e 存储 p(后面会判断 e 是否 null, 如果不为 null, 则进行值的替换);
4, 如果不等, 判断 p 的类型是否为 TreeNode, 即是否为红黑树的结构, 如果是则使用红黑树的方式插入;
5, 如果不是 TreeNode, 则使用链表的方式插入;
6, 插入完成后更新元素的个数 size, 如果 size 大于 threshold 进行扩容;
上面是 put 的大体过程, 对于红黑树的插入, 暂不做分析, 下面分析下扩容函数 resize, 其源码如下
- final Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap> 0) {
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr <<1; // double threshold
- }
- else if (oldThr> 0) // initial capacity was placed in threshold
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap <MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- //1, 创建一个新的 Node 数组, 保存数据
- @SuppressWarnings({"rawtypes","unchecked"})
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- table = newTab;
- //2, 如果旧数组不为空, 则要把元素拷贝到新数组
- if (oldTab != null) {
- // 循环旧数组中的元素
- for (int j = 0; j <oldCap; ++j) {
- Node<K,V> e;
- //j 索引处不为 null, 取出给 e
- if ((e = oldTab[j]) != null) {
- // 清空 j 处的元素
- oldTab[j] = null;
- //2.1, 判断 e 是否有后继, 如果没有说明仅有一个 Node 元素, 重新计算 e 中 key 的 hash 值, 得到在新数组中的索引, 进行插入
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- //2.2.1 判断 e 是否为 TreeNode 类型, 如果是使用红黑树的方式
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- //2.2.2 不是红黑树的数据结构, 为链表结构, 进行链表结构的数据拷贝
- else { // preserve order
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- next = e.next;
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
- }
在上面源码中进行了详细注释, 具体步骤可查看注释.
2,get(Object key)
get 函数是使用 key 取出其对于的 value 的过程, 其源码如下
- public V get(Object key) {
- Node<K,V> e;
- return (e = getNode(hash(key), key)) == null ? null : e.value;
- }
使用 getNode 函数取出 Node 元素, 如果 Node 为 null, 则返回 null, 如果不为则返回其 value 属性值, 关于 Node 类的构成稍后分析, 先看 getNode 函数,
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- //1, 判断 table 不为 null 且长度大于 0, 且要取的 key 处索引位置元素不为 null
- if ((tab = table) != null && (n = tab.length)> 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- //2, 如果第一个元素和给定的 key 相等则直接返回第一个元素 first
- if (first.hash == hash && // always check first node
- ((k = first.key) == key || (key != null && key.equals(k))))
- return first;
- if ((e = first.next) != null) {
- //3.1, 如果第一个元素的类型为 TreeNode, 使用红黑树的方式取得 Node
- if (first instanceof TreeNode)
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
- //3.2, 使用链表的方式取得 Node
- do {
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
在上面的代码中进行了详细注释, 可参考.
下面看下 Node 的结构,
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- Node(int hash, K key, V value, Node<K,V> next) {
- this.hash = hash;
- this.key = key;
- this.value = value;
- this.next = next;
- }
Node 作为 HashMap 的静态内部类, 其属性有 hash,key,value,next, 使用这些属性存储数据, 其中 key value 即为我们说的 hashMap 中的键值对, 这里使用 Node 进行封装. next 指向下个 Node 的地址.
以上对 HashMap 做了主要分析, 后面计划对其哈希 hash 函数即红黑树做分析.
有不正之处, 欢迎指正!
来源: https://www.cnblogs.com/teach/p/10922730.html