首页 > 其他分享 >cmu15545-哈希表(Hash Table)

cmu15545-哈希表(Hash Table)

时间:2024-11-09 16:21:07浏览次数:1  
标签:取模 Hash 碰撞 分裂 cmu15545 哈希 Table 指针 Hashing

基本概念

哈希和树一样,是数据库系统中用于访问数据的方法。

image-20241109143725399

空间复杂度:$O(n)$

时间复杂度:$O(1)~ O(n)$

权衡:更大的哈希空间(碰撞减少),还是更少的哈希空间(碰撞处理)?

哈希函数

哈希结构

两种思路:

  • Operating Address【空间换时间】
    • Linear Probe Hashing
    • Cuckoo Hashing
  • Chained Hashing(Bucket)【时间换空间】
  • 结合(渐进式扩展哈希空间)
    • Extenible Hashing
    • Linear Hashing【最常用】

下面探讨如何通过这些机制避免或处理哈希值碰撞。

Linear Probe Hashing

  • 碰撞时移动到下一个槽

  • 删除时建立墓碑:墓碑可以被新值代替;也可以通过垃圾回收清理

    image-20241109145156402

  • 非唯一值怎么存:键值同存(如上图所示,每个槽里存放的是键和值)

Cuckoo Hashing

  • 基本思想:多哈希函数+鸠占鹊巢

  • 注意点:无限循环检测

过程演示:

有空位时:直接占用。

image-20241109152501060

发生碰撞时,如果两个哈希位都已经被占用了,踢出原来的数据,让他重新哈希,以此反复,直到找到空位。

image-20241109152712021

image-20241109152733975

![image-20241109152752871](/Users/iven/Library/Application Support/typora-user-images/image-20241109152752871.png)

获取时只需要找两个哈希位即可。

image-20241109152828049

Chained Hashing

  • 碰撞数据存在哈希桶中,桶满则溢出
  • 布隆过滤器加速查询

image-20241109153732659

Extenible Hashing

依照哈希值的位映射到哈希桶。

00和01指向同一个桶是因为复用。

插入C时,对应的哈希桶10已经满了,选择位增加为3,拓展10的哈希空间为100和101,移动数据,尝试插入。

image-20241109155148853

Linear Hashing

基本思想:

  • 渐进式扩展:当哈希桶溢出时,不是分裂溢出的哈希桶,分裂指针指向的哈希桶,渐进地扩充所有哈希桶。

  • 循环扩展:当本轮所有哈希桶都分裂完后,指针跳转回起始位置,重新开始循环,并丢弃上一轮的哈希函数。

  • 查询保证:查找一个数据最多只会有两次哈希。

过程演示:

插入17时,1号哈希桶溢出,扩展0号哈希桶,分裂指针下移;数据8和20对8取模做数据重分布。

image-20241109155520745

image-20241109160012353

查询值20时,对4取模,落到0号桶,由于在分裂指针上方,说明需要再次对8(2n)取模,落到4号桶内,查询得到值20。

image-20241109160206542

垃圾回收:如果最末位的哈希桶为空,可以删除,然后上移分裂指针。

分裂指针走到哪里跳回开头,不会无限循环吗:有变量记录当前轮的截止位置,避免无限循环。

为什么在0号桶对4取模后,再对8取模,得到的结果只会在0和4号桶,而不会到其他比如5,6,7号桶:见下图。

image-20241109162347072

标签:取模,Hash,碰撞,分裂,cmu15545,哈希,Table,指针,Hashing
From: https://www.cnblogs.com/timothy020/p/18536926

相关文章

  • 【GreatSQL 优化器 - 01】const_table
    一、const_table介绍GreatSQL的优化器主要用JOIN类来进行处理SQL语句的,JOIN类有以下四个table数量相关的成员变量。其中const_tables是optimize最开始就检查并且标识的,因为这样可以把记录最少的表放在执行计划的第一步,在后面的执行计划里面这些consttables是不参......
  • 【GreatSQL优化器-01】const_table
    【GreatSQL优化器-01】const_table一、const_table介绍GreatSQL的优化器主要用JOIN类来进行处理SQL语句的,JOIN类有以下四个table数量相关的成员变量。其中const_tables是optimize最开始就检查并且标识的,因为这样可以把记录最少的表放在执行计划的第一步,在后面的执行计划里面这......
  • 详述stable diffusion的过程 以及扩散过程
    AnswerStableDiffusion是一种基于扩散模型的图像生成技术,广泛应用于文本到图像的生成。其整个过程可以分为三个主要步骤:前向扩散过程、后向训练过程和后向推理过程。以下是对每个步骤的详细说明。1.StableDiffusion概述StableDiffusion通过将图像视为概率分布,并逐步改变......
  • WebMagic抓取 table分页数据, table分页时,URL不变
    动态页面爬虫前的准备:https://www.cnblogs.com/maohuidong/p/18517953一:java添加maven依赖:<dependency><groupId>us.codecraft</groupId><artifactId>webmagic-core</artifactId><version>0.7.4</version></dependency>&......
  • 欢迎 Stable Diffusion 3.5 Large 加入 Diffusers
    作为StableDiffusion3的改进版本,StableDiffusion3.5如今已在HuggingFaceHub中可用,并可以直接使用......
  • 不要再使用 READ TABLE 了,教你如何使用新语法读取内表
    在本文章中,您将了解ABAP7.40版中引入的新读取语法。该语法早在2013年就已引入,因此已不再新鲜。但是,如果您仍在使用READTABLE关键字来读取表项,那么这篇文章绝对适合您。请看下面的示例。请注意,下面的代码是在读取语句之前编写的。DATA:it_flightsTYPESTANDARD......
  • stable diffusion图生图
    本节内容,给大家带来的是stablediffusion的图生图课程,我们在midjourney的课程中有学习过midjourney的图生图功能,即使用垫图的方式来引导AI绘制图片。图生图是AI绘图程序一个非常重要的功能,stablediffusion同样提供了类似的功能,而且stablediffusion图生图功能所提供的选项......
  • stable diffusion 大模型
    本节内容,给大家带来的是stablediffusion的基础模型课程。基础模型,我们有时候也称之为大模型。在之前的课程中,我们已经多次探讨过大模型,并且也见识过一些大模型绘制图片的独特风格,相信大家对stablediffusion大模型已经有了一定的了解。使用不同的大模型,绘制的图片风格,内容,精细......
  • Stable Diffusion LoRA, LyCoris
    本节内容,给大家带来的是stablediffusion的LoRA与LyCoris模型课程。我们在上节课程中,已经详细讲解了关于大模型的使用。在stablediffusion中打造一个大模型,需要基于大量特定特征的图像集进行训练,我们通常将这个过程称之为Dreambooth训练,这个过程比较耗时,同时对计算资源的要求......
  • 【comfyui教程】ComfyUI 现已支持 Stable Diffusion 3.5 Medium!人人都能轻松上手的图
    前言ComfyUI现已支持StableDiffusion3.5Medium!人人都能轻松上手的图像生成利器大家翘首以盼的StableDiffusion3.5Medium模型终于来了!就在今天,StabilityAI正式推出了这款“亲民版”平衡模型,让创作者们得以在消费级GPU上体验到AI图像生成的最新黑科技。本文将带......