HashMap源码解析(空间结构和特性、常用方法、扩容机制、链表转化为红黑树的两个条件等)

本文主要是介绍HashMap源码解析(空间结构和特性、常用方法、扩容机制、链表转化为红黑树的两个条件等),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、概念

HashMap继承了AbstractMap,实现了Map,Cloneable,Serializable接口,它是基于散列表实现的,存储的是Key/Value对,底层使用数组+链表+红黑树组成,数组是存储元素并且查找快,链表是为了解决哈希冲突而存在的,红黑树是为了解决链表中查询速度慢而使用的。非线程安全的,如果需要线程安全,可以使用ConcurrentHashMap或者使用Collections.synchronizedMap()包裹HashMap达到线程安全的目的。

2、空间结构

对象序列化的UID,类序列化时会传入一个serialVersionUID。在反序列化时,JVM会把传来的字节流中的serialVersionUID于本地相应实体类的serialVersionUID进行比较。如果相同说明是一致的,可以进行反序列化,否则会出现反序列化版本一致的异常,即是InvalidCastException。

private static final long serialVersionUID = 362498820763181265L;

默认的初始容量大小为1<<4,即1往左移动4位,aka16(aka? 集合中的说唱扛把子?)。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认最大容量为1左移30位,aka 2的30次方。最好是通过构造函数指定,以免多次扩容影响效率。

static final int MAXIMUM_CAPACITY = 1 << 30;

默认的装载因子0.75,即当容量到达默认容量*装载因子时就会扩容。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的链表长度达到8以后,链表就会转化为红黑树(实际上后面还有一个判断条件)。

static final int TREEIFY_THRESHOLD = 8;

默认当红黑树元素个数将为6个时,转换回链表。

static final int UNTREEIFY_THRESHOLD = 6;

默认的当数组长度小于这个值时,会先进行扩容稀释一个链表存储位置,当数组长度大于64且链表长度大于8时,就会转换为红黑树。

static final int MIN_TREEIFY_CAPACITY = 64;

HashMap内部类,用来单个的HashMap数据,包括hash值、key、value和链表的指针,重写了equals方法。

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; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}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;}}

红黑树节点存储结构,分为左节点右节点前节点和父节点,还有一个是否是红色节点或者黑色节点。

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}/*** Returns root of tree containing this node.*/final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}}}

HashMap中存储这些Node<K,V>所使用的数组。使用transient修饰跟ArrayList类似,节省序列和时不必要的空间,同时避免在不同JVM中hashcode方法不同导致桶位置不一样。

transient Node<K,V>[] table;

存储的key/value键值对,使用Set集合存储。

transient Set<Map.Entry<K,V>> entrySet;

整个HashMap中存储的数据的个数。

transient int size;

计数器,前面讲ArrayList和LinkedList都提到过。

transient int modCount;

扩容时的阈值,即装载因子*容量。

int threshold;

实际上的装载因子,没有指定就是默认值。

final float loadFactor;

HashMap的大概结构是这个样子。
在这里插入图片描述

3、常用方法

构造函数

  1. 不传入任何参数,属性全部使用默认的属性。
    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; }
  1. 传入初始容量,覆盖默认的初始容量16。
    public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}
  1. 传入初始容量和装载因子,会检查初始容量和装载因子的正确性,然后覆盖默认的初始容量和装载因子。检查初始容量时会调用tableSizeFor,具体做法就是把当前容量的二进制最高位右边的位都填上1。实际上返回了一个比给定容量大且接近2的幂次方的一个整数。借用一张图来演示过程。
    在这里插入图片描述
    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的幂次方的一个整数。this.threshold = tableSizeFor(initialCapacity);}//返回一个比给定容量大且接近2的幂次方的一个整数。static final int tableSizeFor(int cap) {//减1防止cap刚好是2的幂次方数。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;}
  1. 传入Map集合,如果当前Map集合为空,直接调用tableSizeFor初始化一个容量,如果传入集合的容量大于当前的阈值,就先进行扩容,resize操作后面讲,最后遍历集合,然后放入到当前集合中。
    public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;//讲Map集合存到当前集合中putMapEntries(m, false);}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//集合中元素个数int s = m.size();if (s > 0) {//如果table未初始化,设置threshold。if (table == null) {float ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t > threshold)threshold = tableSrizeFor(t);}else if (s > threshold)resize();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的hash值

  1. 计算key的hashCode的值h。
  2. h^h向右移动16位得到最终的hash值。

进行这一个hash处理的原因是后续计算hash散落在数组的哪个下标上时要与(n-1)相&,由于n-1只有最右边几位是1,其他位全是0。为了让hashcode的高位也参与了后续的散列运算,减少hash冲突。(因为hashcode是一个整体,如果只取最右边的几个数参与运算,那么hashcode的值就不那么客观有效),借一张图来演示。
在这里插入图片描述

    static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

扩容操作

HashMap的扩容操作不仅仅是增加容量和阈值,还涉及到里面元素的迁移。如果是数组中单节点rehash很简单,直接散列运算找到新的索引,如果是链表,因为扩容后n-1右边新增了一位,所以&操作合,需要判断是在当前所有还是在当前索引加上扩容长度的索引。红黑树rehash还要判断树转换为链表和链表转换为树和判断是红节点还是黑节点等操作。

    final Node<K,V>[] resize() {//记录当前的Node数组Node<K,V>[] oldTab = table;//记录当前的Node数组容量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;}//新的容量等于当前容量向左移动1位,即*2。else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//阈值也翻倍newThr = oldThr << 1;}//容量位空,但是阈值不为空。这是使用构造函数传入初始容量的情况。else if (oldThr > 0) //构造函数的初始容量是放在阈值中的,threshold = tableSrizeFor(t);所以新的容量为当前阈值。newCap = oldThr;//容量和阈值都为空,使用系统默认的。else {        newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//如果阈值为空,newCap * loadFactor;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数组用来装扩容后的元素Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {//遍历当前的Node数组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;//如果节点是红黑树,执行split方法进行红黑树的扩容操作,方法跟链表类似,多了维护红黑树和将红黑树转换为链表的操作(em...就不讲解了)else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);			//进行链表的扩容操作,链表扩容时有两种情况,要么在原位置,要么在原位置加上新扩容长度的新位置。因为^(n-1),n翻倍后,n-1右边的位数任然是1,没有改变,最高位新增了1,最高位上^该元素的hash值时时要么是1要么是0。是1的话就扩张了两倍,是0的话位置就不变。else { Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//如果结果为0,那么该元素的索引不需要改变,放到loHead 链表中if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//如果结果为1,那么该元素的索引需要改变,放到hiHead 链表中else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//将原索引的链表归位,且尾指针设为0if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//将新索引的链表归位,且尾指针设为0if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

添加元素
向HashMap中添加元素时候先要进行是否扩容判断,resize()操作前面讲过了,然后再判断插入的地方是无节点还是链表还是红黑树,还要判断添加后链表是否大于8再决定是否转化为红黑树。

	向hashmap中添加元素。public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//初始化桶数组tableNode<K,V>[] tab; Node<K,V> p; int n, i;//table为空或者长度为0,进行扩容。if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//待插入的hash散列的位置是否有值,没有值就插入到数组中if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//待插入位置有值,且key是一样的,则将e节点指向该键值对Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//待插入位置有值,且key不一样的,判断是链表还是红黑树else if (p instanceof TreeNode)//将节点存在红黑树中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//将节点存在链表尾部for (int binCount = 0; ; ++binCount) {//如果链表遍历到尾没有相同的节点,则新生成一个Nodeif ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//放入时候还要判断超过了链表最大长度8,会转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // treeifyBin(tab, hash);break;}//如果链表中有相同的值,就不用新建Node,跳出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//判断要插入的键值对是否存在再hashmap中if (e != null) { V oldValue = e.value;//onlyIfAbsent表示是否仅在oldValue为null的情况下更新键值对的值if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//判断是否需要扩容++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

获取元素
跟插入元素类似,获取key时先计算出key的hash值,分为数组单节点,链表和红黑树的情况查找。

    public V get(Object key) {Node<K,V> e;//通过hash运算获取key的hash值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;//判定三个条件 table不为Null & table的长度大于0 & table指定的索引值不为Nullif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//判定hash值和key是否相同,相同就直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果第一个节点的next不为nullif ((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;}

链表与红黑树转换
当桶数组容量比较小时,键值对节点 hash 的碰撞率可能会比较高,进而导致链表长度较长。这个时候应该优先扩容,而不是立马树化。因为高碰撞率是因为桶数组容量较小引起的,优先扩容可以避免一些列的不必要的树化过程。同时,桶容量较小时,扩容会比较频繁,扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下,最好优先扩容。

	//将普通节点链表转换成红黑树final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//桶数组容量小于64,优先进行扩容而不是树化if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {//定义两个红黑树;分别表示头部节点、尾部节点TreeNode<K,V> hd = null, tl = null;do {//通过循环将单向链表转换为红黑树存储TreeNode<K,V> p = replacementTreeNode(e, null);//若头部节点为Null,则说明该树没有根节点if (tl == null)hd = p;else {//指向父节点p.prev = tl;//指向下一个节点tl.next = p;}tl = p;//若下一个不为Null,则继续遍历} while ((e = e.next) != null);//红黑树转换后,替代原位置上的单项链表if ((tab[index] = hd) != null)//构建红黑树,以头部节点定为根节点hd.treeify(tab);}}//对红黑树进行拆分final void split(HashMap<K, V> map, Node<K, V>[] tab, int index, int bit) {TreeNode<K, V> b = this;TreeNode<K, V> loHead = null, loTail = null;TreeNode<K, V> hiHead = null, hiTail = null;int lc = 0, hc = 0;//红黑树节点仍然保留了 next 引用,故仍可以按链表方式遍历红黑树。下面的循环是对红黑树节点进行分组,与上面类似for (TreeNode<K, V> e = b, next; e != null; e = next) {next = (TreeNode<K, V>) e.next;e.next = null;if ((e.hash & bit) == 0) {if ((e.prev = loTail) == null)loHead = e;elseloTail.next = e;loTail = e;++lc;} else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}if (loHead != null) {// 如果loHead不为空,且链表长度小于等于 6,则将红黑树转成链表if (lc <= UNTREEIFY_THRESHOLD)tab[index] = loHead.untreeify(map);else {tab[index] = loHead;//hiHead == null 时,表明扩容后,所有节点仍在原位置,树结构不变,无需重新树化if (hiHead != null)loHead.treeify(tab);}}//与上面类似if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)tab[index + bit] = hiHead.untreeify(map);else {tab[index + bit] = hiHead;if (loHead != null)hiHead.treeify(tab);}}}

删除操作

    public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}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;//找到key的散列位置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;//如果键的值与链表第一个节点相等,则将node指向该节点if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {//如果是 TreeNode 类型,调用红黑树的查找定位待删除节点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;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}

4、总结

  1. HashMap源码通过数组+链表+红黑树的结构形成,数组对应对hash值进行散列运算的索引位置,链表是为了解决hash冲突后存储key不同hash相同的元素,红黑树是JDK1.8开始为了解决链表查询效率问题。
  2. HashMap触发扩容有两种条件:
    1. HashMap容量超过了当前的阈(yu)值,实在是装不下了会进行扩容。
    2. 链表长度超过8,但是HashMap的总体容量不超过64,此时优先扩容减少hash冲突,也避免形成树后再次扩容对树的拆分。
  3. HashMap是非线程安全的,多线程同时put时候会导致数据不一致。HashTable和ConcurrentHashMap是线程安全的,在多线程情况下ConcurrentHashMap是更优的选择。
  4. HashMap在1.7链表采用头插法避免遍历链表,多线程时扩容可能会发生死循环情况。1.8采用尾插法不会导致死循环,且引入红黑树加快查询效率。
  5. HashMap存储的位置不是一尘不变的,会随着扩容而改变数组内的索引位置。

这篇关于HashMap源码解析(空间结构和特性、常用方法、扩容机制、链表转化为红黑树的两个条件等)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/826944

相关文章

SpringBoot中使用Flux实现流式返回的方法小结

《SpringBoot中使用Flux实现流式返回的方法小结》文章介绍流式返回(StreamingResponse)在SpringBoot中通过Flux实现,优势包括提升用户体验、降低内存消耗、支持长连... 目录背景流式返回的核心概念与优势1. 提升用户体验2. 降低内存消耗3. 支持长连接与实时通信在Sp

Conda虚拟环境的复制和迁移的四种方法实现

《Conda虚拟环境的复制和迁移的四种方法实现》本文主要介绍了Conda虚拟环境的复制和迁移的四种方法实现,包括requirements.txt,environment.yml,conda-pack,... 目录在本机复制Conda虚拟环境相同操作系统之间复制环境方法一:requirements.txt方法

Nginx 重写与重定向配置方法

《Nginx重写与重定向配置方法》Nginx重写与重定向区别:重写修改路径(客户端无感知),重定向跳转新URL(客户端感知),try_files检查文件/目录存在性,return301直接返回永久重... 目录一.try_files指令二.return指令三.rewrite指令区分重写与重定向重写: 请求

MySQL 打开binlog日志的方法及注意事项

《MySQL打开binlog日志的方法及注意事项》本文给大家介绍MySQL打开binlog日志的方法及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录一、默认状态二、如何检查 binlog 状态三、如何开启 binlog3.1 临时开启(重启后失效)

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义

Python中提取文件名扩展名的多种方法实现

《Python中提取文件名扩展名的多种方法实现》在Python编程中,经常会遇到需要从文件名中提取扩展名的场景,Python提供了多种方法来实现这一功能,不同方法适用于不同的场景和需求,包括os.pa... 目录技术背景实现步骤方法一:使用os.path.splitext方法二:使用pathlib模块方法三

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使

CSS place-items: center解析与用法详解

《CSSplace-items:center解析与用法详解》place-items:center;是一个强大的CSS简写属性,用于同时控制网格(Grid)和弹性盒(Flexbox)... place-items: center; 是一个强大的 css 简写属性,用于同时控制 网格(Grid) 和 弹性盒(F

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中,我们经常需要让某个元素占据容器的剩余空间,本文将介绍5种不同的方法来实现这个需求,并分析各种方法的优缺点,感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中,我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求