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

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件,方便以后开发的时候查找!!! 函数工具: Lodash 页面固定: stickUp、jQuery.Pin 轮播: unslider、swiper 开关: switch 复选框: icheck 气泡: grumble 隐藏元素: Headroom

HDFS—集群扩容及缩容

白名单:表示在白名单的主机IP地址可以,用来存储数据。 配置白名单步骤如下: 1)在NameNode节点的/opt/module/hadoop-3.1.4/etc/hadoop目录下分别创建whitelist 和blacklist文件 (1)创建白名单 [lytfly@hadoop102 hadoop]$ vim whitelist 在whitelist中添加如下主机名称,假如集群正常工作的节

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

常用的jdk下载地址

jdk下载地址 安装方式可以看之前的博客: mac安装jdk oracle 版本:https://www.oracle.com/java/technologies/downloads/ Eclipse Temurin版本:https://adoptium.net/zh-CN/temurin/releases/ 阿里版本: github:https://github.com/

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi