当前位置：首页 > news >正文

Hashtable 描述及源码解析

news 来源：原创 2025/5/25 15:22:54

一、Hashtable的基本概念

二、Hashtable的源码解析

构造函数

哈希算法函数

处理哈希冲突

类定义和成员变量

构造方法

插入元素

查找元素

删除元素

扩容

Hashtable（哈希表）是一种非常重要的数据结构，它提供了快速的数据插入、删除和查找功能。以下是对Hashtable的详细描述及源码解析：

一、Hashtable的基本概念

哈希函数：能将键值转换为哈希表范围内的索引（0~M-1），是哈希表的核心。哈希函数的设计目标是尽量减小冲突（多个不同的键映射到相同的哈希值）的可能性。
哈希表：一个由数组构成的数据结构，数组的每个位置称为槽（Slot）或桶（Bucket）。通过哈希函数计算得到的哈希值用作数组的索引，将键值对存储在对应的槽中。
哈希冲突：由于哈希表的输出范围有限，而键的数量可能非常多，因此不同的键可能通过哈希函数得到相同的索引，这种现象称为哈希冲突。

二、Hashtable的源码解析

以下是对Hashtable源码的一些关键点的解析，注意，具体的实现可能因编程语言和库的不同而有所差异。

构造函数

Hashtable的构造函数通常需要两个参数：容量和装载因子。装载因子是哈希表中存储桶数（count）所占桶数组（buckets）桶数（hashsize）的最大比率，它决定了哈希表何时需要扩容。装载因子默认为1.0，但某些实现（如微软的.NET Framework）会将其乘以一个系数（如0.72）以优化性能和内存使用。

构造函数内部会利用容量/装载因子获取一个桶数组大小的估值，并借助一个辅助类（如HashHelpers）获取一个大于等于某个值（如3）的素数作为内部桶数组的初始长度，并以此长度初始化桶数组。

哈希算法函数

Hashtable内部采用的哈希算法函数可能有所不同，但目标都是将键值转换为哈希表中的索引。一些实现可能采用双重散列法，这是开放地址法中较好的方法之一。双重散列法使用两个哈希函数，当发生冲突时，通过第二个哈希函数计算一个新的索引。

处理哈希冲突

处理哈希冲突的方法有多种，常见的包括开放定址法和链地址法。

* **开放定址法**：当发生冲突时，通过某种规则在哈希表中寻找下一个可用的槽来存放数据。这些规则可能包括线性探测、二次探测等。

* **链地址法**：每个槽存储一个链表或其他数据结构，当发生冲突时，新的键值对被添加到链表中。这种方法可以避免哈希表的扩容和重新分配内存的开销，但可能会增加查找时间。

类定义和成员变量

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable
{// 默认容量private static final int DEFAULT_CAPACITY = 11;// 最大容量private static final int MAXIMUM_CAPACITY = 1 << 30;// 默认加载因子private static final float DEFAULT_LOAD_FACTOR = 0.75f;// 容量private int capacity;// 加载因子private float loadFactor;// 元素个数private transient int count = 0;// 存储元素的数组private transient Entry<?,?>[] table = {};// 修改次数private transient int modCount = 0;// 内部类，哈希表的节点private static class Entry<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Entry<K,V> next;Entry(int hash, K key, V value, Entry<K,V> next) {this.hash = hash;this.key =  key;this.value = value;this.next = next;}}
}

构造方法

Hashtable 提供了多个构造方法，允许用户指定初始容量、加载因子或使用默认值。

public Hashtable() {this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}public Hashtable(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public Hashtable(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal Load: "+loadFactor);if (initialCapacity==0)initialCapacity = 1;this.loadFactor = loadFactor;table = new Entry<?,?>[initialCapacity];threshold = (int)(table.length * loadFactor);
}

插入元素

在 Hashtable 中，插入元素时，会根据键的哈希值，找到合适的位置插入节点。

public synchronized V put(K key, V value) {// 处理 null 键if (key == null)return putForNullKey(value);int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % table.length;Entry<K,V> entry = table[index];while (entry != null && !key.equals(entry.key))entry = entry.next;V oldValue;if (entry != null) {oldValue = entry.value;entry.value = value;} else {addEntry(hash, key, value, index);modCount++;}return oldValue;
}

查找元素

在 Hashtable 中，查找元素时，会根据键的哈希值，从对应的位置开始比较，直到找到匹配的节点或遍历完整个链表。

public synchronized V get(Object key) {if (key == null)return getForNullKey();int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % table.length;for (Entry<K,V> e = table[index]; e != null; e = e.next) {if (e.hash == hash && key.equals(e.key))return e.value;}return null;
}

删除元素

在 Hashtable 中，删除元素时，会先找到要删除的节点，然后从链表中移除该节点。

public synchronized V remove(Object key) {Entry<K,V> entry = removeEntryForKey(key);return (entry == null ? null : entry.value);
}private Entry<K,V> removeEntryForKey(Object key) {int hash = (key == null) ? 0 : key.hashCode();int index = (hash & 0x7FFFFFFF) % table.length;Entry<K,V> e = table[index];Entry<K,V> prev = null;while (e != null) {if (e.hash == hash && key.equals(e.key)) {if (prev == null)table[index] = e.next;elseprev.next = e.next;modCount++;count--;return e;}prev = e;e = e.next;}return e;
}

扩容

当哈希表中的元素数量超过某个阈值（如装载因子与当前桶数组大小的乘积）时，哈希表会进行扩容。扩容操作会创建一个新的桶数组，并将原数组中的元素重新哈希并插入到新数组中。这个操作可能会比较耗时，因此在实际应用中需要尽量避免频繁的扩容操作。

当 Hashtable 中的元素个数超过阈值时，会进行扩容操作，将容量扩大为原来的两倍。

protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;int newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAXIMUM_CAPACITY > 0) {if (oldCapacity == MAXIMUM_CAPACITY)return;newCapacity = MAXIMUM_CAPACITY;}Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];threshold = (int)(newCapacity * loadFactor);table = newMap;for (int i = oldCapacity ; i-- > 0 ;) {for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {Entry<K,V> e = old;old = old.next;int index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = (Entry<K,V>)newMap[index];newMap[index] = e;}}
}

Hashtable 通过哈希表作为底层的数据结构，实现了线程安全的 Map 接口。在插入、查找和删除元素时，Hashtable 会根据键的哈希值，找到合适的位置进行操作。当元素个数超过阈值时，Hashtable 会进行扩容操作，以保证性能。

Hashtable 描述及源码解析

目录一、Hashtable的基本概念二、Hashtable的源码解析构造函数哈希算法函数处理哈希冲突类定义和成员变量构造方法插入元素查找元素删除元素扩容 Hashtable（哈希表）是一种非常重要的数据结构，它提供了快速的数据插入、删…...

编程日记 2025/5/25 15:22:54

clickhouse-数据库引擎

1、数据库引擎和表引擎数据库引擎默认是Ordinary，在这种数据库下面的表可以是任意类型引擎。生产环境中常用的表引擎是MergeTree系列，也是官方主推的引擎。 MergeTree是基础引擎，有主键索引、数据分区、数据副本、数据采样、删除和修改等功…...

编程日记 2025/5/23 23:12:12

深度学习之超分辨率算法——SRCNN

网络为基础卷积层 tensorflow 1.14 scipy 1.2.1 numpy 1.16 大概意思就是针对数据，我们先把图片按缩小因子照整数倍进行缩减为小图片，再针对小图片进行插值算法，获得还原后的低分辨率的图片作为标签。 main.py 配置文件 from model im…...

编程日记 2025/5/23 23:12:09

本机如何连接虚拟机MYSQL

要让本机（主机）连接到虚拟机上的 MySQL 数据库，你需要确保虚拟机和主机之间的网络连接正常，并且 MySQL 配置允许外部连接。以下是实现本机连接虚拟机 MySQL 的步骤： 步骤 1：确认虚拟机与本机的网络连接确…...

编程日记 2025/5/25 15:13:17

Download GraalVM 上面链接选择jdk的版本以及系统的环境下载graalvm的tar包解压tar包 tar -xzf graalvm-jdk-<version>_macos-<architecture>.tar.gz 移入java的文件夹目录 sudo mv graalvm-jdk-<version> /Library/Java/JavaVirtualMachines 设置环境变…...

编程日记 2025/5/24 18:23:25

大模型日报 2024-12-19

大模型日报 2024-12-19 大模型资讯标题：OpenAI发布季第十天：ChatGPT登陆电话、WhatsApp，你可以给ChatGPT真正打电话了摘要：OpenAI于2024年12月18日发布了ChatGPT的新功能，用户可以通过电话和WhatsApp与ChatGPT进行互…...

编程日记 2025/5/25 15:01:19

【数据结构练习题】链表与LinkedList

顺序表与链表LinkedList 选择题链表面试题1. 删除链表中等于给定值 val 的所有节点。2. 反转一个单链表。3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。4. 输入一个链表，输出该链…...

编程日记 2025/5/25 14:18:10

使用 acme.sh 申请域名 SSL/TLS 证书完整指南

使用 acme.sh 申请域名 SSL/TLS 证书完整指南简介为什么选择 acme.sh 和 ZeroSSL？前置要求安装过程步骤一：安装 acme.sh步骤二：配置 ZeroSSL 证书申请方法一：手动 DNS 验证（推荐新手使用）方法二&#xf…...

编程日记 2025/5/25 15:10:10

微信小程序开发入门

实现滚动需要设置高度和边框轮播图差值表达式（ {{表达式的值}} ）,info数据要写到js文件的data数据中小程序中常用的事件...

编程日记 2025/5/17 23:42:41

【LeetCode】9、回文数

【LeetCode】9、回文数文章目录一、数学: 除法和取模1.1 数学: 除法和取模二、多语言解法一、数学: 除法和取模 1.1 数学: 除法和取模例如 15251, offset 也是五位数的 10000 先判断首1和尾1, 再变为 525, offset 变为 100 再判断首5和尾5, 再变为 2, offset 变为 1 整个…...

编程日记 2025/5/20 8:15:15

面试题整理9----谈谈对k8s的理解2

面试题整理9----谈谈对k8s的理解2 1. Service 资源1.1 ServiceClusterIPNodePortLoadBalancerIngressExternalName 1.2 Endpoints1.3 Ingress1.4 EndpointSlice1.5 IngressClass 2. 配置和存储资源2.1 ConfigMap2.2 Secret2.3 PersistentVolume2.4 PersistentVolumeClaim2.5 St…...

编程日记 2025/5/25 14:19:34

fpga系列 HDL：Quartus II PLL (Phase-Locked Loop) IP核 (Quartus II 18.0)

在 Quartus II 中使用 PLL (Phase-Locked Loop) 模块来将输入时钟分频或倍频，并生成多个相位偏移或频率不同的时钟信号： 1. 生成 PLL 模块在 Quartus II 中： 打开 IP Components。 file:///C:/intelFPGA_lite/18.0/quartus/common/help/w…...

编程日记 2025/5/25 7:50:00

中国量子计算机领域的发展现状与展望

中国量子计算机领域的发展现状与展望摘要随着全球科技竞争的加剧，量子计算作为前沿技术领域备受瞩目。中国在量子计算机的研发方面取得了显著进展，本文将深入探讨中国量子计算机领域的现状、取得的成果、面临的挑战以及未来的发展方向，并…...

编程日记 2025/5/25 3:36:54

html（超文本标记语言）

声明！ 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下，如涉及侵权马上删除文章，笔记只是方便各位师傅的学习和探讨，文章所提到的网站以及内容，只做学习交流，其他均与本人以及泷羽sec团队无关&…...

编程日记 2025/5/25 14:11:27

如何在Windows系统上安装和配置Maven

Maven是一个强大的构建和项目管理工具，广泛应用于Java项目的自动化构建、依赖管理、项目构建生命周期控制等方面。在Windows系统上安装Maven并配置环境变量，是开发者开始使用Maven的第一步。本文将详细介绍如何在Windows系统上安装和配置Maven&#xff0…...

编程日记 2025/5/24 9:11:52

基于Python Scrapy的豆瓣Top250电影爬虫程序

Scrapy安装 Python实现一个简单的爬虫程序（爬取图片）_python简单扒图脚本-CSDN博客创建爬虫项目创建爬虫项目： scrapy startproject test_spider 创建爬虫程序文件： >cd test_spider\test_spider\spiders >scrapy g…...

编程日记 2025/5/25 14:15:01

mysql,数据库数据备份

mysql 一.数据库备份概念1.备份分类2.备份策略3.备份三要素二.完全备份操作1.物理备份(还原),冷备份2.逻辑备份,温备份三.percona软件的xtrabackup工具备份(2备份,3还原),增量,差异1.percona软件安装2.增量备份(还原)3.差异备份四.binlog日志1.binlog日志概念2.查看binlog日志信…...

编程日记 2025/5/25 15:18:26

模仿elementui的Table，实现思路

vue2子组件使用render，给子子组件插槽传值和elementui的Table一样使用render 在 Vue 2 中，子组件使用render函数向子子组件插槽传值可以通过以下步骤实现： 1、创建子组件首先创建一个子组件，在子组件中使用render函数来渲染内容…...

编程日记 2025/5/20 6:46:16

Android Studio AI助手---Gemini

从金丝雀频道下载最新版 Android Studio，以利用所有这些新功能，并继续阅读以了解新增内容。 Gemini 现在可以编写、重构和记录 Android 代码 Gemini 不仅仅是提供指导。它可以编辑您的代码，帮助您快速从原型转向实现，实现常见的…...

编程日记 2025/5/25 2:33:56

大模型+安全实践之春天何时到来？

引子：距《在大模型实践旅途中摸了下上帝的脚指头》一文发布近一年，2024年笔者继续全情投入在大模型＋安全上，深度参与了一些应用实践，包括安全大模型首次大规模应用在国家级攻防演习、部分项目的POC直到项目落地，也推动了一些场景安全大模型应用从0到3的孵化上市。这一年也…...

编程日记 2025/5/25 14:25:03

ACL技术---访问控制列表

是一种策略。对于网络中的流量而言，通常有两种处理方式允许拒绝 ACL 的原理配置了 ACL 的网络设备会根据事先设定好的报文匹配规则对经过该设备的报文进行匹配，然后对报文执行预先设定好的处理动作。 ACL 的功能访问控制：在设备…...

编程日记 2025/5/25 15:19:53

第25周：文献阅读

目录摘要 Abstract 文献阅读现有问题提出方法创新点方法论实验研究数据集数据预处理仿真实验评价指标实验结果分析总结摘要本篇论文提出了一种基于深度学习框架的风速预测方法——SSA-BiLSTM网络，旨在提高风速预测的精确性。研究使…...

编程日记 2025/5/25 14:44:32

BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出）

Matlab实现BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出） 目录 Matlab实现BiTCN-BiGRU基于双向时间卷积网络结合双向门控循环单元的数据多特征分类预测（多输入单输出）分类效果基本描述…...

编程日记 2025/5/25 14:32:12

docker数据卷

什么是数据卷？ 在容器中是无法通过vi命令对一个容器中的资源做修改的，这个时候就需要通过数据卷将文件中的内容映射到宿主机，在宿主机修改的文件会更新到容器中，并且容器被删除后不会把数据卷删除，数据卷中的数据会被持…...

编程日记 2025/5/25 15:11:47

Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务间的通讯-信号量【入门三】

继续上一篇任务创建【Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务创建【入门二】-CSDN博客】今天要实现再创建一个任务。【二值和互斥都进行测试】 ①、通过任务A发送一个信号量，另一个任务得到信号量后再发送helloworld。 ②、两个任务通过互斥信…...

编程日记 2025/5/23 23:12:07

使用C#绘制具有平滑阴影颜色的曼德布洛特集分形

示例使用复数类在 C# 中轻松绘制曼德布洛特集分形解释了如何通过迭代方程绘制曼德布洛特集：...

编程日记 2025/5/23 23:12:04

Unittest01|TestCase

一、入门 1、新建测试文件打开pycharm→左上角新建项目→选择项目路径→选择python解释器→创建→点击新建好的项目，右键新建python文件→测试文件（py文件）命名必须以test开头 2、创建测试用例定义测试类：导入unittest模块→…...

编程日记 2025/5/25 14:33:48

Django实现异步视图asyncio请求

随着现代Web应用程序对性能和响应速度的需求不断增加，开发者们越来越倾向于采用异步编程来提升应用的效率和用户体验。在传统的Web开发框架中，通常采用同步请求方式，这意味着每一个请求都需要等待前一个请求完成后才能继续处理。对于高并发的请求，可能会出现性能瓶颈。而Dj…...

编程日记 2025/5/21 14:37:15

Apache Samza开源的分布式流处理框架

Apache Samza 是一个开源的分布式流处理框架，用于处理实时数据流和分布式任务。它最初由 LinkedIn 开发，并在 2014 年捐赠给 Apache 软件基金会。Samza 的设计目标是为开发人员提供一个易用、可靠、高效的流处理工具。以下是其关键特点和架构的简介：核心特点简单的编程模…...

编程日记 2025/5/21 22:33:33

Linux实验报告5-shell脚本编程进阶

目录一：实验目的二：实验内容 1 编写脚本，实现将当前目录中所有子目录的名称输出到屏幕上。 2 首先以你的姓氏的拼音为开头在当前用户的主目录下新建3个文件和2个子目录，如zi1，zi2，zi3以及子目录zi.d和…...

编程日记 2025/5/24 10:18:57

YOLO系列正传（四）YOLOv3论文精解(下)——损失函数推导与其他优化项

系列文章 YOLO系列基础 YOLO系列基础合集——小白也看得懂的论文精解-CSDN博客 YOLO系列正传 YOLO系列正传（一）类别损失与MSE损失函数、交叉熵损失函数-CSDN博客 YOLO系列正传（二）YOLOv3论文精解(上)——从FPN到darknet-53-C…...

编程日记 2025/5/20 21:59:19

【漏洞复现】CVE-2023-37461 Arbitrary File Writing

漏洞信息 NVD - cve-2023-37461 Metersphere is an opensource testing framework. Files uploaded to Metersphere may define a belongType value with a relative path like ../../../../ which may cause metersphere to attempt to overwrite an existing file in the d…...

编程日记 2025/5/23 23:12:01

一、Hashtable的基本概念

二、Hashtable的源码解析

构造函数

哈希算法函数

处理哈希冲突

类定义和成员变量

构造方法

插入元素

查找元素

删除元素

扩容

相关文章：