[Java]散列表的数据结构以及对象在JVM堆中的存储过程

简介: [Java]散列表的数据结构以及对象在JVM堆中的存储过程

1、什么是“散列表”?

大家先看张图,这是我理解的“散列表”底层数据结构图。

我先大致说说 JVM 的内存结构。

JVM内存结构主要由堆、栈和方法区组成。栈主要用于存储基本数据类型变量和引用、以及引用类型变量引用等;堆主要用于存储对象和数组;方法区主要用于存储类信息和常量。

这里主要讲的是“堆”。

对象在堆中不是随意存储的,而是通过一种数据结构散列表 \color{green}{散列表}散列表进行存储(存储于散列表中)。何为散列表?它的数据结构大致如上图所示,纵向是数组,横向是链表(有些资料中也将“链表”称之为“桶” \color{green}{“桶”}),数组的每一个节点都是链表的表头

Hash系列(如:java.util.Hashtablejava.util.HashMap)的数据结构就是散列表,下文以 Hashtable 为例。

P S PSPS:散列表的结构为何这样设计?又为何要将对象采用散列表结构进行存储?往下看。

2、关于对象存储过程

2.1 加载过程

关于创建对象方法,可参考博文《Java知识点锦集》的第3.2项。

对象创建完成,为对象在 Hashtable 中选择一个存储位置,需要使用对象的内存地址在 Hashtable 中进行检索。

  • 第一步:将对象内存地址(十六进制)转化成十进制,再通过h a s h 算法 hash 算法hash算法,得到一个整型数字,即hashcode
  • 第二步:通过某种运算,得出与此对象具有相同 hashcode 的“桶”的位置(索引);(关于“运算”,见本文末)
  • 第三步:在确定“桶”后,检索,比较entry中的key,找到对象合适的存储位置后插入“桶”。

补充说明: \color{purple}{补充说明:}补充说明:

Hashtable 是一种数据结构,可以存储任何类型数据,对象只是其一。

如果 Hashtable 存储的是对象,则key存储的是内存地址,value存储的是对象。

若 Hashtable 中存储的是对象,则加载过程就是检索对象应存储位置后直接插入对象,不存在覆盖现象。

如:Hashtable,映射(有些资料也称之为“条目” \color{green}{“条目”}条目)是Entry。由于key可能重复,故可能会覆盖。

扩展一点: \color{brown}{扩展一点:}扩展一点:

大家可能会疑惑:使用Map时,打印key,显示的是 String,并不是你说的内存地址啊?

因为,如果key的类型是 String,如:映射Map.Entry = {"name", [对象]},其底层(JVM中)是先在方法区的字符串常量池中创建一个字符串常量"name",此常量对应一个内存地址,然后将此内存地址经过上文中的“加载过程”作为key存储进Map中。当我们输出key时,在底层会通过其存储的内存地址,去字符串常量池中查找,从而输出"name"

2.2 注意事项

  1. h a s h c o d e \color{green}{hashcode}hashcode的作用主要是用于在数组中,定位与对象具有相同 hashcode 的“桶”的表头位置(索引), hashcode 本身并不存储于 Hashtable。
  2. 散列表的纵向(数组)和横向(链表)的每个节点的数据类型都是entry
    注:Hashtable 类中节点的数据类型是Map.Entry
  3. 两个不同对象的hashcode可能相同,同一个“桶”中的所有对象的hashcode都相同。
  4. 散列表的纵向设计为数组是因为数组便于检索(定位具有相同hashcode的“桶”效率高),横向设计为链表是因为链表便于修改(插入、修改效率高)。
  5. “桶”是双向链表 \color{red}{“桶”是双向链表}是双向链表.。两头都可以是表头,这样设计是为了提高检索对象的速度。
  6. “桶”的数据结构不是一成不变的。当entry个数达到一定临界值时,“桶”会重构,从而提高检索对象性能。
    重构规则: \color{blue}{重构规则:}重构规则:entry个数超过8个时,重构为红黑树 \color{green}{红黑树}红黑树(大家以二叉树的结构理解就行);当小于等于6时,重构回链表。

3、Hashtable 扩容机制

先说定义:

“扩容”指扩大 Hashtable 的容量(即“桶”的个数),上面第6点中提及的“重构”指修改“桶”的数据结构,两者不要混淆。

3.1 扩容机制是什么?

Hashtable 何时扩容?这里涉及一个概念——加载因子 \color{green}{加载因子}加载因子(又名“负载因子”)。

  • 每个“桶”都有一个初始entry容纳个数。
  • “加载因子”指填满(“桶”中entry个数达到初始容纳个数)的“桶”的个数占 Hashtable 当前容量(指 Hashtable 的当前“桶”个数)的比例,也称之为“扩容阈值” \color{blue}{“扩容阈值”}扩容阈值
  • 加载因子越大,h a s h 碰撞 \color{red}{hash碰撞}hash碰撞越多,性能越低。加载因子的默认值是0.75,这是考虑到空间(内存)和时间(性能)的折中值。
    注:“hash碰撞”就是上文“加载过程”中的第二步。查找与新对象具有相同hashcode的对象所在“桶”的过程。

3.2 扩容时刻

Hashtable 的扩容时刻是:(指当 Hashtable 中entry个数达到的扩容临界值)

x * 0.75 * 8

x是当前容量,默认值为110.75是加载因子的默认值;8是“桶”重构的临界值。(注:当entry个数达到8个时,“桶”重构,但仍然可以继续存储,与扩容机制无关)

可实际上,一般情况下,扩容时刻会是:

x * 0.75 * 6

为什么是6,不是8?因为 Hashtable 不存在平均分配的机制,且对象的内存地址是任意的,故 hashcode 任意。

P S \color{red}{PS}PS:这两个“扩容时刻”都是一个估计值,作为理论参考。

补充说明 \color{green}{补充说明}补充说明

Hashtable 类有一个属性threshold(扩容阈值),值为当前容量 * 加载因子,此处的“扩容时刻”即threshold与“桶”重构时平均节点数之积。

4、Hashtable 实用举例

@Override
public boolean equals(Object obj) {
    if (this.hashCode() == obj.hashCode()) {
        if (this == obj)
            return true;
        else 
            return false;
    } else
        return false;
}

使用散列表提高对象检索性能。

5、扩展

Hashtable 与 HashMap 的区别:

  1. Hashtable 的默认容量为11,HashMap 的默认容量为16
  2. Hashtable 继承于 Dictionary,HashMap 继承于 AbstractMap
  3. 由于 Hashtable 是线程安全的,故效率低。因此,在多线程环境下,使用ConcurrentHashMap类;而在单线程环境下,使用 HashMap。

最后

相信这篇文章会让大家对散列表的数据结构有了初步的了解,如果大家想进一步了解其底层实现,可查阅这两篇博文:

  1. Java-API简析_java.util.HashTable<K, V>类(基于 Latest JDK)(浅析源码)
  2. Java-API简析_java.util.HashMap<K,V>类(基于 Latest JDK)(浅析源码)

本文完结。

相关文章
|
3天前
|
存储 供应链 Java
《Java 简易速速上手小册》第3章:Java 数据结构(2024 最新版)
《Java 简易速速上手小册》第3章:Java 数据结构(2024 最新版)
4 1
|
4天前
|
缓存 监控 Java
深入理解Java虚拟机(JVM)性能调优
【4月更文挑战第18天】本文探讨了Java虚拟机(JVM)的性能调优,包括使用`jstat`、`jmap`等工具监控CPU、内存和GC活动,选择适合的垃圾回收器(如Serial、Parallel、CMS、G1),调整堆大小和新生代/老年代比例,以及代码优化和JIT编译策略。通过这些方法,开发者能有效提升应用性能并应对复杂性挑战。性能调优是持续过程,需伴随应用演进和环境变化进行监控与优化。
|
10天前
|
Java API
编码的奇迹:Java 21引入有序集合,数据结构再进化
编码的奇迹:Java 21引入有序集合,数据结构再进化
15 0
|
13天前
|
Oracle Java 关系型数据库
java体系结构和jvm
java体系结构和jvm
|
15天前
|
存储 算法
【算法与数据结构】深入解析二叉树(二)之堆结构实现
【算法与数据结构】深入解析二叉树(二)之堆结构实现
|
23天前
|
存储 算法
【数据结构】什么是堆?
【数据结构】什么是堆?
16 0
【数据结构】什么是堆?
|
24天前
|
缓存 Java C#
【JVM故障问题排查心得】「Java技术体系方向」Java虚拟机内存优化之虚拟机参数调优原理介绍(一)
【JVM故障问题排查心得】「Java技术体系方向」Java虚拟机内存优化之虚拟机参数调优原理介绍
64 0
|
27天前
|
算法 搜索推荐
数据结构第十二弹---堆的应用
数据结构第十二弹---堆的应用
|
27天前
|
存储 算法 C++
数据结构第十一弹---堆
数据结构第十一弹---堆
|
28天前
|
缓存 安全 Java
Java并发编程中的高效数据结构 - ConcurrentHashMap
本文将深入探讨Java并发编程中的一种高效数据结构 - ConcurrentHashMap。我们将详细介绍ConcurrentHashMap的基本原理,包括其设计思路、实现方式以及如何在多线程环境下提供高效的并发访问。同时,我们还将通过实例代码演示如何使用ConcurrentHashMap来优化并发程序的性能。