Java集合之一 —— HashMap
本文对HashMap的讲解是基于JDK1.8版本.
// 初始化HashMap容器
Map<String, Integer> map = new HashMap<>();
// 把元素插入到map集合中
map.put("QRB", 22);
// 根据key值获取value值
Integer age = map.get("QRB");
// 输出打印结果 : 22
System.out.println(age);
上面执行过程 : 构造器初始化HashMap容器 --> 把元素插入到map集合中 --> 根据key值获取value值 --> 输出打印结果. 在这一过程的每一步操作,你是否了解过背后的底层原理实现?如果没有,可以跟着本文一起学习HashMap的底层数据结构是怎么样实现的?本文会对Java集合框架中的HashMap的实现原理进行简单了解.
HashMap : 简单的自我介绍
HashMap 的数据结构是基于 数组 + 链表 + 红黑树 组成,而Entry<K,V>对象是HashMap的基本存储单位,Entry<K,V>对象是一种key-value键值对映射的数据结构对象.
HashMap 维护着一个内部静态类 Node<K,V> 节点, 它是Entry<K,V>对象的实现类.
也就是说,HashMap集合存储着许多个 <Node<K,V> 节点,那这些 Node<K,V> 节点 跟 数组、链表、红黑树 有何联系的呢?
HashMap默认会初始化一个长度为16的数组(table,16个桶),根据key值的hashcode值进行哈希算法计算出一个hash值,hash值与数组的长度进行位运算计算出数组的索引值(桶的位置,0-15,哈希算法与数组长度进行位运算计算出来的数组索引值总是在数组长度的范围内),并且所有的桶默认指向一个NULL;每个桶装着要么是指向一个NULL、要么是链表、要么是一颗红黑树.链表是解决了哈希冲突,红黑树解决了链表长度过长时遍历查询效率过低的问题(下面有解释什么是哈希冲突).
假如向一个桶内插入元素,会出现三种情况 :
- 第一种情况就是如果这个桶里面指向的是一个NULL(所有的桶默认指向一个NULL,即默认桶内没有元素),则直接把当前的Node<K,V>节点添加到这个桶里面;
- 第二种情况就是当前桶内装的是一条链表(即存在元素),则需要进行遍历判断是否存在同时满足 key的hash值是否相等 且 通过==、equals()的比较进行判断key是否为相同对象 的条件,如果满足则说明是同一个key对象,替换当前插入的value值,反之则插入到链尾中;
- 第三种情况就是当前桶内的装的是一棵红黑树(即存在元素),把元素插入到红黑树中,同样也会判断是否存在同时满足 key的hash值是否相等 且 通过==、equals()的比较进行判断key是否同一个对象 的条件.
// Node<K,V> 节点 实现类
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;
}
public final K getKey() { return key; }
// 还有更多的方法
...
...
}
HashMap存储结构图
【PS : HashMap转变为红黑树的条件是 : 当出现链表长度>=8 且 数组容量>=64 时 才会把链表转红黑树,而上图画了一颗红黑树,而数组只有16个,由于幅度问题,所以图中暂时忽略这个问题】
哈希算法
// 是一个哈希函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
哈希函数(hash(Object key))计算出哈希值,通过(n - 1) & hash(哈希值)计算出桶的位置(数组的索引值),从代码可以看出是哈希算法根据key的hashCode值的高16位和低16位去进行异或运算而计算出hash值.
什么是哈希冲突和红黑树解决了什么?
我们知道默认初始化下是16个桶(table),现在你需要插入12个元素,最理想状态下是12个元素占用了12个桶的位置,但是没有什么事是十全十美的,如果两个不同的元素(不同的key),通过哈希算法计算出hash值,并且通过hash值与数组长度进行位运算计算出数组的索引值相同,也就是说,要装进的桶已经存在元素了,这就是所谓的 哈希冲突 .减少哈希冲突是HashMap提升性能的有效手段之一,现在知道哈希算法多么重要了吧,而好的哈希算法会尽可能地保证 计算简单和散列地址分布均匀.但是数组是一种固定长度的存储数据结构,再好的哈希算法也会遇到哈希冲突;哈希冲突的解决方法有很多 : HashMap采用的是 链地址法: 链表法.
链表的作用就是解决了哈希冲突,而链表对于插入和删除操作,只需要移动指针就可以,不像数组那样要拷贝位置,数据量大的时候极大的影响了效率.而对于遍历操作的时间复杂度为O(n),当链表的长度过长的时候则会影响查询效率.这个时候红黑树就出现了,红黑树在进行添加,删除,查找等操作,性能十分之高.那什么时候使用红黑树呢?
HashMap在链表长度为8且数组的容量大于64(MIN_TREEIFY_CAPACITY)的时候则转化为红黑树,当链表长度为8且数组的容量小于64(MIN_TREEIFY_CAPACITY)的时候,则扩容,扩容的时候原数组中的数据则重新计算其在新数组中的位置.
全局变量
几个核心全局变量 :
// 默认初始化数组为 16 个桶
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 负载因子 默认值 : 默认是 0.75 ,该变量跟扩容有关系
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表长度为 8 的时候 且 数组的容量大于64的时候则转化为红黑树
// 链表长度为 8 的时候 且 数组的容量小于64的时候则扩容,
// 扩容的时候原数组中的数据必须重新计算其在新数组中的位置
// 扩容机制 : 数组长度变为原来的两倍,也就是 16 * 2 = 32;
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
// 底层是个数组
transient Node<K,V>[] table;
// 实际存储的key-value键值对的个数
transient int size;
// 负载因子,代表了table的填充度有多少,默认是0.75
final float loadFactor;
// 阈值: HashMap在进行扩容时需要参考这个阈值 threshold,
// 一般为 threshold = capacity*loadFactory
// capacity为桶的数量(默认16个),loadFactory为负载因子(默认0.75),
// 例如 threshold = 16 * 0.75 = 12;
// 这个12代表什么呢:当数组中存储的Node数量达到12个的时候则需要扩容了.
(默认桶为16个,说明添加13个Node的时候就需要扩容了,
但是再极端的情况下,添加的元素8个在同一个桶中,需要转化为红黑树,
而转化红黑树发现当前的桶的数量是16个,小于64个,不需要转红黑树,走扩容,
这个时候就扩容为32个桶,threshold边为24了,
这种情况还没达到13个Node就扩容了,理想状态下的13个Node再扩容,
这样的做法可以减少哈希冲突.)
int threshold;
构造器(4个)
// 1、initialCapacity : 初始化多少个桶,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);
}
// 2、initialCapacity : 初始化多少个桶,默认 负载因子为 0.75;
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 3、无参构造器,默认16个桶、负载因子0.75,大部分情况下使用无参构造器就行了
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 4、m参数 : 一个Map对象 (相对应把两个Map合并起来)
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将m的所有元素存入本HashMap实例中,这个方法讲完put方法后再讲
putMapEntries(m, false);
}
添加元素
现在我们选择第3种无参构造器初始化容器的方式,当put第一个元素的时候才是真正的完成初始化.每当我们向容器put元素,HashMap做了什么操作?
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
我们经常调用的put方法,其实核心是putVal()方法,全部总共有五个参数,重点只关心前三个参数就行: 三个参数分别代表 哈希值,key,value;
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;
2、// (n - 1) & hash] 计算出桶的位置,如果当前桶不存在元素,则不是哈希冲突,直接把元素装进桶里.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
3、// 桶里存在元素,也就是哈希冲突了
Node<K,V> e; K k;
4、// 判断第一个元素是否为相同的key
// 同时满足
// hash值相等(跟hashcode值有关) 且
// key值相等(==和equals方法) 条件,
// 则说明该桶里存在同一个key了(相同对象)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
5、// 当前桶里面是一棵红黑树,则把元素put进红黑树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
6、// 桶里的第一个元素 不是相同的key 或者 也不是一棵红黑树,则是一条链表
else {
// 链表循环判断
for (int binCount = 0; ; ++binCount) {
7、// 判断 链表的下一节点是null时 ,表示是链表的尾结点了,直接put进去
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
8、// 当循环达到8次时,说明链表的长度位8了,要转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
9、// 当下一结点不是null,说明不是最后一个结点,需要判断一下是不是相同key
// 如果存在相同的key,则break,即跳出循环;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
10、// 如果e为null的话 上面已经直接生成一个新的节点添加桶里了,
// 所以这里如果e不为null,说明出现桶里面相同的key对象,直接替换value值就好了.
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 这个参数看懂了吗,就是说存在相同的key你可以不更改
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 出现相同的key 返回被替换的value值
return oldValue;
}
}
++modCount;
11、// threshold 阈值,当容器里的元素数量大于这个阈值的时候则需要扩容 默认是 16*0.75=12
// size达到13则扩容,扩容的时候原数组中的数据必须重新计算其在新数组中的位置.
if (++size > threshold)
resize(); // 扩容方法
afterNodeInsertion(evict);
// 返回null 说明是成功插入数据,而不是出现同一个key对象
return null;
}
我们重新整理一下put方法的执行代码思路:
- 1、判断数组(table)是否为空,如果是则扩容(数组长度扩大到原来的两倍).
- 2、计算出数组索引值的位置,并且判断是否为null,如果是为null,则直接插入到桶里;
- 3-9、如果不为null,则可能是一条链表或者一棵红黑树(哈希冲突),出现哈希冲突,首先必须判断key是否同一个对象(根据hash值和 ==、equlas方法判断),如果存在相同的key则把这个对象赋值给 e,为什么赋值给e : 第10步判断e不为null的时候则说明存在相同的key,替换value就好了.
- 10、如果e为null的话,上面已经直接生成一个新的节点添加桶里了(例如第2、7步),所以这里如果e不为null,说明出现桶里面相同的key对象,直接替换value值就好了.
- 11、size达到13则扩容,扩容的时候原数组中的数据必须重新计算其在新数组中的位置.
- 讲到这里,我们大致知道HashMap是如何把元素存进容器里了.
弄清楚putVal()方法,putMapEntries()方法就容易多了.
putMapEntries(m, false)
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
1、// 获取 m 中元素的个数
int s = m.size();
2、// s大于0,说明m实例中存在元素需要合并到本例的HashMap中
if (s > 0) {
3、// 当前的table还没初始化,则需要初始化一些数组容量、阈值
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);
}
4、// 之前table有过初始化了,如果m的元素个数大于threshold,则需要扩容
else if (s > threshold)
resize();
5、// 把所有的元素put进当前的HashMao容器中,调用的putVal()
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);
}
}
}
根据key获取value
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
核心方法是getNode(int hash, Object key),其实就是根据 { key的hash值找到数组索引位置 且 key是否相等(==、equals方法) } 这个条件来获取value.
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
1、// 老规矩 获取桶的位置(tab[(n - 1) & hash]))
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
2、// 判断key是否同一个对象
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
3、// 哈希冲突 要么是链表要么是红黑树
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);
}
}
4、// 没有找到 返回null
return null;
}
疑问
1.为什么HashMap的数组初始化长度总是2的幂?
2.对于可变对象作为key对象,为什么要重写key对象的equals方法和hashCode方法?
3.HashMap的扩容机制(resize()方法)是怎么样的呢?
4.HashMap的哈希算法.
结束语
本文只是简单的介绍了HashMap的put方法、get方法和数据存储结构,HashMap还提供了包括删除、查询、包含等很多方法,只要理解了基本的数据结构思路,其他方法慢慢的就可以看懂了.HashMap还有很多细节的东西值得我们深入理解,下篇文章再继续一起探讨.
- 原创不易
- 希望看完这篇文章的你有所收获!
相关参考资料
- JDK1.8