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

简介: 本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。

【版权声明】未经博主同意,谢绝转载!(请尊重原创,博主保留追究权)
https://developer.aliyun.com/article/1635711
出自【进步*于辰的博客

参考笔记二,P67、P68.1。

1、什么是“散列表”?

大家先看张图,这是我理解的“散列表”底层数据结构图。
在这里插入图片描述
我先大致说说 JVM 的内存结构。
JVM内存结构主要由堆、栈和方法区组成。栈主要用于存储基本数据类型变量和引用、以及引用类型变量引用等;堆主要用于存储对象和数组;方法区主要用于存储类信息和常量。

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

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

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

2、关于对象存储过程

2.1 加载过程

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

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

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

补充说明:

Hashtable 是一种数据结构,可以存储任何类型数据,对象只是其一。
如果 Hashtable 存储的是对象,则key存储的是内存地址,value存储的是对象。

若 Hashtable 中存储的是对象,则加载过程就是检索对象应存储位置后直接插入对象,不存在覆盖现象。
如:Hashtable<String, Object>,映射(有些资料也称之为“条目”)是Entry<String, Object>。由于key可能重复,故可能会覆盖。


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

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

不过,这里有一个问题我暂未理清,大家看String类的第3.22项的hashcode(),此方法返回字符串的哈希码。可见,两个内容相同的字符串的hash相同。那么,Hashtable<String, Object>的数据结构又是怎样的?

2.2 注意

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

    3、Hashtable 扩容机制

    先说定义:

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

    3.1 扩容机制是什么?

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

    • 每个“桶”都有一个初始entry容纳个数。
  • “加载因子”指填满(“桶”中entry个数达到初始容纳个数)的“桶”的个数占 Hashtable 当前容量(指 Hashtable 的当前“桶”个数)的比例,也称之为“扩容阈值”。
  • 加载因子越大,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 任意。

PS:这两个“扩容时刻”都是一个估计值,作为理论参考。

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

4、散列表应用示例

@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
    1. Hashtable 继承于 Dictionary<K,V>,HashMap 继承于 AbstractMap<K,V>
  2. 由于 Hashtable 是线程安全的,故效率低。因此,在多线程环境下,使用ConcurrentHashMap<K,V>类;而在单线程环境下,使用 HashMap。

    最后

    本文中的例子是为了方便大家理解和阐述知识点而简单举出的,旨在阐明知识点,并不一定有实用性,仅是抛砖引玉。

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

本文完结。

相关文章
|
24天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
61 16
|
2月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
70 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
2月前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
55 8
|
2月前
|
存储 Java
JVM知识体系学习四:排序规范(happens-before原则)、对象创建过程、对象的内存中存储布局、对象的大小、对象头内容、对象如何定位、对象如何分配
这篇文章详细地介绍了Java对象的创建过程、内存布局、对象头的MarkWord、对象的定位方式以及对象的分配策略,并深入探讨了happens-before原则以确保多线程环境下的正确同步。
57 0
JVM知识体系学习四:排序规范(happens-before原则)、对象创建过程、对象的内存中存储布局、对象的大小、对象头内容、对象如何定位、对象如何分配
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
72 1
|
2月前
|
算法 Java API
【用Java学习数据结构系列】对象的比较(Priority Queue实现的前提)
【用Java学习数据结构系列】对象的比较(Priority Queue实现的前提)
26 1
|
2月前
|
算法 Java
JVM进阶调优系列(3)堆内存的对象什么时候被回收?
堆对象的生命周期是咋样的?什么时候被回收,回收前又如何流转?具体又是被如何回收?今天重点讲对象GC,看完这篇就全都明白了。
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
31 0
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现