dtcms文档 properties 物联网项目 uwp webforms vue论坛 bootstrap后台模板 sql数据库教学视频 seo教程下载 jquery的点击事件 虚拟机重启命令 cmd清空命令 mysql 连接 python异常 python编程工具 python搭建网站 java教程 java时间 java实现 java数据库 randomjava java操作数据库 java接口实例 linux内核编程 rewritebase atq corelpainter 简体中文语言包 微信客户管理系统 数科阅读器 怎么设置迅雷为默认下载器 流水账软件 电脑cmd命令大全 语音分析软件 苹果手机验机软件 彻底卸载mysql execryptor linux格式化硬盘 dll注入器 联发科p22
当前位置: 首页 > 学习教程  > 编程语言

Java集合(3):小白也能看懂的HashMap图解、底层原理与Hash算法

2021/2/13 20:22:38 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

前面分析了Java集合中ArrayList和LinkedList的源码,这次说一下另一个常用的集合:HashMap。 一 、HashMap的特点 (1)属于Map下的集合,用KV键值对存储元素,元素是无序的,key不允许重复&#xff…

前面分析了Java集合中ArrayList和LinkedList的源码,这次说一下另一个常用的集合:HashMap。

一 、HashMap的特点

(1)属于Map下的集合,用KV键值对存储元素,元素是无序的,key不允许重复,value允许重复,允许存储null。
(2)底层数据结构是哈希表,实现是链表+数组,JDK 8 后又加了红黑树。
(3)多线程环境下不安全,解决方法:

  • 使用Hashtable;
  • 调用Collections类的synchronizedMap方法;
  • 使用juc包下的ConcurrentHashMap类代替(此方法效率最高)。

二、初识底层结构

特点中提到,HashMap底层结构为数组+链表+红黑树,先看一下大体的结构图:
在这里插入图片描述
简单的说,当一个数据要添加到HashMap中时,首先根据key找到数组的位置,如果数组已经有数据了则与前面的数据形成链表,如果链表过长则形成红黑树。
那么这个数组到底多大?链表多长时会形成红黑树?这一系列问题,我们可以在HashMap的属性中找到答案。

三、属性

HashMap中定义了六个常量,用来控制它的底层结构。
(1)static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
默认初始容容量等于16,也就是数组(也习惯称为为桶)的大小为16,这里既然有默认容量,也就是说数组的大小是可以改变的。此外,数组的容量必须是2的幂,至于原因会在后面解释。
(2)static final int MAXIMUM_CAPACITY = 1 << 30;
最大容量,也是说的数组长度(桶的个数)。为什么是1 << 30?因为int类型的数据能存下最大的2的幂就是2的30次方。
(3)static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认的负载系数。前面说到数组的大小是会变化的,那么什么时候数组会变化呢?数组中已经存储的容量占总容量的负载系数倍,数组就会扩容。例如默认初始容量是16,默认负载系数为0.75,则当数组中存储元素超过16*0.75=12时,数组就会扩容。
(4)static final int TREEIFY_THRESHOLD = 8;
树形化的阈值为8。当一个链表上存储元素的个数多于8时链表就会开始转换为红黑树存储。
(5)static final int UNTREEIFY_THRESHOLD = 6;
取消树形化的阈值为6。当一个红黑树中的元素少于6时,红黑树就会转化为链表。
(6)static final int MIN_TREEIFY_CAPACITY = 64;
最小树形化阈值为64。这个参数的意思就是说,如果桶的个数小于64,那么即使链表长度大于8,也不会化为红黑树,而是会先采取扩容。

四、底层结构详解

看完了HashMap的各个属性,我们就可以明确HashMap底层结构的变化了:
1.如果构造方法采用默认的构造方法,会创建一个容量为16的数组。添加数据会在数组中添加,如果数组中有数,则在后面形成链表。
在这里插入图片描述

2.继续添加数据,有两种情况会导致数组扩容

a.数组中存储元素的格子(桶)的数量大于数组容量*负载系数
在这里插入图片描述

b.如果数组其中一个格子的链表长度大于8
在这里插入图片描述

数组的扩容是按照扩容两倍的规则扩容的,扩容完后已有的数据会重新计算在HashMap中的位置。
3.扩容后的数组,如果容量大于64,继续添加数据,如果数组中存储元素的格子(桶)的数量大于数组容量*负载系数会继续扩容,但是如果链表长度大于8,链表转变为红黑树。
在这里插入图片描述
如果因为删除数据或扩容导致红黑树的元素小于6,红黑树会变回链表。关于添加数据、扩容等源码会在后面的文章详细介绍。

五、定位算法

看到这里,可能会疑惑,数据是如何选择要存到数组的哪个位置的?比较容易想到的是计算出数据key的hash值,与数组的容量进行取模(%)运算,然后得出位置。

其实HashMap也是这么做的,但是由于计算机的模运算消耗较大,HashMap采用了位与运算(&)来代替,用的是以下公式:hash % N = hash & N-1 。比如在HashMap中添加元素的方法中有段代码为:

 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

其中tab[]就是数组,i = (n - 1) & hash就是计算出的位置。

此外,在JDK1.8中还优化了hash算法,当数组容量太小时(例如16),参与位与运算(&)的hash值的高位并不会参加运算,决定存储位置只会取决于hash值的低四位,大大增大了hash冲突(多个数据进行计算存储的位置相同)的概率。优化的hash算法如下:

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

看代码可知是将hash值右移16位并进行异或(^)计算,这样高位也能参与后面的计算了。

综上,定位算法的计算过程如下:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_700465.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?