从 0 到 1 读懂:哈希表

哈希表

  • 一、什么是哈希表?
  • 二、两种散列函数构造方法
    • 1、直接定址法
    • 2、除留余数法(常用)
  • 三、散列地址冲突
  • 四、常用冲突处理
    • 1、负载因子调节(减少冲突概率)
    • 2、开放定址法(闭散列)
      • (1)线性探测
      • (2)二次探测
    • 3、链地址法(开散列)
    • 4、冲突严重时的解决办法
  • 五、Java 中 HashMap 的实现
    • 1、定义map结点
    • 2、put 插入方法的实现
    • 3、get 查询方法的实现

一、什么是哈希表?

一般来说,搜索的效率取决于搜索过程中元素的比较次数。例如顺序结构中,查找一个元素时需要挨个比对元素,因此时间复杂度为 O ( N ) O(N) O(N)。对于一颗平衡的搜索树,查找的时间复杂度为树的高度,即 O ( l o g 2 ( N ) ) O(log_2(N)) O(log2(N)).

而上述都并不是理想的搜索方法,理想的搜索方法是,可以不经过任何比较,一次直接从表中得到要搜索的元素。 这时就引出了哈希表的数据结构。哈希表就是通过(散列函数)哈希函数,使元素的存储位置与它的关键码 key 之间能够建立一一映射的关系,那样我们在查找关键字时,不需要比较就可获得需要的记录的存储位置。时间复杂度可达到 O ( 1 ) O(1) O(1).

采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(HashTable).

二、两种散列函数构造方法

1、直接定址法

如果我们现在要对 0~100 岁的人口数字统计表,那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时 f ( k e y ) = k e y f ( key) =key f(key)=key.

如果我们现在要统计的是 80 后出生年份的人口数,那么我们对出生年份这个关键字可以用年份减去 1980 来作为地址。此时 f ( k e y ) = k e y − 1980 f ( key) = key-1980 f(key)=key1980.

也就是说,我们可以取关键字的某个线性函数值为散列地址,即 f ( k e y ) = a × k e y + b f ( key ) =a \times key+b f(key)=a×key+b (a 为常数).

这样的散列函数优点就是简单,均匀,也不会产生冲突,但问题是这需要事先知道关键字的分布情况,适合查找表较小且连续的情况。由于这样的限制,在现实应用中,此方法虽然简单,但却并不常用

2、除留余数法(常用)

此方法为最常用的构造散列函数方法,对于散列表长为 m 的散列函数公式为: f ( k e y ) = k e y / p f ( key) = key / p f(key)=key/p ,(p <= m).

很显然,本方法的关键就在于选择合适的 p 如果选得不好,就可能会容易产生冲突。根据前辈们的经验,若散列表表长为 m 通常 p 为小于或等于表长(最好接近 m )的最小质数。

三、散列地址冲突

在上文中,提到了冲突这个概念,那么到底什么是冲突呢?

在理想的情况下,每一个关键字,通过散列函数计算出来的地址都是不一样的,可现实中,这只是个理想。我们时常会碰到两个关键字 k e y 1 ≠ k e y 2 key_1 \neq key_2 key1=key2,但是却有 f ( k e y 1 ) = f ( k e y 2 ) f(key_1) = f(key_2) f(key1)=f(key2),这种现象我们称为冲突 (oollision) ,并把 k e y 1 key_1 key1 k e y 2 key_2 key2 称为这个散列函数的同义词 (synonym)。出现了冲突当然非常糟糕,那将造成数据查找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少,但是不能完全避免。

四、常用冲突处理

1、负载因子调节(减少冲突概率)

散列表的负载因子定义为:loadFactor = 填入表中的元素个数 /散列表的长度

loadFactor 是散列表装满程度的标志因子。由于表长是定值,loadFactor 与“填入表中的元素个数”成正比,所以,loadFactor 越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,Q越小,标明填入表中的元素越少,产生冲突的可能性就越小。

常见的负载因子阈值通常为 0.7 或 0.8,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75。当负载因子超过一定阈值时,可能会导致哈希冲突的增加,因此我们会对负载因子进行调节,由于表长是一定的,所以一般采用扩容的方式增加哈希表的大小,从而降低负载因子。扩容后,原有的元素需要重新计算哈希值和位置,并存储到新的哈希表中。

2、开放定址法(闭散列)

开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。根据寻找空散列的方式,可以分为以下两种:

(1)线性探测

线性探测就是从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

公式 f i ( k e y ) = ( f ( k e y ) + d i ) / m , ( d = 1 , 2 , . . . . , m − 1 ) f_i ( key ) = ( f ( key ) +d_i ) / m,(d =1,2,....,m-1) fi(key)=(f(key)+di)/m(d=12....m1)

(2)二次探测

从上面例子中可以看到,我们在解决冲突的时候,还会碰到如 25 这种本来都不是同义词却要争夺一个地址的情况 ,称这种现象为堆积。很显然,堆积的出现,使得我们需要不断处理冲突,无论是存入还是查找效率都会大大降低。为了解决上述种问题,提出了二次探测法,双向寻找到可能的空位置。

公式 f i ( k e y ) = ( f ( k e y ) + d i ) / m , ( d i = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , q 2 , − q 2 , q < = m / 2 ) f_i ( key ) = ( f (key) +d_i) / m ,(d_i=1^2,-1^2,2^2,-2^2,...,q^2,-q^2,q<=m/2) fi(key)=(f(key)+di)/m(di=12122222...q2q2q<=m/2)

例如使用二次探测,再向上述HashTable中插入 34

3、链地址法(开散列)

首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。此时,已经不存在什么冲突换址的问题了,无论有多少个冲突,都只是在当前位置给单链表增加结点的问题。

4、冲突严重时的解决办法

上面提到了,哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了,那如果冲突严重,就意味
着小集合的搜索性能其实也时不佳的,这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化,例如:

  1. 每个桶的背后是另一个哈希表
  2. 每个桶的背后是一棵搜索树

五、Java 中 HashMap 的实现

1、定义map结点

HashMap底层使用哈希表,下面就使用哈希表简单实现一下,HashMap 中的 插入查询 方法。首先是定义 map 结点:

public class MyHashMap<K,V> {// 定义 map 结点:key-value 模型static class Node<K,V> {public K key;public V value;public Node<K,V> next;public Node(K key, V value) {this.key = key;this.value = value;}}// 创建哈希表,初始容量为 10public Node<K,V>[] hashTable = (Node<K, V>[]) new Node[10];// 哈希表中有效元素个数public int usedSize;// 负载因子,此处取0.75(负载因子 = 填入表中元素个数/散列表长度)public static final double LOAD_FACTOR = 0.75;
}

2、put 插入方法的实现

再进行插入操作时,我们需要根据结点 key 值计算散列位置,由于 key 不一定为数值类型,我们不能直接使用它散列函数的计算。此时我们需要用到 hashCode() 方法:

hashCode() 方法可以获取对象的哈希码,它是一个整数,用来表示对象的状态,且哈希码具有唯一性。

所以我们可以通过 hashCode() 方法求得 key 的哈希码,然后根据得到的哈希码带入散列函数去计算散列位置。这里需要注意一点是:

使用 hashCode() 获取到的哈希码是一个有符号的整形,这也就意味着得到的哈希码有可能是负数,而哈希表的底层是一个数组,它的下标值不可能为负数,因此需要将得到的哈希码按位与上Integer.MAX_VALUE 也就是 0x7FFFFFFF,使得到的值是一个正数。

	// 1.put(K key,V value):插入操作public void put(K key,V value) {// 计算 key 值的 hash 值int hash = key.hashCode() & Integer.MAX_VALUE;// 取留余数法计算散列位置int index = hash % hashTable.length;// 拿到散列位置的哈希桶Node<K,V> cur = hashTable[index];// 判断是否已经存在key值(哈希表中不允许存在相同key值)while (cur != null) {if (cur.key.equals(key)) {// 如果存在 key 相同的元素,更新 value 值cur.value = value;return;}cur = cur.next;}// 采用头插法Node<K,V> newNode = new Node<>(key, value);newNode.next = hashTable[index];hashTable[index] = newNode;usedSize++;// 为减少冲突率,我们要判断负载因子是否超过预设值if (calculate_LoadFactor() >= LOAD_FACTOR) {// 如果大于等于负载因子,需要扩容resize();}}// (1) calculate_LoadFactor():计算此时负载因子private double calculate_LoadFactor() {return usedSize * 1.0 / hashTable.length;}// (2) resize():扩容并重新计算哈希值和位置,并存储到新的哈希表中。private void resize() {// 扩容Node<K,V>[] newhashTable = (Node<K, V>[]) new Node[2* hashTable.length];// 因为改变了散列表长度,需要重新将每一个结点散列到新的位置for (int i = 0; i < hashTable.length; i++) {Node<K,V> cur = hashTable[i];while (cur != null) {// 记录curNext的位置,防止后续调整丢失Node<K,V> curNext = cur.next;// 重新计算哈希值int hash = cur.key.hashCode() & Integer.MAX_VALUE;// 根据散列函数计算散列位置int index = hash % newhashTable.length;// 头插法cur.next = newhashTable[index];newhashTable[index] = cur;cur = curNext;}}// 更新哈希表hashTable = newhashTable;}

3、get 查询方法的实现

    // 2.get(K key):查询public V get(K key) {// 计算哈希值int hash = key.hashCode() & Integer.MAX_VALUE;// 根据散列函数计算散列位置int index = hash % hashTable.length;// 遍历哈希桶,寻找元素Node<K,V> cur = hashTable[index];while (cur != null) {if (cur.key.equals(key)) {// 找到返回 值valuereturn cur.value;}cur = cur.next;}// 找不到返回 nullreturn null;}

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

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

相关文章

【运维】linkis1.3.2添加jdbc引擎(添加mysql、greenplum、starrocks、doris数据源查询)与配合多数据源管理提交任务初探

文章目录 一. 引擎的安装1. 前置工作2. 获取引擎插件3. 上传和加载4. 引擎刷新4.1. 重启刷新4.2. 检查引擎是否刷新成功 二. 测试mysql、starrocks与doris数据库1. 通过shell提交任务2. 通过(IDE)shell进行提交3. 通过接口提交 三. 添加greenplum四. 通过linkis的数据源管理提交…

【韩顺平 零基础30天学会Java】程序流程控制(2days)

day1 程序流程控制&#xff1a;顺序控制、分支控制、循环控制 顺序控制&#xff1a;从上到下逐行地执行&#xff0c;中间没有任何判断和跳转。 Java中定义变量时要采用合法的前向引用。 分支控制if-else&#xff1a;单分支、双分支和多分支。 单分支 import java.util.Scann…

Appium-移动端自动测试框架,如何入门?

Appium是一个开源跨平台移动应用自动化测试框架。 既然只是想学习下Appium如何入门&#xff0c;那么我们就直奔主题。文章结构如下&#xff1a; 1、为什么要使用Appium&#xff1f; 2、如何搭建Appium工具环境?(超详细&#xff09; 3、通过demo演示Appium的使用 4、Appium如何…

《学爸》成爆款背后,马栏山以BOT模式示范“文化+科技”路径

文|智能相对论 作者|范柔丝 今年暑期档的爆款电影&#xff0c;必有《学爸》一席之地。 这部给众多深陷教育旋涡的家长带来深刻思考的电影&#xff0c;就是马栏山视频文创产业园经过3年筹备&#xff0c;首部本土孵化出品的教育现实体裁院线大电影。 据猫眼专业版数据&#x…

优于立方复杂度的 Rust 中矩阵乘法

中途&#xff1a;三次矩阵乘法 一、说明 几年前&#xff0c;我在 C 年编写了 Strassen 矩阵乘法算法的实现&#xff0c;最近在 Rust 中重新实现了它&#xff0c;因为我继续学习该语言。这是学习 Rust 性能特征和优化技术的有用练习&#xff0c;因为尽管 Strassen 的算法复杂性优…

【LLM数据篇】预训练数据集+指令生成sft数据集

note 在《Aligning Large Language Models with Human: A Survey》综述中对LLM数据分类为典型的人工标注数据、self-instruct数据集等优秀的开源sft数据集&#xff1a;alpaca_data、belle、千言数据集、firefly、moss-003-sft-data多轮对话数据集等 文章目录 note构造指令实例…

【Linux】网络层协议:IP

我们必须接受批评&#xff0c;因为它可以帮助我们走出自恋的幻象&#xff0c;不至于长久在道德和智识上自我陶醉&#xff0c;在自恋中走向毁灭&#xff0c;事实上我们远比自己想象的更伪善和幽暗。 文章目录 一、IP和TCP之间的关系&#xff08;提供策略 和 提供能力&#xff09…

QT 基本对话框

包括&#xff1a; 1.标准文件对话框 dialog.h #ifndef DIALOG_H #define DIALOG_H#include <QDialog> #include <QTextCodec> #include <QLabel> #include <QLineEdit> #include <QPushButton> #include <QGridLayout> #include <QFr…

通过DBeaver 给Postgre SQL表 设置主键自增

1.创建表 CREATE TABLE public.company ( id int4 NOT NULL , name text NOT NULL, age int4 NOT NULL, address bpchar(50) NULL, salary float4 NULL, join_date date NULL, CONSTRAINT company_pkey PRIMARY KEY (id) ); 2.插入数据&#xff08;不传入id&#xff…

【Leetcode】104.二叉树的最大深度

一、题目 1、题目描述 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:3示例2: 输入:root = [1,null,2] 输出:2提示: 树中节点的数量在 [0, 104…

并查集及其简单应用

文章目录 一.并查集二.并查集的实现三.并查集的基本应用 一.并查集 并查集的逻辑结构:由多颗不相连通的多叉树构成的森林(一个这样的多叉树就是森林的一个连通分量) 并查集的元素(树节点)用0~9的整数表示,并查集可以表示如下: 并查集的物理存储结构:并查集一般采用顺序结构实…

【Redis】——Redis基础的数据结构以及应用场景

什么是redis数据库 Redis 是一种基于内存的数据库&#xff0c;对数据的读写操作都是在内存中完成&#xff0c;因此读写速度非常快&#xff0c;常用于缓存&#xff0c;消息队列、分布式锁等场景。&#xff0c;Redis 还支持 事务 、持久化、Lua 脚本、多种集群方案&#xff08;主…

Centos7卸载|安装JDK1.8|Xshell7批量控制多个终端

一: 使用yum安装的好处是较为方便|环境变量自动配置完成。 1.1: 执行下面的命令,检查是否已安装了jdk # 查看当前是否安装了JDK&#xff0c; [rootwww ~]# rpm -qa |grep java [rootwww ~]# rpm -qa |grep jdk [rootwww ~]# rpm -qa |grep gcj [rootwww ~]# rpm -qa | grep -…

数据结构——二叉搜索树(附带C++实现版本)

文章目录 二叉搜索树概念 二叉树的实际应用二叉树模拟实现存储结构二叉搜索树构成二叉搜索树的查找插入操作中序遍历二叉树的删除循环(利用左子树最右节点&#xff09;递归(利用右子树根节点) 二叉树拷贝二叉树资源的销毁 二叉树实现完整代码总结 二叉搜索树 概念 二叉搜索树…

PHPStudy 安装tp8 php8.2.9

一、PhpStudy升级PHP版本&#xff0c;安装PHP8.2操作步骤 1.1、官网下载最新的php版本 打开Windows版的官网下载&#xff0c;地址&#xff1a;https://windows.php.net/download/ 页面上有不同的PHP版本&#xff0c;这里我们下载的是64位nts版的PHP8.2.9。 1.2、解压下载的文…

2023.8 - java - 泛型

泛型问题的引出&#xff1a; jdk 1.5 引出泛型 // package 泛型; public class index {public static void main (String[] args){test t new test();t.setContent("aaa");int a (int) t.getContent();System.out.println(a);} }class test{Object content;publi…

国内常见的几款可视化Web组态软件

组态软件是一种用于控制和监控各种设备的软件&#xff0c;也是指在自动控制系统监控层一级的软件平台和开发环境。这类软件实际上也是一种通过灵活的组态方式&#xff0c;为用户提供快速构建工业自动控制系统监控功能的、通用层次的软件工具。通常用于工业控制&#xff0c;自动…

[SWPUCTF 2022 新生赛]ez_ez_php

这段代码是一个简单的PHP文件处理脚本。让我们逐行进行分析&#xff1a; error_reporting(0); - 这行代码设置了错误报告的级别为0&#xff0c;意味着不显示任何错误。 if (isset($_GET[file])) { - 这行代码检查是否存在一个名为"file"的GET参数。 if ( substr($_…

无涯教程-Perl - wantarray函数

描述 如果当前正在执行的函数的context正在寻找列表值,则此函数返回true。在标量context中返回false。 语法 以下是此函数的简单语法- wantarray返回值 如果没有context,则此函数返回undef&#xff1b;如果lvalue需要标量,则该函数返回0。 例 以下是显示其基本用法的示例…

记录Taro巨坑,找不到sass类型定义文件

问题 taronutuisassts项目里tsconfig.json一直报红报错。 找不到“sass”的类型定义文件。 程序包含该文件是因为: 隐式类型库 “sass” 的入口点 其实正常人想的肯定是装上 types/sass试试。开始我试过了&#xff0c;没用。删了依赖重装也没用。后面在issue中找到答案了 解决…