HashMap:基于哈希表的 Map 接口的实现,此实现提供所有可选的映射操作,并允许使用 null 值和 null 键
1.前言
上一章讲述了基于链表的List集合LinkedList,它可以实现高效的实现增删操作,存储时不限制于连续的内存空间.这一章讲解增删高效,遍历高效的集合HashMap
2.目录
目录
3.HashMap源码分析
3.1.HashMap的数据结构
HashMap的底层是基于数组和链表(1.8引入红黑树,大数据场景)实现的,它通过计算散列码来决定存储的位置,达到查询高效.hsah值得计算是通过key的hashcode,只要hashCode相同,计算出来的hash值就一样,这就出现了所谓的hash冲突,HashMap是通过链表来解决hash冲突的,JDK7后,链表容量超过8,转化为红黑树
拉链法.png
static class Node<K,V> implements Map.Entry<K,V> {
//元素的哈希值 决定在table的位置
final int hash;
final K key;
V value;
//记录下一个元素结点(单链表结构,用于解决hash冲突)
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//key 的 hashCode 异或 value的 hashCode
//运算作用就是将2个hashCode的二进制中，同一位置相同的值为0，不同的为 1
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断两个Entry是否相等
// 若两个Entry的“key”和“value”都相等，则返回true。
// 否则，返回false
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
HashMap内存结构
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; // 颜色，root 节点为黑色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...
}
3.2.1.实现接口和属性
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//序列化因子
private static final long serialVersionUID = 362498820763181265L;
//初始化容量16 必须是2的倍数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大所能容纳的key-value 个数
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转化为红黑树的阈值,该值必须大于2,并且应该至少为8，
static final int TREEIFY_THRESHOLD = 8;
//当执行resize操作时,当桶中bin的数量少于UNTREEIFY_THRESHOLD时使用链表来代替树,默认值是6
static final int UNTREEIFY_THRESHOLD = 6;
//当链表中的元素等于8个进行创建树的时候,如果当前桶的数量小于64,则进行扩容重新分配 hash 值
static final int MIN_TREEIFY_CAPACITY = 64;
//存储数据的Node数组,长度是2的幂,充当哈希表的作用
transient Node<K,V>[] table;
//key和value的set集合
transient Set<Map.Entry<K,V>> entrySet;
//map中保存的键值对的数量
transient int size;
//被修改的次数
transient int modCount;
//容量乘以装在因子所得结果,如果key-value的数量等于该值,则调用resize方法,扩大容量,同时修改threshold的值。
int threshold;
//装载因子 衡量HashMap满的程度
final float loadFactor;
}
- Cloneable:方便集合数据的复制
- Serializable:可序列化传输集合数据
3.2.2.初始化
HashMap(int initialCapacity, float loadFactor):使用指定的初始容量和默认的加载因子初始化HashMap,这里需要注意的是,并不是你指定的初始容量是多少那么初始化之后的HashMap的容量就是多大,例如new HashMap(20,0.8),那么实际的初始化容量是32,因为tableSizeFor()方法会严格要求把初始化的容量是以2的次方数成长只能是16、32、64、128...
public HashMap() {
//使用默认的加载因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
//设置初始化容量,使用0.75作为默认的加载因子
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
//>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
//|是按位或操作，就是只要有一个1就是1，两个都是0才是0
//二进制高位至多含2个1(使最高位的1,右移做非,变成2个1)
n |= n >>> 1;
//二进制高位至多含4个1
n |= n >>> 2;
//二进制高位至多含8个1
n |= n >>> 4;
//二进制高位至多含16个1
n |= n >>> 8;
//二进制高位至多含32个1 int4个字节32位
n |= n >>> 16;
//+1 变成2的倍数 呼应cap-1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
深拷贝一份HashMap对象,使用0.75作为默认的加载因子
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) {
//没有初始化存放<key,value>的Node 构造器初始化
if (table == null) { // pre-size
//获取最大容量 向下取整 所以+1
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//大于阈值 重新计算
if (t > threshold)
//重新计算阈值 且为2的倍数
threshold = tableSizeFor(t);
}
//已经初始化
else if (s > threshold)
//扩容 数组的扩容
resize();
//循环里的putVal可能也会触发resize
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//添加entry
putVal(hash(key), key, value, false, evict);
}
}
}
3.2.3.扩容机制
jdk1.8 resize()方法:扩容机制,较复杂,简单理解,jdk1.7原理一致,table增长为2的倍数,且为原容量的2倍,元素的hash值以及位置可能发生变化
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;
}
//没超过最大值，就扩充为原来的2倍
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
// 当第一次调用resize的时候会执行这个代码,初始化table容量以及阈值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//将以前table中的值copy到新的table中去
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
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 { // preserve order
// 链表优化重hash的代码块
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;
}
// 原索引+oldCap
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;
}
jdk1.7 resize(int newCapacity)方法:扩容机制,数组table扩容,思路清晰些
//传入新的容量
void resize(int newCapacity) {
//引用扩容前的Entry数组
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//扩容前的数组大小如果已经达到最大(2^30)了
if (oldCapacity == MAXIMUM_CAPACITY) {
//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return;
}
//初始化一个新的Entry数组
Entry[] newTable = new Entry[newCapacity];
//！！将数据转移到新的Entry数组里
transfer(newTable);
//HashMap的table属性引用新的Entry数组
table = newTable;
//修改阈值
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
//src引用了旧的Entry数组
Entry[] src = table;
int newCapacity = newTable.length;
//遍历旧的Entry数组
for (int j = 0; j < src.length; j++) {
//取得旧Entry数组的每个元素
Entry<K,V> e = src[j];
if (e != null) {
//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
src[j] = null;
do {
Entry<K,V> next = e.next;
//！！重新计算每个元素在数组中的位置
int i = indexFor(e.hash, newCapacity);
//标记[i]
e.next = newTable[I];
//将元素放在数组上
newTable[i] = e;
//访问下一个Entry链上的元素
e = next;
} while (e != null);
}
}
}
static int indexFor(int h, int length) {
//与(11...)运算 结果取决于h 使冲突更少
return h & (length - 1);
}
3.2.4.put增添元素方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//扰动函数计算hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, I;
//如果是第一次调用,则会调用resize 初始化table 以及threshold
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果对应的索引没有Node,则新建Node放到table里面。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果hash值与已存在的hash相等，并且key相等，则准备更新对应Node的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果hash值一致,但是key不一致,那么将新的key-value添加到已有的Node的最后面
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 当某个节点的链表长度大于8,则扩大table 数组的长度或者将当前节点链表变成树节点链表
//未初始化或为最小容量情况下扩容,其它转红黑树,提升索引效率
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//hash值和key值相等的情况下，更新value值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回旧的value
return oldValue;
}
}
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
来自美团技术文章
3.2.5.get方法获取元素
get(Object key):根据key的hash值和key，可以唯一确定一个value
public V get(Object key) {
Node<K,V> e;
//存在返回值,不存在返回空
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
///如果索引到的第一个Node,key 和 hash值都和传递进来的参数相等，则返回该Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果索引到的第一个Node 不符合要求,循环变量它的下一个节点
if ((e = first.next) != null) {
//结点是tree类型,查找树节点
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;
}
3.2.6.containsKey方法
containsKey(Object key)方法:getNode方法实现的,如果key对应的value不存在则返回false
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
3.2.7.containsValue方法
containsValue(Object value)方法:遍历对象所有的value,遇到value相等的,则返回true
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//遍历table
for (int i = 0; i < tab.length; ++i) {
//遍历结点链表
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//都为null 或者equals相等
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
3.2.8.remove方法
remove(Object key)方法:通过key(或者包含值)删除元素,会涉及到链表位置的重新对接
public V remove(Object key) {
Node<K,V> e;
//通过key移除时matchValue传false value不需要传
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* @param key的hash值
* @param key值
* @param 需要remove 的value，
* @param 为true时候，当value相等的时候才remove
* @param 如果为false 的时候，不会移动其他节点。
* @return 返回被移除的Node，或者返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//如果定位到的第一个元素符合条件，则跳出if else
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//同上面get(Object key的思想)
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//移除符合要求的节点，将链表重新连接起来
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//红黑树移除结点
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
//删除的是链表的第一个结点
tab[index] = node.next;
else
//此时p为链表的前一个结点
p.next = node.next;
++modCount;
//当前的key-value 对数减一
--size;
afterNodeRemoval(node);
//返回删除的结点
return node;
}
}
//不存在返回null
return null;
}
3.2.9.clear方法
clear()方法:将每个数组元素置空
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
//置空链表也随之置空
tab[i] = null;
}
}
4.总结
本章主要讲解删除高效,查找高效的HashMap,它是ArrayList和LinkedList的一种折中实现,其数据存储,扩容和冲突解决的思想都值得我们我们好好理解和学习,它是面试的高频题,需要我们花些时间理解是原理的实现.下章将讲解几种在特殊场景下高效的数据结构
