Connor学Java - HashMap实现原理

Learn && Live

虚度年华浮萍于世，勤学善思至死不渝

前言

Hey，欢迎阅读Connor学Java系列，这个系列记录了我的Java基础知识学习、复盘过程，欢迎各位大佬阅读斧正！原创不易，转载请注明出处：http://t.csdn.cn/UHgc2，话不多说我们马上开始！

1.HashMap的底层实现原理？

JDK7

Entry(key + value)数组 + 链表，默认初始化容量16，默认加载因子0.75

常用变量

// 默认的初始化容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
// 为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
// 若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
// 若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;// Entry数组
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;// map中的实际键值对个数，即数组中元素个数
transient int size;// 每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
// 当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;// 数组扩容阈值
int threshold;// 加载因子
final float loadFactor;					// Entry节点类
static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;
}

构造函数

// 指定容量和加载因子，
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;threshold = initialCapacity;init();
}// 指定容量，加载因子默认0.75
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}// 空参构造，默认容量16，加载因子0.75
public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

JDK8

Node数组 + 链表/红黑树，当链表上的元素个数超过8个并且数组长度超过64时自动转化为红黑树，节点变成树节点，以提高搜索效率到O(logN)；相反，若红黑树上的元素个数减少到6时，就会退化为链表

常用变量

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {// 默认的初始化容量为16，必须是2的n次幂static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 最大容量为 2^30static final int MAXIMUM_CAPACITY = 1 << 30;// 默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。// 为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。// 若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，// 若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。static final float DEFAULT_LOAD_FACTOR = 0.75f;// 刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树static final int TREEIFY_THRESHOLD = 8;// 当红黑树上的元素个数，减少到6个时，就退化为链表static final int UNTREEIFY_THRESHOLD = 6;// 链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。// 这是为了避免，数组扩容和树化阈值之间的冲突。static final int MIN_TREEIFY_CAPACITY = 64;// 存放所有Node节点的数组transient Node<K,V>[] table;// 存放所有的键值对transient Set<Map.Entry<K,V>> entrySet;// map中的实际键值对个数，即数组中元素个数transient int size;// 每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。// 当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。transient int modCount;// 数组扩容阈值int threshold;// 加载因子final float loadFactor;					// 普通单向链表节点类static class Node<K,V> implements Map.Entry<K,V> {// key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置final int hash;final K key;V value;// 指向单链表的下一个节点Node<K,V> next;}// 转化为红黑树的节点类static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {// 当前节点的父节点TreeNode<K,V> parent;  // 左孩子节点TreeNode<K,V> left;// 右孩子节点TreeNode<K,V> right;// 指向前一个节点TreeNode<K,V> prev;    // needed to unlink next upon deletion// 当前节点是红色或者黑色的标识boolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}}
}

构造函数

// 指定容量和加载因子
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;// 这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16// 注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂this.threshold = tableSizeFor(initialCapacity);
}// 仅指定容量，加载因子默认0.75
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}// 空参构造，默认容量16，加载因子0.75
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;
}

tableSizeFor

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;
}

先给出结论：该方法返回的是大于当前传入值cap的最小的2的整数次方的值。下面以14为例说明：

2.HashMap的size为什么必须是2的整数次方？

上面已经从底层源码实现的角度分析了为什么是2的整数次方，下面从这样做的作用角度来进行讨论

（1）当size为2的n次方时，h & (size - 1)就相当于对size取模，且位运算计算速度比直接取模快得多，优化运行速度，且每次扩容都是翻倍

（2）如果size为2的n次方，则size - 1转化为二进制一定是111…的形式，在与h的二进制进行与操作时效率会非常的快，且不浪费空间。如果size不是2的n次方，比如size为15，则size - 1为14，二进制为1110，此时再与h与操作，得到的结果最后一位均为0，则最后一位为1的位置就只能空出来了，空间浪费相当大。此外，数组可以使用的位置比数组长度小了很多，进一步增加了发生冲突的几率，减慢了get、put的效率，造成空间时间上的浪费