HashMap-简介
HashMap 主要用来存放键值对,它基于哈希表的 Map 接口实现,是常用的 Java 集合之一,是非线程安全的。
HashMap
可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个
JDK1.8 之前 HashMap
由 数组+链表 组成的,数组是 HashMap
的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。 JDK1.8 以后的 HashMap
在解决哈希冲突时有了较大的变化,当链表长度大于等于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
HashMap
默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。并且, HashMap
总是使用 2 的幂作为哈希表的大小。
HashMap-数据结构
这是 HashMap 类中的一个成员变量,它是一个存储桶数组。table 数组用于存储键值对的实际数据。
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
}
这是 HashMap 内部定义的静态嵌套类 Node,它实现了 Map.Entry 接口。每个 Node 对象表示 HashMap 中的一个键值对,它包含键、值以及指向下一个节点的引用,从结构上来看,HashMap中链表结构与LinkedList相似。
测试示例
public static void main(String[] args) {
HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("KING",100);
}
图解HashMap-put方法
根据key获取hash值
Hash是将Key转换为一个短的、定长的值去替代源Key作为索引,以更快的查询。
通过hash方法得到"KING"对应的hash值为2306996。
计算方式:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
通过hash值得到对应的桶的Index
计算方式:
(n - 1) & hash
如此,当调用put方法将元素添加到HashMap时,“KING”、100便被放入到Index为4的Node中。
由于index为4的Node节点并无除"KING"其他元素,所以它的下一个节点信息为null。用同样的方法将"CLARK"
,90放入HashMap。
不同的Key得到的Index值相同的情况
接下来我们把Key:“BLAKE”,value:10放入该Map,得到key值的hash为63281940:
根据63281940计算Index结果为4:
由于"KING"对应的Node节点也为4,Key:"BLAKE"计算出的Index同样为4,不同的key通过哈希算法(n - 1) & hash计算出的索引位置相同时即为哈希冲突,HashMap在发生哈希冲突时,会将具有相同哈希码的键值对存储在同一个桶(bucket)中,通过链表或者在元素数量较多时转换为红黑树来处理冲突。如此,HashMap的结构将变为:
图解HashMap-get方法
HashMap的get方法用于获取指定键对应的值。
以获取"KING"的值为例:
Integer integer = hashMap.get("KING");
先计算出key的hash值,根据key值和key的hash值去获取Node信息。
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) {
// 数组元素相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中可能存在不止一个节点
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
先来明确一下各个变量的意义:
- key:要查询的指定key
- table:当前HashMap哈希表实际数据存储,用于存储节点的桶
- first:要查询的指定key匹配到某个桶的第一个节点
- e:临时节点,用于遍历桶中的节点链表或树结构。在这段代码中,e 用于遍历桶中的节点以查找匹配的键值对。
- n:这是一个整数,表示哈希表的长度,即桶的数量。
- k:这是一个键对象,表示 first 节点的键,即指定key计算后hash值对应桶的第一个节点的键。
链表
把上文源码链表部分翻译成一张图片:
图片局部放大:
当同一个Node<Key,Value>中存在多个元素时,开始根据key值和key的hash值在链表中匹配对应的value值。
红黑树
由于在链表中获取对应Value值的过程是通过for循环实现的,其时间复杂度为O(n),当链表过长时,查询时间变长,JDK使用红黑树解决了该问题,当链表长度大于8时,链表进行树化。
红黑树结构
如果存储桶中的元素是一个红黑树,则通过红黑树的查找算法,在红黑树中查找具有相同哈希码并且键相等的节点。
后续内容文章持续更新中…
近期发布。
关于我
👋🏻你好,我是Debug.c。微信公众号:种棵代码技术树 的维护者,一个跨专业自学Java,对技术保持热爱的bug猿,同样也是在某二线城市打拼四年余的Java Coder。
🏆在掘金、CSDN、公众号我将分享我最近学习的内容、踩过的坑以及自己对技术的理解。
📞如果您对我感兴趣,请联系我。
若有收获,就点个赞吧,喜欢原图请私信我。