散列/散列函数「建议收藏」

散列/散列函数「建议收藏」散列是一种用于以常数平均时间执行插入、删除和查找的技术。每个关键字被映射到从0-TableSize-1这个范围中的某个数,并且被放到适当的单元中。这种映射就叫做散列函数我认为,先用散列函数将我们所要进行操作的集合整合成散列表,是对之后的操作的一种便利。放到实际中去,我们要进行操作的集合不仅仅只是数字,例如图书馆中的书籍分类等等。而且就算是一组不连续差距较大的数字,要执行后序的插入删除和查找都是很不方

大家好,又见面了,我是你们的朋友全栈君。

散列是一种用于以常数平均时间执行插入、删除和查找的技术。

每个关键字被映射到从0-TableSize-1这个范围中的某个数,并且被放到适当的单元中。这种映射就叫做散列函数

我认为,先用散列函数将我们所要进行操作的集合整合成散列表,是对之后的操作的一种便利。放到实际中去,我们要进行操作的集合不仅仅只是数字,例如图书馆中的书籍分类等等。而且就算是一组不连续差距较大的数字,要执行后序的插入删除和查找都是很不方便的。我们可以通过某种规定,将每个关键字放到合适的为止上去,编写散列函数。但是难免会遇到两个关键词被单列到同一个值的情况,(称为冲突),如何解决冲突是一个很关键的问题,之后另开博。

对于一般的数字,可以通过模运算

一个简单的代码实现如下(不涉及冲突)

#include<stdio.h>

int main()
{
    //自定义数组,存放初始的数字集合 
    int a[9] = {
  
  22,23,25,21,20,27,24,28,26};
    int b[9];
    int i;
    for(i = 0; i < 9; i++)
    {
        b[a[i]%10] = a[i];   //通过模10运算,将关键字散列合适的位置 
    }
    for(i = 0; i < 9; i++)   //输出散列表 
    printf("%d ", b[i]);
    return 0;
} 

输出结果如图

这里写图片描述

如果关键字是字符串,另一个很容易想到的办法是将字符中的ASCII码值加起来
伪代码如下:

Index
Hash(const char *key, int TableSize)
{
    unsigned int HashVal = 0;
    while(*key != '\0')   //循环将字符中的ASCII值加起来
        HashVal += *key++;
    return HashVal % TableSize;  //对TableSize取余并返回其值
}

虽然这种方法简单又很容易得到答案,但是对于很大的表,此函数并不会很到的分配关键字。设所有关键字最多8个字符长,由于char类型的值最多是127,因此这个散列函数之恩那个取值在0到27*8之间,若TableSize超过了1w,显然这并不是一种均匀的分配。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/146415.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • springboot线程池的使用和扩展

    springboot线程池的使用和扩展我们常用ThreadPoolExecutor提供的线程池服务,springboot框架提供了@Async注解,帮助我们更方便的将业务逻辑提交到线程池中异步执行,今天我们就来实战体验这个线程池服务;本文地址:http://blog.csdn.net/boling_cavalry/article/details/79120268实战环境windowns10;jdk1.8;spring

  • MFC之进度条CProgressCtrl

    MFC之进度条CProgressCtrl一、成员函数简介1、create()针对不是通过资源文件上拖拉进度条控件生成的进度条,需要用此函数创建一个。2、SetRange()设置进度条的起始值和终止值。3、SetPos()设置进度条的当前位

  • MPU9250传感器

    MPU9250内部包括3轴陀螺仪、3轴加速度计和3轴磁力计,这3个功能输出都是16位的数字量;可以通过常用的数据总线(IIC)接口和单片机进行数据交互,传输速率400kHz/s。陀螺仪的角速度测量范围±2000(°/s),具有良好的动态响应特性。加速度计的测量范围最大为±16g(g为重力加速度),静态测量精度高。磁力计采用高灵度霍尔型传感器进行数据采集,磁感应强度测量范围为±4800μT,可用于对偏航角的辅助测量。MPU9250自带的数字运动处理器DMP硬件加速引擎,可

  • 操作系统实验五 虚拟存储器管理

    实验五虚拟存储器管理一、实验目的1、理解虚拟存储器概念。2、掌握分页式存储管理地址转换和缺页中断。二、实验内容与基本要求1、模拟分页式存储管理中硬件的地址转换和产生缺页中断。2、用先进先出页面调度算法处理缺页中断。三、实验报告内容1、分页式存储管理和先进先出页面调度算法原理。a.分页式存储管理原理  在存储器管理中,连续分配方式会形成许多“碎片”,虽然可通过“紧凑”方法将

  • pytest指定用例_电脑文件怎么自定义排序

    pytest指定用例_电脑文件怎么自定义排序前言测试用例在设计的时候,我们一般要求不要有先后顺序,用例是可以打乱了执行的,这样才能达到测试的效果.有些同学在写用例的时候,用例写了先后顺序,有先后顺序后,后面还会有新的问题(如:上个用例返回

  • gcc命令大全

    gcc命令大全一、gcc的基本用法使用gcc编译器时,必须给出一系列必要的调用参数和文件名称。不同参数的先后顺序对执行结果没有影响,只有在使用同类参数时的先后顺序才需要考虑。如果使用了多个-L的参数来定义库目录,gcc会根据多个-L参数的先后顺序来执行相应的库目录。因为很多gcc参数都由多个字母组成,所以gcc参数不支持单字母的组合,Linux中常被叫短参数(shortoptions),如-dr…

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号