一, 什么是 HashMap
Java 中 Map 是用来存储键值对 <key,value> 的汇合类, 也就是哈希表, 而 HashMap 是 Map 的实现类.
具备存储效率高, 查问快的特点, 但不是线程同步的, 依照哈希表的特点,Map 中的 key 是不能反复的.
二, 实现原理
HashMap 采纳数组 + 链表 + 红黑树实现
每个数组空间采纳 Node<key,value> 节点来保留键值对, 在肯定的条件下会采纳 TreeNode<key,value> 保留数据.
三, 根本属性介绍
//The default initial capacity - MUST be a power of two // 默认初始容量 - 必须是 2 的幂. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4//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. // 哈希数组最大容量, 如果构造函数制订了更大的值, 则只应用最大值, 并且大小只能为 2 的幂 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. // 树化阈值: 当一个数组框中的节点数量大于 TREEIFY_THRESHOLD 时该当采纳树来存储, 而不是链表 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 smallest table capacity for which bins may be treeified. // 树化的最小阈值: 只有哈希表中的节点数量大于 64 时, 能力将链表转换为树 static final int MIN_TREEIFY_CAPACITY = 64// 存储节点的哈希数组 transient Node<K, V>[] table// 哈希表中的节点数量 transient int size// 批改 HashMap 的次数, 用于 fail-fast transient int modCount//The next size value at which to resize (capacity * load factor) // 下一次须要扩容的界线 (扩容阈值) int threshold//The load factor for the hash table // 负载系数, 次要用来调节哈希表的填充度 final float loadFactor
四, 构造函数
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);
}五, 罕用办法介绍
/**
* 计算传入值的 hash 值, 用来计算存储的地位
* 将 hashCode 的高 16 位与低 16 位进行异或操作, 这样做的起因次要是为了更好的扩散 hash 散布, 缩小哈希碰撞
* 如果采纳 & 则计算出来的后果会向 0 凑近, 采纳 | 计算的后果会向 1 凑近, 都不能做到均匀分布
* 做异或操作的起因: 加大对哈希码低位的随机性
* String s = "Hello World!";
* Integer.toBinaryString(s.hashCode())
* h.hashCode() = 1100 0110 0011 1100 1011 0110 0001 1101
* h.hashCode() >>> 16 = 0000 0000 0000 0000 1100 0110 0011 1100
* 1100 0110 0011 1100 1011 0110 0001 1101 ^
* 0000 0000 0000 0000 1100 0110 0011 1100
* 1100 0110 0011 1100 1000 0110 0001 1100
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}/**
* 刚办法次要用来计算哈希表的大小, 从下面的属性可知, 哈希表的大小始终为 2 的幂
* 这样做的起因是:
* 1. length 的二进制示意始终为 100...000,length - 1 的二进制为 1111...111
* 2. 长度等于 2 的幂时,hash%length = hash&(length - 1), 但后者比前者效率更高
* 3. 能够保障计算的地位更加的扩散, 如果长度为奇数, 则 length - 1 为偶数, 无论怎么取余或 & 操作, 最终后果都为偶数, 会造成一半空间节约
*/
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;
}获取节点
final Node<K, V> getNode(int hash, Object key) {Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 始终查看首节点是否为要找的节点
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 如果首节点为树形节点, 则须要在红黑树外面查找
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
do {
// 在链表中寻找须要找的节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
// 向链表前面挪动
} while ((e = e.next) != null);
}
}
return null;
}
// 查找节点
final TreeNode<K, V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);
}
// 获取树的根节点
final TreeNode<K, V> root() {for (TreeNode<K, V> r = this, p; ;) {
// 只有根节点的父节点为空
if ((p = r.parent) == null)
return r;
// 向父节点挪动
r = p;
}
}
// 在树中查找
final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
TreeNode<K, V> p = this; // 复制以后节点
do {
int ph, dir; // 以后节点的 hash 值, 方向
K pk; // 以后节点的 key
TreeNode<K, V> pl = p.left, pr = p.right, q; // 以后节点的左孩子, 右孩子, 以及 q 来返回查找到的后果
// 以后节点的 hash 值大于须要找的节点的 hash 值, 须要向左子树挪动
if ((ph = p.hash) > h)
p = pl;
// 以后节点的 hash 值小于须要找的节点的 hash 值, 须要向右子树挪动
else if (ph < h)
p = pr;
// 以后节点的 hash 值雷同, 并且 key 也雷同, 间接返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 左子树为空, 向右子树挪动查找
else if (pl == null)
p = pr;
// 右子树为空, 向左子树挪动判断
else if (pr == null)
p = pl;
// 这一步次要通过 Comparable 比照以后遍历的节点 p 的 key 和要查找的 key 的大小
else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr; // 小于 0 向左遍历, 大于 0 向右遍历
// 这一步示意无奈通过 Comparable 比拟大小, 则从右孩子持续递归遍历查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
// 从右孩子递归遍历后还没有找到, 从左孩子持续查找
p = pl;
} while (p != null);
return null;
}
static int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 : ((Comparable) k).compareTo(x));
}插入节点
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K, V>[] tab;
Node<K, V> p;
int n, i;
/*
* 1, 如果哈希表为空, 则通过 resize() 创立. 所以, 初始化链表的机会为第一次调用 put 函数时
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
* 判断是否存在 hash 抵触:
* 若不存在, 则间接在该数组地位新建节点, 直接插入
* 否则, 代表 hash 抵触, 即以后存储地位已存在节点, 则顺次向下判断
* a. 以后地位的 key 与要存入地位的 key 雷同
* b. 判断需插入的数据结构是否为红黑树或链表
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e; // 待批改的节点
K k;
/*
* a. 判断 table[i] 的元素的 key 是否与需插入的 key 一样, 如果一样间接用新的 value 笼罩旧的 value
*/
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/*
* b. 判断须要插入的是否为红黑树, 如果为红黑树则间接在树中插入或更新键值对
*/
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
/*
* c. 如果是链表, 则间接在链表中更新键值对
* i. 遍历 table[i], 判断 key 是否存在, 采纳 equals 比照以后遍历节点的 key 与待插入数据的 key, 如果雷同则间接用新的 value 笼罩旧 value
* ii. 遍历结束没有上述情况, 则间接在链表尾部插入新的节点
* tips: 新增节点之后, 须要判断链表的长度是否大于 8, 如果是, 须要树化
*/
else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {
// 向链表尾部插入
p.next = newNode(hash, key, value, null);
// 如果以后链表的长度大于 8, 则须要树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果找到了 key 雷同的节点, 则间接退出
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
// 向后挪动节点进行遍历
p = e;
}
}
/*
* 找到须要批改的 node 则间接用新值代替旧值
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 默认实现为空, 为了给 LinkedHashMap 来实现有序 map
afterNodeAccess(e);
return oldValue;
}
}
// 批改次数 +1, 用于 fail-fast
++modCount;
// 节点数量大于阈值, 须要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
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)
// 如果旧的阈值大于 0, 则示意哈希表曾经被初始化了, 则新的容量等于旧的阈值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 初始化
newCap = DEFAULT_INITIAL_CAPACITY;
// 新的阈值等于初始容量 * 加载因子
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阈值等于 0
if (newThr == 0) {
// 计算新的阈值
float ft = (float) newCap * loadFactor;
// 新的容量大于最大值并且新的阈值大于最大值, 则新的阈值为最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
// 赋值新的阈值
threshold = newThr;
// 创立新的哈希表, 赋值新的哈希表
@SuppressWarnings({"all"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
if (oldTab != null) {
// 将每个 bucket 中都挪动到新的 bucket 中
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
// 旧节点置空
oldTab[j] = null;
// 以后节点没有后置节点, 间接计算地位插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if
// 以后节点为树节点, 须要插入树节点并且调节树均衡
(e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else {
// 解决链表节点
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);
// 原索引放在 bucket 中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引 +oldCap 放到 bucket 中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}五, 与之前版本比照
1. hash 值计算形式
//1.7
static final int hash(int h) {h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}从上能够看出 1.7 一共做了 5 次异或操作和 4 次无符号右移操作, 而 1.8 一共做了一次右移和一次异或, 效率比 1.8 高
2. 存储数据结构不同
1.7 采纳数组 + 链表解决哈希抵触, 链表采纳头插法
1.8 采纳数组 + 链表 + 红黑树 解决哈希抵触, 链表采纳尾插法
并且 1.7 的数据结构还会造成循环链表
问题产生的条件:
多线程同时进行 put 时, 如果同时调用了 resize 操作, 可能会导致循环链表产生, 进而会导致前面 get 的时候产生死循环
问题产生的起因:
多线程下进行 put, 本来应该在以后节点的 next 被其余线程移到新数组的空地位上, 而以后节点的 next 指针指向刚放入的节点, 从而造成循环链表.
3. 扩容机制不同
1.7 对原先的每一个节点从新计算插入地位
1.8 只有第一个地位上的节点不须要从新计算插入地位, 其余的都为以后地位 + 旧数组容量