理解数据结构 hashtable的简易理解思路

结构图

为了方便演示，下图中分区算法为下标取模

private int hashFun(int id) {//使用 hash并取模return id % size;}

在这里插入图片描述

Hashtable的结构如图所示：是一个数组（元素为各个链表的表头）+ 多个链表组成，也就是说 hashtable 结合了数组和链表的优点。

  • 数组的特点：寻址容易，插入和删除困难；
  • 链表的特点：寻址困难，而插入和删除操作容易；
  • 哈希表的特点：寻址插入和删除操作都容易。

简单的代码实现

该代码实现的功能有分区存储与查找

  • 数据 Emp 的存储：存储时采用ID 取模算法确定数据的存储位置。
  • 数据 Emp的查找：根据 ID 查找数据
public class HashTableDemo {public static void main(String[] args) {HashTable hashTable = new HashTable(7);hashTable.add(new Emp(1, "jack"));hashTable.add(new Emp(2, "tom"));hashTable.add(new Emp(3, "smith"));hashTable.add(new Emp(4, "mary"));hashTable.add(new Emp(5, "king"));hashTable.add(new Emp(6, "scott"));hashTable.add(new Emp(7, "peter"));hashTable.add(new Emp(8, "jack1"));hashTable.add(new Emp(9, "jack2"));hashTable.add(new Emp(10, "jack3"));hashTable.add(new Emp(11, "jack4"));hashTable.add(new Emp(12, "jack5"));hashTable.add(new Emp(13, "jack6"));hashTable.add(new Emp(14, "jack7"));hashTable.add(new Emp(15, "jack8"));hashTable.list();}
}class HashTable {/*** 数组*/private EmpLinkedList[] empLinkedListArray;/*** 数组的大小*/private int size;public HashTable(int size) {this.size = size;empLinkedListArray = new EmpLinkedList[size];for (int i = 0; i < size; i++) {empLinkedListArray[i] = new EmpLinkedList();}}public void add(Emp emp) {// 使用散列函数确定放入哪个链表int empLinkedListNo = hashFun(emp.id);empLinkedListArray[empLinkedListNo].add(emp);}/*** 使用某种算法确定数据的存放位置* 这里简单的使用模运算，来确定数据应该落在那个数组元素指定的链表上，* 只是一种特例，因为所存的数据包含 ID，所以采用对 ID 取模运算。* 更具一般性的算法是使用 哈希函数，对数组大小取模，这里只是个例子。** @param id 数组的索引* @return*/private int hashFun(int id) {//使用 hash并取模return id % size;}public void list() {for (int i = 0; i < size; i++) {empLinkedListArray[i].list(i);}}
}class EmpLinkedList {private Emp head;public void add(Emp emp) {if (head == null) {head = emp;return;}Emp temp = head;//游标while (temp.next != null) {temp = temp.next;}temp.next = emp;}public void list(int no) {if (head == null) {System.out.println("第" + no + "链表为空");return;}System.out.print("第" + no + "链表信息为：");Emp temp = head;while (temp != null) {System.out.print("id=" + temp.id + " name=" + temp.name + " ");temp = temp.next;}System.out.println();}public Emp findEmpById(int id) {if (head == null) {return null;}Emp temp = head;while (temp != null) {if (temp.id == id) {return temp;}temp = temp.next;}return temp;}
}class Emp {public int id;public String name;public Emp next;public Emp(int id, String name) {this.id = id;this.name = name;}public int getId() {return id;}public void setId(int id) {this.id = id;}public String getName() {return name;}
}

哈希表的理解

可以将每一条链表理解为一个区间，数据按照某种算法添加到与之相适应的区间，也称为分区算法， kafka中 分区的设计思路也是基于此。

这里的算法是对与数据相关的那个属性或者特征值（称为 key）进行某种运算,得到一个唯一的一个数据，该算法的结果决定的所谓的数据落盘。

哈希表的主要功能：

  • 分区存储：对具有相同的特征的数据进行跟组存储。
  • 分区查找：依据数据的特性值，在特定的分组中查找数据，提高了检索的效率。

哈希表名字的由来

为了保证数据查找的唯一性，采用哈希函数才作为分区算法，即是哈希表的由来。

为什么采用哈希函数？

基于哈希函数的性质，所以采用哈希函数作为分区算法。

哈希函数是一种将任意长度的数据映射为固定长度输出的算法。哈希函数广泛应用于计算机科学的多个领域，如数据索引、密码学、数据完整性校验等。以下是哈希函数的主要概念及其性质：

概念

  1. 输入与输出：

    • 输入：可以是任意长度的数据（字符串、文件等）。
    • 输出：固定长度的哈希值（通常是固定长度的二进制串或十六进制字符串）。

  2. 用途：

    • 数据索引：快速查找数据。
    • 数据完整性校验：检测数据是否被篡改。
    • 密码学：安全地存储密码。
    • 散列表：实现高效的数据结构。

性质

  1. 确定性：

    • 对于相同的输入，哈希函数总是产生相同的输出。
    • 这一性质确保了哈希值的可预测性和一致性。

  2. 均匀分布：

    • 哈希函数应尽量使不同的输入产生不同的哈希值，以减少冲突。
    • 均匀分布有助于提高哈希表的性能。

  3. 单向性：

    • 从哈希值很难反推出原始输入数据。
    • 这一性质在密码学中尤为重要，确保了数据的安全性。

  4. 抗碰撞性：

    • 弱抗碰撞性：给定一个输入数据，很难找到另一个不同的输入数据，使得两者的哈希值相同。
    • 强抗碰撞性：很难找到两个不同的输入数据，使得它们的哈希值相同。
    • 抗碰撞性是哈希函数在密码学应用中的关键属性。

  5. 计算效率：

    • 哈希函数应具有较高的计算效率，以便在实际应用中能够快速生成哈希值。

  6. 敏感性：

    • 即使输入数据有微小的变化，哈希值也会发生显著变化。
    • 这一性质有助于检测数据的微小修改。

常见的哈希函数

  • MD5：128位哈希值，已不再推荐用于安全性要求高的场景。
  • SHA-1：160位哈希值，同样不推荐用于安全性要求高的场景。
  • SHA-256：256位哈希值，广泛用于安全敏感的应用。
  • SHA-3：新一代哈希函数，提供更高的安全性和性能。

哈希表的实质

根据对哈希表的结构和算法分析可知，

  • 哈希表的结构：数组（这里体现了哈希）+链表（这里体现里表）；
  • 哈希表的实现逻辑：就是由哈希算法（分区算法）、数组（存放分区首元素）和链表（可以理解为分区）来实现的。

Java 中的 hashtable

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {/*** The hash table data.*/private transient Entry<?,?>[] table;/*** The total number of entries in the hash table.*/private transient int count;/*** The table is rehashed when its size exceeds this threshold.  (The* value of this field is (int)(capacity * loadFactor).)** @serial*/private int threshold;/*** The load factor for the hashtable.** @serial*/private float loadFactor;/*** The number of times this Hashtable has been structurally modified* Structural modifications are those that change the number of entries in* the Hashtable or otherwise modify its internal structure (e.g.,* rehash).  This field is used to make iterators on Collection-views of* the Hashtable fail-fast.  (See ConcurrentModificationException).*/private transient int modCount = 0;/** use serialVersionUID from JDK 1.0.2 for interoperability */@java.io.Serialprivate static final long serialVersionUID = 1421746759512286392L;/*** Constructs a new, empty hashtable with the specified initial* capacity and the specified load factor.** @param      initialCapacity   the initial capacity of the hashtable.* @param      loadFactor        the load factor of the hashtable.* @throws     IllegalArgumentException  if the initial capacity is less*             than zero, or if the load factor is nonpositive.*/public Hashtable(int initialCapacity, float loadFactor) {}/*** Constructs a new, empty hashtable with the specified initial capacity* and default load factor (0.75).** @param     initialCapacity   the initial capacity of the hashtable.* @throws    IllegalArgumentException if the initial capacity is less*              than zero.*/public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}/*** Constructs a new, empty hashtable with a default initial capacity (11)* and load factor (0.75).*/public Hashtable() {this(11, 0.75f);}/*** Constructs a new hashtable with the same mappings as the given* Map.  The hashtable is created with an initial capacity sufficient to* hold the mappings in the given Map and a default load factor (0.75).** @param t the map whose mappings are to be placed in this map.* @throws NullPointerException if the specified map is null.* @since   1.2*/public Hashtable(Map<? extends K, ? extends V> t) {this(Math.max(2*t.size(), 11), 0.75f);putAll(t);}}

从源码中可以看出来hashtable 一共提供了 4 个构造方法

  • public Hashtable(int initialCapacity, float loadFactor)： 用指定初始容量和指定加载因子构造一个新的空哈希表
  • public Hashtable(int initialCapacity) ：用指定初始容量和默认的加载因子 (0.75) 构造一个新的空哈希表
  • public Hashtable()：默认构造函数，容量为 11，加载因子为 0.75
  • public Hashtable(Map<? extends K, ? extends V> t)：构造一个与给定的Map具有相同映射关系的新哈希表

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/491508.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

java 通过jdbc连接sql2000方法

java 通过jdbc连接sql2000方法

1、java通过jdbc连接sql2000 需要到三个jar包&#xff1a;msbase.jar mssqlserver.jar msutil.jar 下载地址&#xff1a;https://download.csdn.net/download/sunfor/90145580 2、将三个jar包解压到程序中的LIB下&#xff1a; 导入方法&#xff1a; ①在当前目录下&#xff…
阅读更多...
[蓝桥杯 2019 国 B] 排列数

[蓝桥杯 2019 国 B] 排列数

目录 前言 题解 思路 疑问 解答 前言 对于本篇文章是站在别人的基础之上来写的&#xff0c;对于这道题作为2019年国赛B组的最难的一题&#xff0c;他的难度肯定是不小的&#xff0c;这道题我再一开始接触的时候连思路都没有&#xff0c;也是看了两三遍别人发的题解&#x…
阅读更多...
VCU--新能源汽车VCU电控开发

VCU--新能源汽车VCU电控开发

课程目标 信号采集的原理 使用simulink处理信号 做一个MIL仿真测试 零、参考 构建Simulink模型——CAN通信 | chans Bloggerrrrr 一、功能概述 1.硬线信号 定义&#xff1a;通过物理导线直接连接的电气信号&#xff0c;一根导线传输一个信号。本质&#xff1a;是一种点对…
阅读更多...
Codeforces Round 993 (Div. 4)题解

Codeforces Round 993 (Div. 4)题解

A. Easy Problem 思路&#xff1a;经过看了一眼&#xff0c;我们发现&#xff0c;ab的和一定是n&#xff0c;且两个都是正整数&#xff0c; 所以a的范围就是从1~n-1 所以输出n-1即可 #include<bits/stdc.h> using namespace std; #define int long long int t; int n…
阅读更多...
日期格式、JSR303校验

日期格式、JSR303校验

日期格式 public class Monster() {DateTimeFormat(pattern "yyyy-MM-dd")private Date birthday; } 输入&#xff1a;2024-11-12&#xff0c; 输出&#xff1a;Monster{birthdaySun Nov 12 00:00:00 CST 2024} public class Monster {JsonFormat(pattern &…
阅读更多...
数据结构——队列的模拟实现

数据结构——队列的模拟实现

大家好&#xff0c;上一篇博客我带领大家进行了数据结构当中的栈的模拟实现 今天我将带领大家实现一个新的数据结构————队列 一&#xff1a;队列简介 首先来认识一下队列&#xff1a; 队列就像我们上学时的排队一样&#xff0c;有一个队头也有一个队尾。 有人入队的话就…
阅读更多...
红外测温原理及设计

红外测温原理及设计

1、红外测温仪 经过新冠疫情的洗礼&#xff0c;大家对红外测温枪应该不陌生。在公共场所、企业单位乃至家庭门口&#xff0c;它都成了守护健康的第一道防线。然而&#xff0c;关于红外测温枪有个细节常被误解——它那闪烁的红点&#xff0c;大部分人会认为就是用这个红色的点测…
阅读更多...
了解垃圾回收机制与内存泄漏

了解垃圾回收机制与内存泄漏

目录 一、垃圾回收机制的基本原理 &#xff08;1&#xff09;基本原理理解 &#xff08;2&#xff09;回收 二、垃圾回收的算法 1.标记清除算法 2.引用计数算法 三、减少垃圾回收 &#xff08;1&#xff09;减少对象创建 &#xff08;2&#xff09;优化数据结构及内存…
阅读更多...
Stable Diffusion Controlnet常用控制类型解析与实战课程 4

Stable Diffusion Controlnet常用控制类型解析与实战课程 4

本节内容&#xff0c;是stable diffusion Controlnet常用控制类型解析与实战的第四节课程。上节课程&#xff0c;我们陆续讲解了几个与图像风格约束相关的控制类型&#xff0c;本节课程我们再学习一些实用价值较高的控制类型&#xff0c;看一看他们提供了哪些控制思路。 一&…
阅读更多...
C++之二：类和对象

C++之二：类和对象

相关代码&#xff1a; C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析求解问题的步骤&#xff0c;调用函数逐步解决问题。 C是面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情的完成分为不同的几个参与者&#xff08;对象&#xff09;&#xff0c;靠…
阅读更多...
B站bilibili视频转文字字幕下载方法

B站bilibili视频转文字字幕下载方法

本文将讲述介绍一种使用本地工具如何快速的下载B站的字幕为本地文本文件的方法。 通常获取B站字幕需要在浏览器中安装第三方插件&#xff0c;通过插件获取字幕。随着大模型&#xff0c;生成式AI&#xff0c;ChatGPT的应用&#xff0c;B站也提供了AI小助手对视频的内容进行总结…
阅读更多...
EM算法的参数更新过程

EM算法的参数更新过程

1. 计算每个高斯分布的责任度 责任度&#xff08;Responsibility&#xff09; 表示数据点 由第 k 个高斯分布生成的概率占总概率的比例。在 E步&#xff08;Expectation Step&#xff09; 中计算。 公式&#xff1a; 其中&#xff1a; ​: 责任度&#xff0c;表示数据点 ​ …
阅读更多...
文件包含include

文件包含include

文件包含 第一道题是攻防世界的fileclude 这里第二行我们可以看见告诉我们在flag.php里面 然后检查了两次file1和file2是否为空 如果file2"hello ctf"成立 那么就可以包含file1 这里我们要使用php伪协议 来访问我们需要的flag.php并且将file2的数值改为"hello…
阅读更多...
优选算法——链表

优选算法——链表

1. 链表常用技巧和操作总结 2. 两数相加 题目链接&#xff1a;2. 两数相加 - 力扣&#xff08;LeetCode&#xff09; 题目展示&#xff1a; 题目分析&#xff1a;本题给的是逆序&#xff0c;其实降低了难度&#xff0c;逆序刚好我们从第一位开始加&#xff0c;算法原理其实就…
阅读更多...
【5G】5G的主要架构选项

【5G】5G的主要架构选项

最初&#xff0c;在3GPP讨论中考虑了所有可能的聚合和核心网络组合&#xff0c;共有八个架构选项。以下重点介绍option2、3、4和7。 1. 独立组网 (Standalone, SA) 架构选项 2 &#xff1a;Standalone architecture with 5G-core 特点&#xff1a; 5G核心网&#xff08;5GC, …
阅读更多...
css 动画实现从中间到两边亮度逐渐变暗的流水灯效果

css 动画实现从中间到两边亮度逐渐变暗的流水灯效果

先看效果&#xff1a; 快结束效果 随着离中心点距离逐渐边远&#xff0c;亮度逐渐变暗 完整的视线代码如下&#xff1a; <template><div class"container"><div class"runner bottom to-right"></div><div class"runner …
阅读更多...
kubeadm_k8s_v1.31高可用部署教程

kubeadm_k8s_v1.31高可用部署教程

kubeadm_k8s_v1.31高可用部署教程 实验环境部署拓扑图**部署署架构****Load Balance****Control plane node****Worker node****资源分配&#xff08;8台虚拟机&#xff09;**集群列表 前置准备关闭swap开启ipv4转发更多设置 1、Verify the MAC address and product_uuid are u…
阅读更多...
测评|携程集团25年社招在线测评北森题库、真题分析、考试攻略

测评|携程集团25年社招在线测评北森题库、真题分析、考试攻略

携程集团社招入职测评北森题库主要考察以下几个方面&#xff1a; 1. **言语理解**&#xff1a;这部分主要测试应聘者运用语言文字进行思考和交流、迅速准确地理解和把握文段要旨的能力。 2. **资料分析**&#xff1a;包括文字题和图表题&#xff0c;考察应聘者快速找出关键信息…
阅读更多...
workman服务端开发模式-应用开发-websockt应用介绍

workman服务端开发模式-应用开发-websockt应用介绍

一、workerman介绍 1、框架介绍 workerman-chat框架是基于workerman的GatewayWorker框架开发的一款高性能支持分布式部署的聊天室系统。 workerman框架官网&#xff1a;http://www.workerman.net/ GatewayWorker框架文档&#xff1a;http://www.workerman.net/gatewaydoc/ 2、特…
阅读更多...
34. 在排序数组中查找元素的第一个和最后一个位置 二分法

34. 在排序数组中查找元素的第一个和最后一个位置 二分法

34. 在排序数组中查找元素的第一个和最后一个位置 class Solution { public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res(2,-1);res[0]findleft(nums,target);if(res[0] -1) return res;res[1] findright(nums,target);…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023